結果
問題 | No.2883 K-powered Sum of Fibonacci |
ユーザー | SnowBeenDiding |
提出日時 | 2024-09-09 04:53:44 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,827 bytes |
コンパイル時間 | 5,462 ms |
コンパイル使用メモリ | 313,408 KB |
実行使用メモリ | 42,564 KB |
最終ジャッジ日時 | 2024-09-09 04:53:54 |
合計ジャッジ時間 | 9,591 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
42,328 KB |
testcase_01 | WA | - |
testcase_02 | AC | 58 ms
42,404 KB |
testcase_03 | AC | 59 ms
42,292 KB |
testcase_04 | WA | - |
testcase_05 | AC | 58 ms
42,376 KB |
testcase_06 | AC | 59 ms
42,384 KB |
testcase_07 | AC | 66 ms
42,284 KB |
testcase_08 | AC | 58 ms
42,292 KB |
testcase_09 | AC | 58 ms
42,248 KB |
testcase_10 | WA | - |
testcase_11 | AC | 57 ms
42,296 KB |
testcase_12 | AC | 56 ms
42,224 KB |
testcase_13 | WA | - |
testcase_14 | AC | 58 ms
42,272 KB |
testcase_15 | AC | 58 ms
42,248 KB |
testcase_16 | AC | 58 ms
42,448 KB |
testcase_17 | AC | 58 ms
42,216 KB |
testcase_18 | AC | 58 ms
42,220 KB |
testcase_19 | WA | - |
testcase_20 | AC | 57 ms
42,440 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 58 ms
42,424 KB |
testcase_28 | AC | 58 ms
42,224 KB |
testcase_29 | WA | - |
testcase_30 | AC | 58 ms
42,356 KB |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 59 ms
42,284 KB |
testcase_34 | WA | - |
testcase_35 | AC | 58 ms
42,288 KB |
testcase_36 | WA | - |
testcase_37 | AC | 59 ms
42,220 KB |
testcase_38 | WA | - |
testcase_39 | AC | 59 ms
42,292 KB |
testcase_40 | AC | 60 ms
42,220 KB |
testcase_41 | AC | 59 ms
42,284 KB |
testcase_42 | WA | - |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; using mint = modint998244353; struct Comb { vector<mint> fact, ifact; int MAX_COM; Comb() {} Comb(int n) { MAX_COM = n; // ここでMAX入力を調整 init(998244353, MAX_COM); } void init(long long MOD, long long MAX_COM) { int n = MAX_COM; assert(n < MOD); fact = vector<mint>(n + 1); ifact = vector<mint>(n + 1); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i; } mint operator()(long long n, long long k) { if (k < 0 || k > n) return 0; return fact[n] * ifact[k] * ifact[n - k]; } }; Comb comb(5000010); struct root5 { // a + b * sqrt(5) mint a, b; root5(mint a, mint b) : a(a), b(b) {} root5() {} root5 operator+(const root5 &r) const { return root5(a + r.a, b + r.b); } root5 operator-(const root5 &r) const { return root5(a - r.a, b - r.b); } root5 operator*(const root5 &r) const { return root5(a * r.a + mint(5) * b * r.b, a * r.b + b * r.a); } root5 operator*(const int n) const { return root5(a * n, b * n); } root5 operator/(const root5 &r) const { mint d = r.a * r.a - mint(5) * r.b * r.b; mint x = a * r.a + mint(5) * b * r.b; mint y = a * r.b - b * r.a; x = x / d; y = y / d; return root5(x, y); } root5 operator/(const int n) const { mint x = a / n; mint y = b / n; return root5(x, y); } root5 pow(ll n) { root5 x = *this; root5 res = root5(1, 0); while (n) { if (n & 1) res = res * x; x = x * x; n >>= 1; } return res; } }; void solve(ll n, int k) { root5 ans = root5(0, 0); root5 a = root5((mint)1 / 2, (mint)1 / 2); root5 b = root5((mint)1 / 2, (mint)-1 / 2); root5 one = root5(1, 0); rep(i, 0, k + 1) { root5 p(1, 0); p = p * comb(k, i).val(); if (i % 2) p = p * -1; root5 x = a.pow(k - i) * b.pow(i); if (x.a.val() == 1 && x.b.val() == 0) { ans = ans + root5(n, 0) * p; } else { ans = ans + p * (x.pow(n + 1) - x) / (one - x); } } root5 ka = root5(0, (mint)1); ka = ka.pow(k); ans = ans * ka; ans = ans / pow_mod(5, k, 998244353); cout << ans.a.val() << endl; return; } int main() { // rep(i, 1, 10) { solve(i, 3); } ll n; int k; cin >> n >> k; solve(n, k); }