結果
問題 |
No.1241 Eternal Tours
|
ユーザー |
![]() |
提出日時 | 2021-02-21 00:34:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 441 ms / 6,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 112,468 KB |
最終ジャッジ日時 | 2025-01-19 02:51:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <atcoder/modint> #include <atcoder/convolution> #include <iostream> using namespace std; using mint = atcoder::modint998244353; template <typename MODINT> void ntt2d(std::vector<std::vector<MODINT>> &mat) { for (auto &vec : mat) atcoder::internal::butterfly(vec); int h = mat.size(), w = mat[0].size(); for (int j = 0; j < w; j++) { std::vector<MODINT> v(h); for (int i = 0; i < h; i++) v[i] = mat[i][j]; atcoder::internal::butterfly(v); for (int i = 0; i < h; i++) mat[i][j] = v[i]; } } template <typename MODINT> void ntt2dinv(std::vector<std::vector<MODINT>> &mat) { int h = mat.size(), w = mat[0].size(); for (int j = 0; j < w; j++) { std::vector<MODINT> v(h); for (int i = 0; i < h; i++) v[i] = mat[i][j]; atcoder::internal::butterfly_inv(v); for (int i = 0; i < h; i++) mat[i][j] = v[i]; } for (auto &vec : mat) atcoder::internal::butterfly_inv(vec); MODINT ninv = MODINT(h * w).inv(); for (auto &vec : mat) { for (auto &x : vec) { x *= ninv; } } } int main() { int X, Y; long long T; int a, b, c, d; cin >> X >> Y >> T >> a >> b >> c >> d; vector dp(1 << (X + 1), vector<mint>(1 << (Y + 1))); dp[a][b] = 1; dp[(1 << (X + 1)) - a][(1 << (Y + 1)) - b] = 1; dp[(1 << (X + 1)) - a][b] = -1; dp[a][(1 << (Y + 1)) - b] = -1; vector trans(1 << (X + 1), vector<mint>(1 << (Y + 1))); trans[0][0] = trans[0][1] = trans[0][(1 << (Y + 1)) - 1] = trans[1][0] = trans[(1 << (X + 1)) - 1][0] = 1; ntt2d(dp); ntt2d(trans); for (size_t i = 0; i < dp.size(); i++) { for (size_t j = 0; j < dp[i].size(); j++) { dp[i][j] *= trans[i][j].pow(T); } } ntt2dinv(dp); cout << dp[c][d].val() << '\n'; }