QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463446 | #6349. Is This FFT? | atgc | RE | 0ms | 0kb | C++23 | 4.2kb | 2024-07-04 20:56:38 | 2024-07-04 20:56:39 |
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
int n,m,mod,N,iN,d;
template <class ADD>
inline void add(ADD &x,ADD y){
x += y;
if(x >= mod) x -= mod;
}
template <class SUB>
inline void sub(SUB &x,SUB y){
x -= y;
if(x < 0) x += mod;
}
__int128 mu;
namespace barrett {
inline ll reduce(ll x) {
ll r = x - (mu * x >> 64) * mod;
return r >= mod ? r - mod : r;
}
inline void setmod(ll mod) {
mu = -1ull / mod;
}
}
using namespace barrett;
ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}
int lim[255];
ll dp[255][32005],val[255][65536],tmp[65536],fact[32005],ifac[32005],inv[32005];
int g;
int test(){
if(power(g,(mod - 1) / 2) == 1) return 0;
int cur = mod - 1;
while(cur % 2 == 0) cur /= 2;
for(int i = 2;i * i <= cur;i++){
if(cur % i) continue;
if(power(g,(mod - 1) / i) == 1) return 0;
while(cur % i == 0) cur /= i;
}
return 1;
}
void init(){
g = 1;
while(!test()) g++;
// printf("find g=%d\n",g);
}
ll ww[20][65536],iw[20][65536];
void reinit(){
rep(i,0,d){
ll w0 = power(g,(mod - 1) >> i);
ww[i][0] = 1;
rep(k,1,(1 << i) - 1) ww[i][k] = reduce(ww[i][k - 1] * w0);
w0 = power(w0);
iw[i][0] = 1;
rep(k,1,(1 << i) - 1) iw[i][k] = reduce(iw[i][k - 1] * w0);
}
}
void FFT(ll *f,int len,int op){
if(len == 1) return;
int hf = len / 2;
rep(i,0,hf - 1){
tmp[i] = f[2 * i];
tmp[i + hf] = f[2 * i + 1];
}
rep(i,0,len - 1) f[i] = tmp[i];
FFT(f,hf,op);FFT(f + hf,hf,op);
ll qwq;
int p = __lg(len);
rep(i,0,hf - 1){
tmp[i] = tmp[i + hf] = f[i];
if(op == 1) qwq = reduce(f[i + hf] * ww[p][i]);
else qwq = reduce(f[i + hf] * iw[p][i]);
add(tmp[i],qwq);
sub(tmp[i + hf],qwq);
}
rep(i,0,len - 1) f[i] = tmp[i];
}
void recalc(int i){
rep(s,0,lim[i]) val[i][s] = reduce(dp[i][s] * ifac[s]);
fill(val[i] + lim[i] + 1,val[i] + N,0);
FFT(val[i],N,1);
}
int main(){
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
// freopen("sub7_3.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&mod);
setmod(mod);
m = n * (n - 1) / 2;
N = iN = 1;
init();
reinit();
fact[0] = 1;
rep(i,1,m) fact[i] = fact[i - 1] * i % mod;
ifac[m] = power(fact[m]);
per(i,m - 1,0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
// rep(i,1,m) printf("%lld ",ifac[i]);
// printf("\n");
rep(i,1,m) inv[i] = ifac[i] * fact[i - 1] % mod;
cerr << clock() << endl;
rep(i,1,n) lim[i] = i * (i + 1) / 2;
dp[0][0] = val[0][0] = 1;
FFT(val[0],N,1);
rep(i,1,n - 1){
if(N <= lim[i]){
while(N <= lim[i]){
N *= 2;
d++;
}
reinit();
rep(j,0,i - 1) recalc(j);
iN = power(N);
}
rep(p,1,i){
rep(k,0,N - 1) val[i][k] += val[p - 1][k] * val[i - p][k];
if((p & 7) == 0) rep(k,0,N - 1) val[i][k] = reduce(val[i][k]);
}
rep(k,0,N - 1) val[i][k] = reduce(val[i][k]);
FFT(val[i],N,-1);
rep(s,0,lim[i]){
dp[i][s + 1] = reduce(val[i][s] * fact[s]);
dp[i][s + 1] = reduce(dp[i][s + 1] * iN);
}
rep(s,0,lim[i]) add(dp[i][s + 1],reduce(dp[i][s] * (lim[i] - s)));
rep(s,0,lim[i]) val[i][s] = reduce(dp[i][s] * ifac[s]);
FFT(val[i],N,1);
// rep(s,0,m) printf("%lld ",dp[i][s]);
// printf("\n");
}
ll i2 = power(2);
rep(i,1,n - 1){
ll output = reduce(dp[i][i * (i + 1) / 2] * fact[i + 1]);
output = reduce(output * i2);
// printf("%lld ",output);
printf("%lld\n",reduce(output * ifac[i * (i + 1) / 2]));
}
cerr << clock() << endl;
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
10 998244353