QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#908464#4228. Double SortlarryyuWA 0ms9960kbC++201.1kb2025-02-20 22:42:202025-02-20 22:42:20

Judging History

This is the latest submission verdict.

  • [2025-02-20 22:42:20]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 9960kb
  • [2025-02-20 22:42:20]
  • Submitted

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'