Submit Info #27177

Problem Lang User Status Time Memory
Partition Function cpp Jeffrey AC 734 ms 7.30 MiB

ケース詳細
Name Status Time Memory
0_00 AC 3 ms 2.55 MiB
100000_00 AC 67 ms 3.55 MiB
10000_00 AC 5 ms 2.62 MiB
1000_00 AC 3 ms 2.62 MiB
100_00 AC 0 ms 2.49 MiB
1_00 AC 2 ms 2.56 MiB
200000_00 AC 182 ms 4.48 MiB
300000_00 AC 330 ms 5.42 MiB
400000_00 AC 512 ms 6.30 MiB
500000_00 AC 734 ms 7.30 MiB
example_00 AC 2 ms 2.55 MiB

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int mod = 1000000007; int main() { ios::sync_with_stdio(false); int n, p[500005] = {1, 1}, q[1200] = {}; for (int i = 1; i < 600; i++) { q[i + i - 1] = (3 * i * i - i) / 2; q[i + i] = (3 * i * i + i) / 2; } cin >> n; for (int i = 2; i <= n; i++) { for (int j = 1; q[j] <= i; j++) { if (j % 4 == 1 || j % 4 == 2) { p[i] += p[i - q[j]]; if (p[i] >= 998244353) p[i] -= 998244353; } else { p[i] -= p[i - q[j]]; if (p[i] < 0) p[i] += 998244353; } } } for (int i = 0; i <= n; i++) cout << p[i] << ' '; }