QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#450558 | #6349. Is This FFT? | zyz07 | TL | 2ms | 7368kb | C++17 | 2.2kb | 2024-06-22 15:30:02 | 2024-06-22 15:30:02 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define range(Tx) begin(Tx),end(Tx)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using ll=long long;
struct FastMod{
using ull=unsigned long long;
using L=__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;
}
}Mod(2);
template<typename T>
T operator%(T x,const FastMod& Mod){
return Mod.reduce(x);
}
template<typename T>
T& operator%=(T& x,const FastMod& Mod){
return x=Mod.reduce(x);
}
ll power(ll x,ll y){
ll r=1;
for(;y;y>>=1,x=x*x%Mod){
if(y&1) r=r*x%Mod;
}
return r;
}
int C2(int x){
return x*(x-1)/2;
}
const int N=255;
int n,mod;
ll f[N][N*N/2],a1[N*N/2],a2[N*N/2];
__int128 g[N*N/2];
ll fac[N*N],inv[N*N],ifac[N*N];
void init_fac(){
fac[0]=1;
For(i,1,N*N-1) fac[i]=fac[i-1]*i%Mod;
inv[1]=1;
For(i,2,N*N-1) inv[i]=(mod-mod/i)*inv[mod%i]%Mod;
ifac[0]=ifac[1]=1;
For(i,2,N*N-1) ifac[i]=ifac[i-1]*inv[i]%Mod;
}
ll combine(int n,int m){
return fac[n+m]*ifac[n]%Mod*ifac[m]%Mod;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>mod;
Mod=FastMod(mod);
init_fac();
f[0][0]=1;
For(i,1,n){
For(j,0,(i-1)/2){
memset(g,0,sizeof(g));
int cnt=(j+1)*(i-j)-1;
For(k,0,C2(j)){
a1[k]=f[j][k]*ifac[C2(j+1)-k]%Mod;
}
For(k,0,C2(i-1-j)){
a2[k]=f[i-1-j][k]*ifac[C2(i-j)-k]%Mod;
}
int l1=C2(j),l2=C2(i-1-j);
For(k1,0,l1){
#pragma GCC unroll 16
For(k2,0,l2){
g[k1+k2]+=a1[k1]*a2[k2];
}
}
if((i-1)%2||j<(i-1)/2){
For(k,0,C2(j)+C2(i-1-j)){
g[k]*=2;
}
}
For(k,0,C2(j)+C2(i-1-j)){
(f[i][k+cnt]+=g[k]%mod*fac[k+cnt]%Mod*fac[C2(j+1)+C2(i-j)-k])%=Mod;
}
}
Dec(j,C2(i),0){
(f[i][j]+=f[i][j+1])%=Mod;
}
For(j,0,C2(i)){
(f[i][j]*=ifac[j])%=Mod;
}
}
For(i,1,n-1){
ll ans=f[i][0],inv=2;
For(j,1,i+1){
(ans*=j)%=Mod;
}
For(j,1,i*(i+1)/2){
(inv*=j)%=Mod;
}
cout<<ans*power(inv,mod-2)%Mod<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7368kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
250 998244353