QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463437 | #6349. Is This FFT? | atgc | RE | 0ms | 0kb | C++14 | 2.7kb | 2024-07-04 20:50:05 | 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';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
10 998244353