QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451096#6349. Is This FFT?EXODUSWA 15ms11108kbC++174.4kb2024-06-22 21:01:272024-06-22 21:01:27

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 21:01:27]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:11108kb
  • [2024-06-22 21:01:27]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define Debug(...) fprintf(stderr,__VA_ARGS__)
#define Exit(p) fprintf(stderr,"[exit]: at breakpoint %d\n",p),exit(0);
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)
template<typename T>void read(T &x){x=0;T flg=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x*=flg;}
template<typename T,typename... Args>void read(T &x,Args &...args){read(x),read(args...);}
template<typename T>void cmax(T& x,T y){x=max(x,y);}
template<typename T,typename... Args>void cmax(T& x,T y,Args ...args){cmax(x,y);cmax(x,args...);}
template<typename T>void cmin(T& x,T y){x=min(x,y);}
template<typename T,typename... Args>void cmin(T& x,T y,Args ...args){cmin(x,y);cmin(x,args...);}
template<typename T,typename U>ostream &operator<<(ostream &os,const pair<T,U>&x){return os<<"("<<x.first<<","<<x.second<< ")"; };
template<typename T>ostream &operator<<(ostream &os,const vector<T> &as){const int sz=as.size();os<<"[";for(int i=0;i<sz;++i){if(i>=256){os<<",...";break;}if(i>0){os<<",";}os<<as[i];}return os<<"]";}
bool membg=0;

constexpr int N=257;
int n,groot,mod,fac[N*N],ifac[N*N],rev[N*N];
int f[N][N*N],h[N][N*N];
int g[N*N];
struct Barret{
	ull p,m;
	Barret(ull _p=2):p(_p),m(((i128)1<<64)/_p){}
	ull mod(ull x){
		ull q=((i128)x*m)>>64;
		x-=q*p;
		return x>=p?x-p:x;
	}
}M;

bool memed=0;

int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=(ll)x*x%mod)
		if(y&1)res=(ll)res*x%mod;
	return res;
}

typedef unsigned long long ull;
void ntt_transfer(std::vector<int>& f, int len, const int g, int tp) {
	f.resize(len);
	for(int i = 0;i < (int)f.size();i++)
		if(i<rev[i])
			swap(f[i],f[rev[i]]);
	std::vector<ull> temp(f.size());
	for (int i = 0; i < (int)f.size(); i++)
		temp[i] = f[i];
	for (int mid = 1; mid < (int)f.size(); mid <<= 1) {
		int len = (mid << 1);
		int cur = qpow(tp ? g : qpow(g, mod - 2), (mod - 1) / len);
		for (int l = 0; l < (int)f.size(); l += len) {
			ull buf = 1;
			for (int k = l; k < l + mid; k++) {
				ull w1 = temp[k], w2 = temp[k + mid] * buf % mod;
				temp[k] = w1 + w2; temp[k + mid] = w1 + mod - w2;
				buf = buf * cur % mod;
			}
		}
	}
	for (int i = 0; i < (int)f.size(); i++)
		f[i] = temp[i] % mod;
	if (!tp) {
		auto inv = qpow(f.size(), mod - 2);
		for (int i = 0; i < (int)f.size(); i++)
			f[i] = (ll) f[i] * inv % mod;
	}
}

int check(int w){
	int t=mod-1;
	for(int i=2;i*i<=t;i++){
		if(t%i==0){
			while(t%i==0)t/=i;
			if(qpow(w,(mod-1)/i)==1)
				return 0;
		}
	}
	if(t>1)
		if(qpow(w,(mod-1)/t)==1)
			return 0;
	return 1;
}

void getgen(){
	for(int i=2;;i++){
		if(check(i)){
			groot=i;
			return;
		}
	}
}

int binom(int n,int m){
	return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}


void solve(){
	read(n,mod);
	M=Barret(mod);
	int inv2=(mod+1)>>1;
	getgen();
	int len=1;
	while(len<=n*(n-1)/2)len<<=1;
	int cnt=0;
	while(len!=(1<<cnt))cnt++;
	for(int i=1;i<len;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));
	for(int i=fac[0]=ifac[0]=1;i<N*N;i++)
		fac[i]=(ll)fac[i-1]*i%mod,ifac[i]=qpow(fac[i],mod-2);
	f[1][0]=1;
	vector<int>G(len),H(len);
	int tot=0;
	for(int i=1;i<=n;i++){
		memset(g,0,sizeof(g));
		for(int k=1;k<i;k++)
			for(int j=0;j<len;j++)
				g[j]=M.mod(g[j]+M.mod((ull)h[k][j]*h[i-k][j])*binom(i,k));
		G.assign(g,g+len);
		// cout<<G<<'\n';
		int tbg=clock();
		ntt_transfer(G,len,groot,0);
		tot+=clock()-tbg;
		for(int j=1;j<=i*(i-1)/2;j++)
			f[i][j]=M.mod(M.mod((ll)G[j-1]*fac[j-1])*inv2);
		for(int j=1;j<=i*(i-1)/2;j++)
			f[i][j]=M.mod(f[i][j]+(ll)f[i][j-1]*(i*(i-1)/2-j+1));
		for(int j=0;j<=i*(i-1)/2;j++)
			h[i][j]=M.mod((ll)(1+(i!=1))*f[i][j]*ifac[j]);
		H.assign(h[i],h[i]+len);
		tbg=clock();
		ntt_transfer(H,len,groot,1);
		tot+=tbg-clock();
		// cout<<H<<'\n';
		for(int j=0;j<len;j++)
			h[i][j]=H[j];
	}
	for(int i=1;i<=n;i++)
		printf("%lld\n",(ll)f[i][i*(i-1)/2]*ifac[i*(i-1)/2]%mod);
	return;
}
int main(){
	Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
	int timbg=clock();
	int T=1;
	while(T--)solve();
	int timed=clock();
	Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
	fflush(stdout);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 11108kb

input:

10 998244353

output:

1
1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062

result:

wrong answer 3rd numbers differ - expected: '532396989', found: '1'