結果
問題 |
No.3172 三角関数べき乗のフーリエ級数展開
|
ユーザー |
|
提出日時 | 2025-06-13 17:33:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 2,260 bytes |
コンパイル時間 | 2,480 ms |
コンパイル使用メモリ | 217,400 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-13 17:33:21 |
合計ジャッジ時間 | 3,183 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int int64_t template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define pi pair<int, int> #define vi vector<int> #define pb push_back #define all(x) (x).begin(), (x).end() template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &x : v) in >> x; return in; } template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) { for (const auto &x : v) out << x << ' '; return out; } template <typename T1, typename T2> istream &operator>>(istream &in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; } template <typename T1, typename T2> ostream &operator<<(ostream &out, const pair<T1, T2> &p) { out << p.first << ' ' << p.second; return out; } const int MOD = 998244353; const int N = 200001; int factorial[N], invfactorial[N]; int power(int a, int b) { int res = 1; a %= MOD; while (b > 0) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res; } void fill_factorial() { factorial[0] = 1; for (int i = 1; i < N; i++) factorial[i] = (factorial[i - 1] * i) % MOD; invfactorial[N - 1] = power(factorial[N - 1], MOD - 2) % MOD; for (int i = N - 1; i > 0; i--) invfactorial[i - 1] = (invfactorial[i] * i) % MOD; invfactorial[0] = 1; } int nCr(int n, int r) { int ans = factorial[n]; ans = (ans * invfactorial[r]) % MOD; ans = (ans * invfactorial[n - r]) % MOD; return ans; } void solve() { fill_factorial(); int n; cin >> n; for (int i = 0; i <= n; i++) { if (n % 2 == i % 2 && i == 0) cout << nCr(n, n / 2) % MOD << " "; else if ((n - i) % 2 == 0) cout << (nCr(n, (n + i) / 2) + nCr(n, (n - i) / 2)) % MOD << " "; else cout << "0 "; } cout << '\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; while (t--) solve(); return 0; }