QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463437#6349. Is This FFT?atgcRE 0ms0kbC++142.7kb2024-07-04 20:50:052024-07-04 20:50:05

Judging History

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

  • [2024-07-04 20:50:05]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-04 20:50:05]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
// #define ull uint64_t
#define ull int64_t
#define d(i) ((i)*(i-1) >> 1)
using namespace std;
const int N = 201;
const int maxn = N*(N-1)>>1;

struct FastMod{
    using ull=unsigned long long;
    using L=unsigned __int128;
    ull b,m;
    FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
    ull reduce(ull a) const{
        ull q=(ull)((L(m)*a)>>64),r=a-q*b;
        return r>=b?r-b:r;
    }
    inline operator int(){return b;}
    int sub(int a,int c)const{
    	a-=reduce(c);
    	return (a>>63)?a+b:a;
    }
}mod(2);
template<typename T,typename=enable_if_t<is_integral<T>::value>>
T operator%(T x,const FastMod& Mod){
	// assert(x%Mod.b == Mod.reduce(x));
    return Mod.reduce(x);
}
template<typename T,typename=enable_if_t<is_integral<T>::value>>
T& operator%=(T& x,const FastMod& Mod){
	// assert(x%Mod.b == Mod.reduce(x));
    return x=Mod.reduce(x);
}

int n,G;
ull qpow(ull a,ull n){ull ans=1;while(n){if(n&1)(ans*=a)%=mod;(a*=a)%=mod,n>>=1;}return ans;}
ull inv[maxn],fac[maxn],ifac[maxn];
void init(){
	fac[0]=ifac[0]=inv[1]=fac[1]=ifac[1]=1;
	for(int i=2;i<maxn;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod,fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
}
int calG() {
	vector<int>ps;
	int x=mod-1;//assert(__builtin_ctz(x) >= 17);
	ps.push_back(2);x>>=__builtin_ctz(x);
	for(int i=3;i*i<=x;++i)if(x%i==0){ps.push_back(i);while(x%i==0)x/=i;}
	if(x!=1)ps.push_back(x);
	for(int G=2;;++G){
		for(int p:ps)
			if(qpow(G, (mod-1)/p) == 1) goto nxt;
		return G;nxt:;
	}
}
//cnt P that len=[j], pts = [i].

int rv[1<<15];
ull f[1<<15], g[N][1<<15];
void NTT(ull*a,int n){
	for(int i=1;i<n;++i)if(i<(rv[i]=(rv[i>>1]|(i&1)*n)>>1))swap(a[i],a[rv[i]]);
	for(int L=1;L<n;L<<=1)for(int i=0,wn=qpow(G,(mod-1)/L>>1);i<n;i+=L<<1) {
		ull w=1;
		for(int j=0;j<L;++j,(w*=wn)%=mod) {
			const ull u=a[i|j],v=a[i|L|j];
			a[i|j]=(u+w*v)%mod,a[i|L|j]=mod.sub(u,w*v);
		}
	}
}
void INTT(ull*a,int n){NTT(a,n);reverse(a+1,a+n);for(int i=0,iv=qpow(n,mod-2);i<n;++i)(a[i]*=iv)%=mod;}


signed main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int modd;cin>>n>>modd;mod=FastMod(modd);
	init();G=calG();int N=1<<15;

	inv[0]=1;g[1][0]=1;NTT(g[1],N);
	cout<<"1\n";
	for(int i=2;i<=n;++i) {
		memset(f,0,sizeof f);
		for(int li=1;li<=i-li;++li)
			for(int j=0;j<N;++j)
				(f[j] += g[li][j]*g[i-li][j] << ((li<<1)!=i) ) %= mod;
		INTT(f,N);

		memmove(f+1,f,d(i) * sizeof f[0]);
		f[i-2]=0;

		for(int j=i-1;j<=d(i);++j) {
			(f[j] += f[j-1]*(d(i)-j+1)%mod*inv[j-1]) %= mod,
			g[i][j] = f[j]*inv[j]%mod;
		}

		NTT(g[i],N);

		cout<<(f[d(i)]*inv[d(i)]%mod*fac[i]%mod*inv[2]%mod+mod)%mod<<'\n';
	}
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

10 998244353

output:


result: