Submit Info #62608

Problem Lang User Status Time Memory
Partition Function cpp-acl cai_lw AC 179 ms 19.38 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.45 MiB
100000_00 AC 40 ms 5.10 MiB
10000_00 AC 5 ms 0.95 MiB
1000_00 AC 1 ms 0.45 MiB
100_00 AC 1 ms 0.45 MiB
1_00 AC 1 ms 0.45 MiB
200000_00 AC 83 ms 9.54 MiB
300000_00 AC 164 ms 17.44 MiB
400000_00 AC 170 ms 18.39 MiB
500000_00 AC 179 ms 19.38 MiB
example_00 AC 1 ms 0.42 MiB

#include <bits/stdc++.h> #include <atcoder/modint> #include <atcoder/convolution> using namespace std; using mint = atcoder::modint998244353; using atcoder::convolution; vector<mint> conv_recip(const vector<mint> &a){ int n=a.size(),n_low=(n+1)/2; if(n==1)return {1/a[0]}; vector<mint> a_low(a.begin(),a.begin()+n_low); vector<mint> b_low=conv_recip(a_low); vector<mint> b=convolution(convolution(b_low,b_low),a); b.resize(n); for(int i=n_low;i<n;i++) b[i]=-b[i]; return b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<mint> coef(n + 1); coef[0] = 1; int k = 1; while (true) { int pent = k * (3 * k - 1) / 2; if (pent > n) break; if (k % 2 == 0) coef[pent] = 1; else coef[pent] = -1; if (k > 0) k = -k; else k = -k + 1; } vector<mint> part = conv_recip(coef); for (int i = 0; i <= n; i++) cout << part[i].val() << (i == n ? '\n' : ' '); }