結果
問題 | No.2883 K-powered Sum of Fibonacci |
ユーザー | Ryuhei Mori |
提出日時 | 2024-09-24 23:25:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 3,000 ms |
コード長 | 3,231 bytes |
コンパイル時間 | 2,212 ms |
コンパイル使用メモリ | 80,020 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 23:25:08 |
合計ジャッジ時間 | 2,916 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 4 ms
6,944 KB |
testcase_12 | AC | 3 ms
6,940 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,944 KB |
testcase_15 | AC | 4 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 3 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 3 ms
6,940 KB |
testcase_20 | AC | 5 ms
6,944 KB |
testcase_21 | AC | 5 ms
6,940 KB |
testcase_22 | AC | 5 ms
6,940 KB |
testcase_23 | AC | 5 ms
6,940 KB |
testcase_24 | AC | 5 ms
6,944 KB |
testcase_25 | AC | 5 ms
6,940 KB |
testcase_26 | AC | 5 ms
6,944 KB |
testcase_27 | AC | 5 ms
6,940 KB |
testcase_28 | AC | 5 ms
6,944 KB |
testcase_29 | AC | 5 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 2 ms
6,944 KB |
testcase_33 | AC | 2 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,940 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,940 KB |
testcase_38 | AC | 2 ms
6,944 KB |
testcase_39 | AC | 2 ms
6,944 KB |
testcase_40 | AC | 2 ms
6,940 KB |
testcase_41 | AC | 2 ms
6,944 KB |
testcase_42 | AC | 5 ms
6,940 KB |
ソースコード
#include <iostream> #include <vector> using i32 = int; using u32 = unsigned; using i64 = long long; using u64 = unsigned long long; template <i32 MOD> struct Mint { i32 n; constexpr Mint(i32 n = 0): n(n) {} constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); } constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; } constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; } constexpr Mint &operator*=(const Mint &rhs){ n = (i64) n * rhs.n % MOD; return *this; } constexpr Mint inv() const { i32 x = MOD; i32 y = n; i32 b = 0, d = 1; while(y){ i32 q = x / y; x = x % y; b -= q * d; std::swap(x, y); std::swap(b, d); } if(b < 0) b += MOD; return b; } constexpr Mint &operator/=(const Mint &rhs){ n = (i64) n * rhs.inv().n % MOD; return *this; } friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; } friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; } friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; } friend constexpr Mint operator/(const Mint &lhs, const Mint &rhs){ return Mint(lhs) /= rhs; } friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; } friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; } friend std::ostream &operator<<(std::ostream &os, const Mint &rhs){ return os << rhs.n; } }; template <class T> T modpow(T x, int n){ T r(1); for(; n; n >>= 1){ if(n&1) r *= x; x *= x; } return r; } constexpr u32 mod = 998244353; using mint = Mint<mod>; using poly = std::vector<mint>; poly mult(const poly &lhs, const poly &rhs){ poly r(lhs.size() + rhs.size() - 1); for(u32 i = 0; i < lhs.size(); i++){ for(u32 j = 0; j < rhs.size(); j++){ r[i+j] += lhs[i] * rhs[j]; } } return r; } void printv(const poly a){ for(u32 i = 0; i < a.size(); i++) std::cout << a[i] << ' '; std::cout << std::endl; } poly denom(u32 k, mint e1, mint e2){ std::vector<mint> fib(k+2); fib[0] = 0; fib[1] = 1; for(u32 i = 2; i < fib.size(); i++) fib[i] = e1 * fib[i-1] - e2 * fib[i-2]; poly den(k+2); den[0] = 1; mint c = 1; for(u32 i = 1; i < den.size(); i++, c *= e2) den[i] = -c * den[i-1] * fib[k+2-i] / fib[i]; den = mult(den, { 1, mod-1 }); return den; } int main(){ u64 n; u32 k; std::cin >> n >> k; std::vector<mint> fib(k+2); fib[0] = 0; fib[1] = 1; for(u32 i = 2; i < fib.size(); i++) fib[i] = fib[i-1] + fib[i-2]; poly den = denom(k, 1, mod-1); poly num(k+2); for(u32 i = 1; i < num.size(); i++) num[i] = num[i-1] + modpow(fib[i], k); num = mult(num, den); num.resize(k+2); mint e1 = 1; mint e2 = mod-1; for(;n; n>>=1){ poly dem = den; for(u32 i = 1; i < dem.size(); i += 2) dem[i] = -dem[i]; num = mult(num, dem); for(u32 i = n&1; i < num.size(); i += 2) num[i/2] = num[i]; num.resize(num.size()/2); e1 = e1 * e1 - 2*e2; e2 = e2 * e2; den = denom(k, e1, e2); } std::cout << num[0] << std::endl; return 0; }