Submit Info #11284

Problem Lang User Status Time Memory
Partition Function cpp koosaga AC 694 ms 9.17 MiB

ケース詳細
Name Status Time Memory
0_00 AC 666 ms 4.55 MiB
100000_00 AC 672 ms 5.50 MiB
10000_00 AC 666 ms 4.54 MiB
1000_00 AC 661 ms 4.49 MiB
100_00 AC 665 ms 4.42 MiB
1_00 AC 660 ms 4.55 MiB
200000_00 AC 679 ms 6.42 MiB
300000_00 AC 685 ms 7.36 MiB
400000_00 AC 691 ms 8.30 MiB
500000_00 AC 694 ms 9.17 MiB
example_00 AC 664 ms 4.42 MiB

#include<bits/stdc++.h> using namespace std; const int MAXN = 500005; const int MOD = 998244353; using lint = long long; int main(){ int n; cin >> n; vector<pair<int, int>> gp; lint P[MAXN+1] = {}; gp.emplace_back(0, 0); for(int i = 1; gp.back().second <= MAXN; i++) { gp.emplace_back(i % 2 ? 1 : -1, i * (3*i - 1) / 2); gp.emplace_back(i % 2 ? 1 : -1, i * (3*i + 1) / 2); } P[1] = 1; for(int n = 2; n <= MAXN; n++) { for(auto it : gp) if(n >= it.second) P[n] += P[n - it.second] * it.first + MOD; P[n] %= MOD; } for(int i=0; i<=n; i++) printf("%lld ", P[i+1]); }