結果

問題 No.3172 三角関数べき乗のフーリエ級数展開
ユーザー 回転
提出日時 2025-06-06 21:43:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 1,742 bytes
コンパイル時間 3,118 ms
コンパイル使用メモリ 273,280 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-06 21:43:06
合計ジャッジ時間 4,669 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
#https://oeis.org/A273496
import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")

import sys
sys.setrecursionlimit(10**6)
MOD = 998244353
N = int(input())

memo = [-1 for _ in range(2*10**5+1)]
def a(n):
    if(n == 0):return 1
    if(memo[n] != -1):return memo[n]
    memo[n] = n * a(n-1) % MOD
    return n * a(n-1) % MOD

def nCr(n,r):
    return a(n) * pow(a(n-r),-1,MOD) * pow(a(r),-1,MOD) % MOD

def f(n,k):
    if((n-k)%2 == 1):return 0
    if(k == 0 and n%2 == 0):return nCr(n,n//2)
    return 2*nCr(n,(n-k)//2)

for k in range(N+1):
    print(f(N,k),end=" ")
print()
*/

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int MOD = 998244353;
const int MAXN = 2 * 100000 + 1;

vector<ll> fact(MAXN, -1);

// 階乗をMODで前計算（メモ化）
ll a(int n) {
    if (n == 0) return 1;
    if (fact[n] != -1) return fact[n];
    return fact[n] = n * a(n - 1) % MOD;
}

// modpow: a^b % MOD を高速に求める
ll modpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 逆元を使ったnCr
ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return a(n) * modpow(a(n - r), MOD - 2, MOD) % MOD * modpow(a(r), MOD - 2, MOD) % MOD;
}

ll f(int n, int k) {
    if ((n - k) % 2 == 1) return 0;
    if (k == 0 && n % 2 == 0) return nCr(n, n / 2);
    return 2 * nCr(n, (n - k) / 2) % MOD;
}

int main() {
    int N;
    cin >> N;
    fact[0] = 1;
    for (int i = 1; i <= 2 * 100000; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    for (int k = 0; k <= N; ++k) {
        cout << f(N, k) << " ";
    }
    cout << endl;

    return 0;
}
0