結果
問題 | No.2514 Twelvefold Way Returns |
ユーザー |
|
提出日時 | 2023-10-20 23:19:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 3,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 3,878 ms |
コンパイル使用メモリ | 255,456 KB |
最終ジャッジ日時 | 2025-02-17 11:02:14 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct Fast {Fast() {std::cin.tie(nullptr);ios::sync_with_stdio(false);cout << setprecision(10);}} fast;#define all(a) (a).begin(), (a).end()#define contains(a, x) ((a).find(x) != (a).end())#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define writejoin(s, a) rep(_i, 0, (a).size()) cout << (a)[_i] << (_i + 1 < (int)(a).size() ? s : "\n");#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";#define yn(b) cout << ((b) ? "yes" : "no") << "\n";using ll = long long;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using mint = modint998244353;using vm = vector<mint>;template <typename mint>class Factorial {public:Factorial(int max) : n(max) {f = std::vector<mint>(n + 1);finv = std::vector<mint>(n + 1);f[0] = 1;for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;finv[n] = f[n].inv();for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * i;}mint fact(int k) const {assert(0 <= k && k <= n);return f[k];}mint fact_inv(int k) const {assert(0 <= k && k <= n);return finv[k];}mint binom(int k, int r) const {assert(0 <= k && k <= n);if (r < 0 || r > k) return 0;return f[k] * finv[r] * finv[k - r];}mint inv(int k) const {assert(0 < k && k <= n);return finv[k] * f[k - 1];}private:int n;std::vector<mint> f, finv;};using ar = array<mint, 3>;ar mul(ar a, ar b) {ar r{0, 0, 0};rep(i, 0, 3) rep(j, 0, 3) r[(i + j) % 3] += a[i] * b[j];return r;}ar pow(ar a, int n) {ar r{1, 0, 0};while (n) {if (n & 1) r = mul(r, a);a = mul(a, a);n /= 2;}return r;}void solve() {int n, m;cin >> n >> m;Factorial<mint> fact(m);mint ans = 0;rep(a, 0, m + 1) rep(b, 0, m + 1 - a) {int c = m - a - b;ar v{0, 0, 0};int d = (2 * b + c) % 3;v[d] = fact.fact_inv(a) * fact.fact_inv(b) * fact.fact_inv(c);v = mul(v, pow(ar{a, b, c}, n));ans += v[0] - v[2];}ans *= fact.fact(m);ans /= mint(3).pow(m);cout << ans.val() << endl;}int main() {int t = 1;// cin >> t;while (t--) solve();}