QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426050 | #6349. Is This FFT? | ushg8877 | WA | 3906ms | 172880kb | C++14 | 3.0kb | 2024-05-30 20:41:01 | 2024-05-30 20:41:01 |
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){
r=r-((r*m)>>64)*p;
return (r>=p?r-p:r);
}
}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';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 8544kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 3906ms
memory: 168844kb
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:
ok 249 numbers
Test #3:
score: 0
Accepted
time: 3735ms
memory: 172880kb
input:
250 65537
output:
1 1 8739 5982 43573 63055 50957 48651 15842 40150 26535 53234 50550 8708 34485 48568 52730 2494 37477 52676 25640 62555 6175 28734 38834 6442 35198 41267 12029 47992 59673 56920 23395 6921 24280 30992 26117 42844 58258 60841 45860 45174 7890 61836 33308 31989 46003 26412 65049 3275 27651 24854 19324...
result:
ok 249 numbers
Test #4:
score: -100
Wrong Answer
time: 32ms
memory: 10300kb
input:
53 388104193
output:
1 1 103494452 258736129 366591373 316042954 8286743 165719455 76764487 79569391 119920409 248672172 70967921 288830028 372167317 246601528 217075355 30878703 257713757 195596822 74307888 28760556 40144420 152500056 256417368 179569968 233881251 14265023 139285509 52123153 223568602 85340031 38657339...
result:
wrong answer 3rd numbers differ - expected: '336356968', found: '103494452'