Submit Info #204

Problem Lang User Status Time Memory
Partition Function cpp14 (anonymous) AC 244 ms 7.26 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.72 MiB
100000_00 AC 31 ms 1.91 MiB
10000_00 AC 4 ms 0.80 MiB
1000_00 AC 1 ms 0.68 MiB
100_00 AC 2 ms 0.67 MiB
1_00 AC 1 ms 0.67 MiB
200000_00 AC 68 ms 3.28 MiB
300000_00 AC 120 ms 4.65 MiB
400000_00 AC 177 ms 5.89 MiB
500000_00 AC 244 ms 7.26 MiB
example_00 AC 1 ms 0.68 MiB

#include <cstdio> #include <cassert> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <functional> #include <stack> #include <queue> #include <tuple> #define getchar getchar_unlocked #define putchar putchar_unlocked #define _rep(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) using namespace std; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f80 = long double; int get_int() { int n, c, sign = 0; while ((c = getchar()) < '-'); if (c == '-') sign = 1, n = 0; else n = c - '0'; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return sign ? -n : n; } void put_int(int n) { if (n < 0) putchar('-'), n = -n; int res[11], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); } __attribute__((optimize("O3"), target("avx"))) vector<int> partition_table_mod(int N, int mod) { vector<int> dp(N + 1), poly(N + 1); dp[0] = poly[0] = 1 % mod; if (N <= 0) return dp; auto add_mod = [&] (int a, int b) { return (a += b - mod) < 0 ? a + mod : a; }; const int v = sqrt(2 * N); for (int i = 1; i <= N / v; ++i) { const int t = i * v; for (int j = i; j < t; ++j) poly[j] = add_mod(poly[j], poly[j - i]); for (int j = t; j <= N; ++j) { poly[j] = add_mod(poly[j], poly[j - i]); dp[j] = add_mod(dp[j], poly[j - t]); } } for (int i = v - 1; i > 0; --i) { for (int j = i; j <= N; ++j) dp[j] = add_mod(dp[j], dp[j - i]); } return dp; } void solve() { int N; while (~scanf("%d", &N)) { auto partitions = partition_table_mod(N, 998244353); for (int i = 0; i <= N; ++i) { put_int(partitions[i]); if (i < N) putchar(' '); } puts(""); } } int main() { clock_t beg = clock(); solve(); clock_t end = clock(); fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC); return 0; }