結果
問題 | No.2514 Twelvefold Way Returns |
ユーザー |
![]() |
提出日時 | 2023-10-20 22:37:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 3,000 ms |
コード長 | 1,826 bytes |
コンパイル時間 | 2,012 ms |
コンパイル使用メモリ | 200,140 KB |
最終ジャッジ日時 | 2025-02-17 10:19:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; const long long ONE_THIRD = 332748118; array<long long, 3> operator +(array<long long, 3> A, array<long long, 3> B){ array<long long, 3> C = {}; for (int i = 0; i < 3; i++){ C[i] = (A[i] + B[i]) % MOD; } return C; } array<long long, 3> operator *(array<long long, 3> A, long long k){ for (int i = 0; i < 3; i++){ A[i] *= k; A[i] %= MOD; } return A; } array<long long, 3> operator *(array<long long, 3> A, array<long long, 3> B){ array<long long, 3> C = {}; for (int i = 0; i < 3; i++){ for (int j = 0; j < 3; j++){ int k = (i + j) % 3; C[k] += A[i] * B[j]; C[k] %= MOD; } } return C; } array<long long, 3> pow(array<long long, 3> A, int N){ array<long long, 3> ans = {1, 0, 0}; while (N > 0){ if (N % 2 == 1){ ans = ans * A; } A = A * A; N /= 2; } return ans; } array<long long, 3> shift(array<long long, 3> A, int N){ array<long long, 3> B = {}; for (int i = 0; i < 3; i++){ B[(i + N) % 3] = A[i]; } return B; } int main(){ int N, M; cin >> N >> M; vector<vector<long long>> binom(M + 1, vector<long long>(M + 1, 0)); for (int i = 0; i <= M; i++){ binom[i][0] = 1; for (int j = 1; j < i; j++){ binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD; } binom[i][i] = 1; } array<long long, 3> ans = {}; for (int i = 0; i <= M; i++){ for (int j = 0; i + j <= M; j++){ int k = M - i - j; long long c = binom[M][i] * binom[M - i][j] % MOD; array<long long, 3> x = {i, j, k}; ans = ans + shift(pow(x, N), j * 2 + k) * c; } } long long ans2 = (ans[0] - ans[1] + MOD) % MOD; for (int i = 0; i < M; i++){ ans2 *= ONE_THIRD; ans2 %= MOD; } cout << ans2 << endl; }