Submit Info #244

Problem Lang User Status Time Memory
Partition Function cpp hos AC 368 ms 9.03 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.71 MiB
100000_00 AC 30 ms 2.30 MiB
10000_00 AC 4 ms 0.68 MiB
1000_00 AC 1 ms 0.67 MiB
100_00 AC 1 ms 0.60 MiB
1_00 AC 0 ms 0.67 MiB
200000_00 AC 88 ms 3.92 MiB
300000_00 AC 162 ms 5.67 MiB
400000_00 AC 261 ms 7.34 MiB
500000_00 AC 368 ms 9.03 MiB
example_00 AC 1 ms 0.67 MiB

#include <stdio.h> using Int = long long; constexpr Int MO = 998244353; constexpr int LIM = 500010; /* 1 / (\sum_k (X^(6k^2+k) - X^(6k^2+5k+1) - X^(6k^2+7k+2) + X^(6k^2+11k+5))) */ Int partition[LIM]; void preparePartition(int lim) { partition[0] = 1; for (int n = 1; n < lim; ++n) { Int sum = 0; for (int k = 0, m = n - 1; ; ++k) { sum += partition[m]; if ((m -= 2 * k + 1) < 0) break; sum += partition[m]; if ((m -= 4 * k + 3) < 0) break; sum -= partition[m]; if ((m -= 2 * k + 2) < 0) break; sum -= partition[m]; if ((m -= 4 * k + 5) < 0) break; } if ((sum %= MO) < 0) sum += MO; partition[n] = sum; } } int main() { int N; scanf("%d", &N); preparePartition(N + 1); for (int n = 0; n <= N; ++n) { if (n > 0) printf(" "); printf("%lld", partition[n]); } puts(""); return 0; }