QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463261 | #6349. Is This FFT? | bear0131 | WA | 27ms | 11596kb | C++14 | 4.5kb | 2024-07-04 16:42:04 | 2024-07-04 16:42:04 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
struct BarrettModulo{
ll p;
__int128 q;
void init(int Mod){
p = Mod, q = ((__int128)1 << 64) / Mod;
}
ll mod(ll x){
ll ret = (x - ((ll)(((__int128)x * q) >> 64) * p));
(ret >= p) ? (ret -= p) : ret;
return ret;
}
} barrett;
int Mod, g_g;
inline void uadd(int &a, const int &b){ a += b - Mod; a += (a>>31) & Mod; }
inline int add(int a, const int &b){ a += b - Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)barrett.mod(1ll * a * b); }
inline int mul(const int &a, const int &b){ return (int)barrett.mod(1ll * a * b); }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 33333;
int fact[fN], invfact[fN], inv[fN];
void initfact(int n){
fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i - 1], i);
invfact[n] = qpow(fact[n], Mod - 2); for(int i = n; i > 0; --i) invfact[i - 1] = mul(invfact[i], i);
for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i - 1]);
}
inline int binom(int n, int m){ return mul(fact[n], mul(invfact[m], invfact[n - m])); }
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> inline void chmax(T &_a, const T &_b){ (_b>_a) ? (_a=_b) : _a; }
template<typename T> inline void chmin(T &_a, const T &_b){ (_b<_a) ? (_a=_b) : _a; }
namespace poly{
int N, bl = -1;
int w[1111111], to[1111111];
void initN(int _n){
int nbl = 0;
while(1<<nbl < _n) ++nbl;
if(nbl == bl) return ;
bl = nbl, N = 1 << bl;
rep(i, N) to[i] = (to[i >> 1] >> 1) | ((i & 1) << (bl - 1));
w[0] = 1, w[1] = qpow(g_g, (Mod - 1) / N);
for(int i = 2; i <= N; ++i) w[i] = mul(w[i - 1], w[1]);
}
void dft(vi &a, int idft = 0){
a.resize(N);
rep(i, N) if(to[i] < i) swap(a[i], a[to[i]]);
for(int len = 0; len < bl; ++len) for(int l = 0; l < N; l += (1<<(len+1))){
for(int i = 0; i < (1<<len); ++i){
int x = a[l + i], y = mul(a[l + (1<<len) + i], w[i << (bl-len-1)]);
a[l + i] = add(x, y), a[l + (1<<len) + i] = sub(x, y);
}
}
if(idft){
for(int i = 1; i < N - i; ++i) swap(a[i], a[N - i]);
int invn = qpow(N, Mod - 2);
rep(i, N) umul(a[i], invn);
}
}
vi conv(vi a, vi b){
initN((int)a.size() + (int)b.size() - 1);
dft(a), dft(b);
rep(i, N) umul(a[i], b[i]);
dft(a, 1);
while(a.back() == 0) a.pop_back();
return a;
}
}
int n;
int C2[222];
int sum[222][22222];
vi g[222];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> Mod;
barrett.init(Mod);
initfact(22222);
{
vi fac;
int t = Mod - 1;
for(int x = 2; x * x <= t; ++x) if(t % x == 0){
fac.push_back(x);
while(t % x == 0) t /= x;
}
if(t > 1) fac.push_back(t);
for(g_g = 2; ; ++g_g){
bool ok = 1;
rep(i, (int)fac.size()){
if(qpow(g_g, (Mod - 1) / fac[i]) % Mod == 1){ ok = 0; break; }
}
if(ok) break;
}
}
//{
// int A, B;
// cin >> A >> B;
// vi a(A+1), b(B+1);
// rep(i, A+1) cin >> a[i];
// rep(i, B+1) cin >> b[i];
// a = poly::conv(a, b);
// rep(i, A+B+1) cout << a[i] << " ";
// cout << endl;
// return 0;
//}
rep(i, n+1) C2[i] = (i * (i-1)) / 2;
poly::initN(32768);
sum[1][0] = 1;
g[1].push_back(1);
poly::dft(g[1]);
cout << "1\n";
for(int i = 2; i <= n; ++i){
vector<__int128> tmp(poly::N, 0);
for(int a = 1; a < i-a; ++a){
int b = i-a;
rep(x, poly::N) tmp[x] += ((__int128)g[a][x]) * g[b][x];
}
rep(j, poly::N) tmp[j] *= 2;
if(i % 2 == 0){
int a = i/2;
rep(x, poly::N) tmp[x] += ((__int128)g[a][x]) * g[a][x];
}
vi f(poly::N);
rep(j, poly::N) f[j] = (int)(tmp[j] % Mod);
poly::dft(f, 1);
//rep(j, 8) cout << (int)f[j] << " ";
//cout << "\n";
for(int c = 0; c <= C2[i]; ++c){
umul(f[c], fact[c]), umul(f[c], fact[C2[i] - c - 1]);
sum[i][c + 1] = add(sum[i][c], f[c]);
}
int all = sum[i][C2[i] + 1];
//cout << i << ": " << all << endl;
cout << mul(mul(all, mul(fact[i], inv[2])), invfact[C2[i]]) % Mod << "\n";
g[i].resize(poly::N);
rep(c, C2[i] + 1){
g[i][c] = sum[i][c];
umul(g[i][c], invfact[c]);
umul(g[i][c], invfact[C2[i] - c]);
}
poly::dft(g[i]);
}
cerr << 1. * clock() / CLOCKS_PER_SEC << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 27ms
memory: 11596kb
input:
10 998244353
output:
1 1 1 532396989 328786831 443364983 567813846 34567523 466373946 474334062
result:
wrong answer 3rd numbers differ - expected: '532396989', found: '1'