Submit Info #58804

Problem Lang User Status Time Memory
Partition Function cpp Kanten4205 AC 1945 ms 9.18 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1879 ms 4.48 MiB
100000_00 AC 1884 ms 5.07 MiB
10000_00 AC 1874 ms 4.59 MiB
1000_00 AC 1895 ms 4.43 MiB
100_00 AC 1871 ms 4.43 MiB
1_00 AC 1884 ms 4.39 MiB
200000_00 AC 1905 ms 6.34 MiB
300000_00 AC 1881 ms 7.30 MiB
400000_00 AC 1893 ms 8.18 MiB
500000_00 AC 1945 ms 9.18 MiB
example_00 AC 1870 ms 4.43 MiB

#include <bits/stdc++.h> using namespace std; const long long MOD1 = 1000000007; const long long MOD2 = 998244353; typedef long long ll; typedef pair<long long, long long> P; const long long INF = 1e9; template <typename T> const int MAX = 510000; vector<ll>part(500001); void init_rt() { part[0] = 1; for (ll i = 1; i < 500001; i++) { for (ll j = 1, sign = 1; i - (j * j * 3 - j) / 2 >= 0; ++j, sign *= -1) { part[i] += part[i-(j*j*3-j)/2] % MOD2 * sign; part[i] %= MOD2; if (i-(j*j*3+j)/2 >= 0) part[i] += part[i-(j*j*3+j)/2] % MOD2 * sign; part[i] %= MOD2; if (part[i] < 0) { while (part[i] < 0) part[i] += MOD2; } } } } ll partition_root(ll N) { return part[N]; } int main() { init_rt(); ll N; cin >> N; for (ll i = 0; i <= N; i++) { if (i != 0) cout << ' '; cout << partition_root(i); } }