結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:56:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,628 bytes |
コンパイル時間 | 2,868 ms |
コンパイル使用メモリ | 198,892 KB |
最終ジャッジ日時 | 2025-01-10 22:30:50 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define srep(i,s,t) for (int i = s; i < t; ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)using namespace std;typedef long long int ll;typedef pair<int,int> P;#define yn {puts("Yes");}else{puts("No");}#define MAX_N 200005const ll MOD = 1000000007;// DPの更新vector<ll> matmul(vector<ll> &dp, vector<vector<ll>> &mt, int m){vector<ll> ret(m,0);rep(i,m){rep(j,m){ret[i] += mt[i][j] * dp[j] % MOD;ret[i] %= MOD;}}return ret;}// 遷移行列の更新vector<vector<ll>> update_matmul(vector<vector<ll>> &mt, int m){vector<vector<ll>> ret(m, vector<ll>(m,0));rep(i,m){rep(j,m){rep(k,m){ret[i][j] += mt[i][k] * mt[k][j] % MOD;ret[i][j] %= MOD;}}}return ret;}void matpow(vector<ll> &dp, vector<vector<ll>> &mt, int m, ll k){while(k){if(k & 1) dp = matmul(dp, mt, m);mt = update_matmul(mt, m);k /= 2;}}// ax + by = gcd(a, b) となるような (x, y) を求める// 多くの場合 a と b は互いに素として ax + by = 1 となる (x, y) を求めるlong long extGCD(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1;y = 0;return a;}long long d = extGCD(b, a%b, y, x); // 再帰的に解くy -= a / b * x;return d;}// 負の数にも対応した mod (a = -11 とかでも OK)inline long long mod(long long a, long long m) {return (a % m + m) % m;}// 逆元計算 (ここでは a と m が互いに素であることが必要)long long modinv(long long a, long long m) {long long x, y;extGCD(a, m, x, y);return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので}int main() {ll n;cin >> n;// ll MOD = 1e9+7;ll m, k;m = 6;k = n;vector<ll> dp(m);rep(i,m) dp[i] = 0;dp[0] = 1;srep(i,1,6){ll tmp = 0;rep(j,i){tmp += dp[j];}dp[i] = tmp % MOD * modinv(6, MOD) % MOD;}vector<vector<ll>> mt(m,vector<ll>(m));rep(i,m)rep(j,m)mt[i][j] = 0;/*適宜行列mtに値を入れる.*/rep(i,6){rep(j,6){if(i == 5){mt[i][j] = modinv(6, MOD);}else{if(j == i+1)mt[i][j] = 1;}}}matpow(dp, mt, m, k);ll ans = dp[0];cout << ans << endl;return 0;}