QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#908464 | #4228. Double Sort | larryyu | WA | 0ms | 9960kb | C++20 | 1.1kb | 2025-02-20 22:42:20 | 2025-02-20 22:42:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
#define ll long long
int n,m;
int c[5050][5050],d[1000010],e[5050];
int fac[1000010],inv[1000010],pre[5050];
ll po(ll x,int y){
ll z=1;
while(y){
if(y%2) z=z*x%mo;
x=x*x%mo,y/=2;
}
return z;
}
void add(int &x,int y){
x+=y;
if(x>=mo) x-=mo;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>n>>m;
c[1][1]=c[1][0]=1;
for(int i=2;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=n;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;
}
fac[0]=1;
for(int i=1;i<=m;i++)
fac[i]=(ll)fac[i-1]*i%mo;
inv[m]=po(fac[m],mo-2);
for(int i=m-1;~i;i--)
inv[i]=(ll)inv[i+1]*(i+1)%mo;
for(int i=n;i<=m;i++)
d[i]=(ll)fac[i]*inv[i-n]%mo*inv[n]%mo;
for(int i=1;i<=n;i++)
for(int j=0;j<=m-1&&m-j*i>=n;j++)
add(pre[i],d[m-j*i]);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
add(e[n-i+1],(ll)((j-i)&1?mo-1:1)*c[j][i]%mo*c[n][j]%mo*pre[j]%mo);
}
}
for(int i=1;i<=n;i++)
add(e[i],e[i-1]);
int f=po(d[m],mo-2);
for(int i=1;i<=n;i++){
add(e[i],e[i-1]);
cout<<(ll)e[i]*f%mo<<'\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9960kb
input:
3 5
output:
1 100000003 500000008
result:
wrong answer 2nd numbers differ - expected: '2.3000000', found: '100000003.0000000', error = '43478261.1739130'