QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463889 | #6349. Is This FFT? | zyz07 | WA | 6268ms | 76364kb | C++17 | 4.1kb | 2024-07-05 15:39:26 | 2024-07-05 15:39:26 |
Judging History
answer
#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,typename=enable_if_t<is_integral_v<T>>>
T operator%(T x,const FastMod& Mod){
return Mod.reduce(x);
}
template<typename T,typename=enable_if_t<is_integral_v<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)>>1;
}
namespace NTT{
unsigned P;
int G;
const int N=1<<16;
template<typename T>
void mod(T& x){
x=(x>=P?x-P:x);
}
unsigned long long W[N],IW[N];
void init(int n){
const int IG=power(G,P-2);
for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
for(int i=0,wn=power(G,(P-1)/l),iwn=power(IG,(P-1)/l),w=1,iw=1;i<mid;i++)
W[mid+i]=w,IW[mid+i]=iw,w=((ll)w*wn)%P,iw=((ll)iw*iwn)%P;
}
void dft(unsigned long long* f,int n){
unsigned long long x,y;
for(int l=n,mid=l>>1;l>=2;l>>=1,mid>>=1)
for(int p=0;p<n;p+=l){
#pragma GCC unroll 16
for(int i=0;i<mid;i++)
x=f[p+i],y=f[p+mid+i],mod(f[p+i]+=y),f[p+mid+i]=W[mid+i]*(P+x-y)%Mod;
}
}
void idft(unsigned long long* f,int n){
unsigned long long x,y;
for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
for(int p=0;p<n;p+=l){
#pragma GCC unroll 16
for(int i=0;i<mid;i++)
x=f[p+i],y=f[p+mid+i]*IW[mid+i]%Mod,mod(f[p+i]+=y),mod(f[p+i+mid]=P+x-y);
}
for(int i=0,invn=power(n,P-2);i<n;i++){
f[i]=f[i]*invn%Mod;
}
}
int gt(int l){
int n=1;
while(n<l)n<<=1;
return n;
}
}
const int N=255;
int n,mod;
ll f[N][N*N/2];
unsigned long long g[N*N],g_[N*N/2],a1[N*N],a2[N*N],dft[N][1<<15];
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;
}
void findrt(){
int t=mod-1;
vector<int> vs;
for(int i=2;i<=t&&i*i<=mod;i++){
if(t%i==0){
vs.push_back(i);
while(t%i==0) t/=i;
}
}
if(t!=1) vs.push_back(t);
for(int i=2;i<=mod;i++){
bool flag=true;
for(int j:vs){
if(power(i,(mod-1)/j)==1){
flag=false;
break;
}
}
if(flag)return NTT::G=i,void();
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>mod;
Mod=FastMod(mod);
NTT::P=mod;
findrt();
NTT::init(1<<15);
const int m=1<<14;
init_fac();
f[0][0]=1;
For(i,1,n){
For(j,0,(i-1)/2){
int cnt=(j+1)*(i-j)-1,l1=C2(j),l2=C2(i-1-j);
if(min(l1,l2)>300){
copy(range(dft[j]),a1);
copy(range(dft[i-1-j]),a2);
For(k,0,m-1){
g[k]=a1[k]*a2[k]%Mod;
}
NTT::idft(g,m);
int w=1+((i-1)%2||j<(i-1)/2);
For(k,0,C2(j)+C2(i-1-j)){
(f[i][k+cnt]+=g[k]*fac[C2(j+1)+C2(i-j)-k]*w)%=Mod;
}
}else{
memset(g_,0,sizeof(g_));
For(k,0,l1){
a1[k]=f[j][k]*ifac[C2(j+1)-k]%Mod;
}
For(k,0,l2){
a2[k]=f[i-1-j][k]*ifac[C2(i-j)-k]%Mod;
}
For(k1,0,l1){
#pragma GCC unroll 16
For(k2,0,l2){
g_[k1+k2]+=a1[k1]*a2[k2];
}
if(k1==l1||!(k1&15)){
#pragma GCC unroll 16
For(k,0,l1+l2){
g_[k]%=Mod;
}
}
}
int w=1+((i-1)%2||j<(i-1)/2);
For(k,0,C2(j)+C2(i-1-j)){
(f[i][k+cnt]+=g_[k]*fac[C2(j+1)+C2(i-j)-k]*w)%=Mod;
}
}
}
Dec(j,C2(i),0){
f[i][j]=(f[i][j]*fac[j]+f[i][j+1])%Mod;
}
For(j,0,C2(i)){
(f[i][j]*=ifac[j])%=Mod;
}
if(C2(i)>300){
For(j,0,C2(i)){
dft[i][j]=f[i][j]*ifac[C2(i+1)-j]%Mod;
}
NTT::dft(dft[i],m);
}
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12748kb
input:
10 998244353
output:
1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
ok 9 numbers
Test #2:
score: -100
Wrong Answer
time: 6268ms
memory: 76364kb
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 207th numbers differ - expected: '888624150', found: '712504328'