QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426025 | #6349. Is This FFT? | ushg8877 | WA | 2937ms | 167944kb | C++14 | 3.0kb | 2024-05-30 20:26:52 | 2024-05-30 20:26:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define poly vector<long long>
const int MAXN=255;
ll MOD,k;
ll f[MAXN][MAXN*MAXN];
namespace FastMod{
ll m,p;
void init(ll pp){m=-1ull/pp,p=pp;}
ll Mod(LL r){
// return r%p;
return r-((r*m)>>64)*p;
}
}using namespace FastMod;
namespace polynomial{// yjl poly plank 5.0 ver
int bfly[MAXN];ll inver[MAXN];
int clogg(int x){return (int)ceil(log2(x));}
ll ksm(ll a,int b){
ll res=1;
while(b){
if(b&1)res=Mod(res*a);
a=Mod(a*a),b>>=1;
}
return res;
}
void butterfly(int l){
static int las;
if(las!=l){
las=l;
for(int i=1;i<(1<<l);i++)
bfly[i]=(bfly[i>>1]>>1)|((i&1)<<(l-1));
}
}
void NTT(poly &f,int l,int typ){
butterfly(l);f.resize(1<<l);
for(int i=0;i<(1<<l);i++)
if(bfly[i]<i) swap(f[i],f[bfly[i]]);
for(int i=0;i<l;i++){
ll step=ksm(3,MOD-1+((MOD-1)>>(i+1))*typ);
for(int j=0;j<(1<<l);j+=(1<<(i+1))){
ll cur=1,l=j+(1<<i);
for(int k=j;k<l;k++){
ll u=f[k],v=Mod(f[k|(1<<i)]*cur);
f[k]=(u+v>MOD?u+v-MOD:u+v);
f[k|(1<<i)]=(u>=v?u-v:u-v+MOD);
cur=Mod(cur*step);
}
}
}
if(typ==-1){
ll val=ksm(1<<l,MOD-2);
for(int i=0;i<(1<<l);i++)
f[i]=Mod(val*f[i]);
}
return;
}
poly operator *(poly f,poly g){
while(!f.empty()&&f.back()==0) f.pop_back();
while(!g.empty()&&g.back()==0) g.pop_back();
if(f.empty()||g.empty()) return (poly){};
int n=f.size()+g.size(),l=clogg(f.size()+g.size());
if(n<=64){
poly h(n-1);
for(int i=0;i<(int)f.size();i++)
for(int j=0;j<(int)g.size();j++)
h[i+j]+=Mod(f[i]*g[j]);
for(ll &i:h) i=Mod(i);
return h;
}
NTT(f,l,1);NTT(g,l,1);
for(int i=0;i<(1<<l);i++)
f[i]=Mod(f[i]*g[i]);
NTT(f,l,-1);f.resize(n-1);
return f;
}
}using namespace polynomial;
ll fac[MAXN*MAXN],inf[MAXN*MAXN];
ll C(int n,int m){return n<0||n>m?0:inf[n]*inf[m-n]%MOD*fac[m]%MOD;}
poly F1[MAXN],F2[MAXN];
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
cin>>k>>MOD;
int M=k*(k-1)/2+1;M=ceil(log2(M));
init(MOD);
fac[0]=inf[0]=1;
for(int i=1;i<MAXN*MAXN;i++) inf[i]=ksm(fac[i]=Mod(fac[i-1]*i),MOD-2);
f[1][0]=1;
F1[1].resize(1<<M);F2[1].resize(1<<M);
F1[1][0]=F2[1][0]=1;
NTT(F1[1],M,0);NTT(F2[1],M,0);
for(int n=2;n<=k;n++) {
poly S(1<<M);
for(int j=1;j<n;j++){
for(int k=0;k<(1<<M);k++){
S[k]+=Mod(F1[j][k]*F2[n-j][k]);
}
}
for(auto &i:S) i%=MOD;
NTT(S,M,-1);
for(int m=1;m<=n*(n-1)/2;m++){
f[n][m]=Mod(Mod(Mod(S[m-1])*fac[n-1])*fac[m-1]);
f[n][m]+=Mod(f[n][m-1]*(n*(n-1)/2-(m-1)));
f[n][m]=Mod(f[n][m]);
}
cout<<Mod(f[n][n*(n-1)/2]*inf[n*(n-1)/2])<<'\n';
F1[n].resize(1<<M),F2[n].resize(1<<M);
for(int i=0;i<=n*(n-1)/2;i++){
F1[n][i]=Mod(Mod(f[n][i]*inf[i])*inf[n-1]*2);
F2[n][i]=Mod(Mod(f[n][i]*inf[i])*inf[n]*2);
}
NTT(F1[n],M,1);NTT(F2[n],M,1);
}
cerr<<"Running Time: "<<1.*clock()/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 6572kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Wrong Answer
time: 2937ms
memory: 167944kb
input:
250 998244353
output:
-2107851819028540352 6719310354008743552 -5718155327817594176 4439775979115156288 5698243052357608896 -3363420986174434880 -2153519732297877952 1908936086629346432 2878629324277894528 8899560095114821120 -1279390385840301184 2267361914661411712 -9046357032216973760 3084450194807393216 23469347211880...
result:
wrong answer 1st numbers differ - expected: '1', found: '-2107851819028540352'