結果
問題 |
No.3044 よくあるカエルさん
|
ユーザー |
![]() |
提出日時 | 2025-02-28 22:20:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 9,263 bytes |
コンパイル時間 | 6,207 ms |
コンパイル使用メモリ | 332,904 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-02-28 22:20:51 |
合計ジャッジ時間 | 6,473 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) #define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__) #define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__) #define CLR(a, b) memset((a), (b), sizeof(a)) #define DUMP(x) cout << #x << " = " << (x) << endl; #define INF (long long)1001001001001001001 #define inf 1001001000 #define MOD 998244353 #define MOD1 1000000007 #define PI 3.14159265358979 #define epsilon 1e-12 #define fcout cout << fixed << setprecision(12) #define MP make_pair #define PB push_back #define fi first #define se second #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) using ll = long long; using ld = long double; using vi = vector<int>; using vl = vector<long long>; using vs = vector<string>; using vd = vector<double>; using vld = vector<long double>; using vb = vector<bool>; using vpii = vector<pair<int, int>>; using vpll = vector<pair<long long, long long>>; using vvi = vector<vector<int>>; using vvl = vector<vector<long long>>; using vvd = vector<vector<double>>; using vvld = vector<vector<long double>>; using vvb = vector<vector<bool>>; using vvpii = vector<vector<pair<int,int>>>; using vvpll = vector<vector<pair<long long,long long>>>; using vvvi = vector<vector<vector<int>>>; using vvvl = vector<vector<vector<long long>>>; using pii = pair<int, int>; using pll = pair<long long, long long>; using LL = __int128_t; using mint = atcoder::modint998244353; using vmint = vector<mint>; using vvmint = vector<vector<mint>>; using vvvmint = vector<vector<vector<mint>>>; ll gcd(ll x, ll y) {if (x == 0) return y; return gcd(y%x, x);} ll lcm(ll x, ll y) { __int128_t xx,yy; xx=x; yy=y; __int128_t ans=xx * yy / gcd(x, y); ll ans2=ans; return ans2; } template<typename T> T POW(T x, ll n){T ret=1; while(n>0){ if(n&1) ret=ret*x; x=x*x; n>>=1; } return ret;} template<typename T> T modpow(T a, ll n, T p) { if(n==0) return (T)1; if (n == 1) return a % p; if (n % 2 == 1) return (a * modpow(a, n - 1, p)) % p; T t = modpow(a, n / 2, p); return (t * t) % p;} template<typename T> T modinv(T a, T m) { if(m==0)return (T)1; T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u;} ll REM(ll a, ll b){ return (a % b + b) % b;} ll QUO(ll a, ll b){ return (a - REM(a, b)) / b;} /* random_device rd; mt19937 gen(rd()); uniform_int_distribution<> dist1(1, 100); [1,100] int random_value = dist1(gen); */ /* auto start = chrono::steady_clock::now(); //時間計測の開始 auto now = std::chrono::steady_clock::now(); //現在時刻と開始時刻の差を測定 double elapsed = std::chrono::duration<double>(now - start).count(); //時間をdouble型で取得 */ /* const int MAXCOMB=510000; std::vector<mint> FAC(MAXCOMB), FINV(MAXCOMB), INV(MAXCOMB); void COMinit() {FAC[0] = FAC[1] = 1;FINV[0] = FINV[1] = 1;INV[1] = 1;for (int i = 2; i < MAXCOMB; i++) {FAC[i] = FAC[i - 1] * i;INV[i] = mint(0) - INV[mint::mod() % i] * (mint::mod() / i);FINV[i] = FINV[i - 1] * INV[i];}} mint COM(int n, int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return FAC[n] * FINV[k] * FINV[n - k];} */ template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));} template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));} template <class T> T BS(vector<T> &vec, T key) {return lower_bound(vec.begin(), vec.end(), key) - vec.begin();} template<class T> pair<T,T> RangeBS(vector<T> &vec, T lowv, T highv){auto itr_l = lower_bound(vec.begin(), vec.end(), lowv); auto itr_r = upper_bound(vec.begin(), vec.end(), highv); return make_pair(distance(vec.begin(), itr_l), distance(vec.begin(), itr_r)-1);} void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); } void yes() { cout << "Yes\n"; exit(0); } int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1}; bool range_in(int i, int j, int h, int w){ if(i<0 || j<0 || i>=h || j>=w) return false; return true;} int bitcount(int n){n=(n&0x55555555)+(n>>1&0x55555555); n=(n&0x33333333)+(n>>2&0x33333333); n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f); n=(n&0x00ff00ff)+(n>>8&0x00ff00ff); n=(n&0x0000ffff)+(n>>16&0x0000ffff); return n;} template<typename T> struct Edge{ int from, to, index; T cost; Edge() : from(-1), to(-1), index(-1), cost(0) {} Edge(int _to) : from(-1), to(_to), index(-1), cost(0) {} Edge(int _to, T _cost) : from(-1), to(_to), index(-1), cost(_cost) {} Edge(int _from, int _to, int _index) : from(_from), to(_to), index(_index), cost(0) {} Edge(int _from, int _to, int _index, T _cost) : from(_from), to(_to), index(_index), cost(_cost) {} bool operator<(const Edge<T>& other) const { return cost < other.cost; } Edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; using Graph = vector<vector<int>>; template <typename T> using WGraph = vector<vector<Edge<T>>>; ////////////////////////////////////////////////////////////////////////////////////////// template <class T> struct Matrix { vector<vector<T>> A; Matrix() = default; Matrix(int n, int m) : A(n, vector<T>(m, T())) {} Matrix(int n) : A(n, vector<T>(n, T())){}; int H() const { return A.size(); } int W() const { return A[0].size(); } int size() const { return A.size(); } inline const vector<T> &operator[](int k) const { return A[k]; } inline vector<T> &operator[](int k) { return A[k]; } static Matrix I(int n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { int n = H(), m = W(); assert(n == B.H() && m == B.W()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { int n = H(), m = W(); assert(n == B.H() && m == B.W()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { int n = H(), m = B.W(), p = W(); assert(p == B.H()); vector<vector<T> > C(n, vector<T>(m, T{})); for (int i = 0; i < n; i++) for (int k = 0; k < p; k++) for (int j = 0; j < m; j++) C[i][j] += (*this)[i][k] * B[k][j]; A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(H()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } bool operator==(const Matrix &B) const { assert(H() == B.H() && W() == B.W()); for (int i = 0; i < H(); i++) for (int j = 0; j < W(); j++) if (A[i][j] != B[i][j]) return false; return true; } bool operator!=(const Matrix &B) const { assert(H() == B.H() && W() == B.W()); for (int i = 0; i < H(); i++) for (int j = 0; j < W(); j++) if (A[i][j] != B[i][j]) return true; return false; } Matrix inverse() const { assert(H() == W()); Matrix B(H()); B.A = inverse_matrix(A); return B; } friend ostream &operator<<(ostream &os, const Matrix &p) { int n = p.H(), m = p.W(); for (int i = 0; i < n; i++) { os << (i ? " " : "") << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() const { Matrix B(*this); assert(H() == W()); T ret = 1; for (int i = 0; i < H(); i++) { int idx = -1; for (int j = i; j < W(); j++) { if (B[j][i] != 0) { idx = j; break; } } if (idx == -1) return 0; if (i != idx) { ret *= T(-1); swap(B[i], B[idx]); } ret *= B[i][i]; T inv = T(1) / B[i][i]; for (int j = 0; j < W(); j++) { B[i][j] *= inv; } for (int j = i + 1; j < H(); j++) { T a = B[j][i]; if (a == 0) continue; for (int k = i; k < W(); k++) { B[j][k] -= B[i][k] * a; } } } return ret; } }; void solve(){ ll n,t; cin>>n>>t; n--; ll k,l; cin>>k>>l; vmint cnt(3); cnt[0]=k-1; cnt[2] = 7-l; cnt[1]=6-cnt[0]-cnt[2]; Matrix<mint> A(t); A[0][0]=(mint)cnt[0]/6; A[0][1]=(mint)cnt[1]/6; A[0][t-1]=(mint)cnt[2]/6; rep(i,t-1){ A[i+1][i]=1; } Matrix<mint> v(t,1); v[0][0]=1; v = (A^n) * v; cout<<v[0][0].val()<<endl; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int TT; TT = 1; //cin >> TT; while(TT--) solve(); }