QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426044 | #6349. Is This FFT? | ushg8877 | WA | 2850ms | 169364kb | C++14 | 2.9kb | 2024-05-30 20:39:11 | 2024-05-30 20:39:11 |
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-((r*m)>>64)*p;
}
}using namespace FastMod;
namespace polynomial{// yjl poly plank 5.0 ver
const int MR=1e6+5;
int bfly[MR];
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(i);
NTT(S,M,-1);
for(int m=1;m<=n*(n-1)/2;m++){
f[n][m]=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: 4ms
memory: 11152kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Wrong Answer
time: 2850ms
memory: 169364kb
input:
250 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062 289137877 768923227 177538883 440227465 101981224 874960215 35275208 664066979 334444870 46651494 799130693 122319095 913072242 44703442 965640306 52873544 461938281 263838691 777326453 356621754 560569747 812581766 46147702 12...
result:
wrong answer 39th numbers differ - expected: '818005', found: '999062358'