結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:51:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 2,168 bytes |
コンパイル時間 | 432 ms |
コンパイル使用メモリ | 52,352 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 08:21:59 |
合計ジャッジ時間 | 2,566 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <cstdio>#include <vector>using std::vector;const int mod = 1e9+7;int f[100005][2];int c[10][10];int a[10][10];int power(int a,int b){int res = 1;while(b){if(b%2) res = res*1ll*a%mod;a = a*1ll*a%mod;b /= 2;}return res;}void mul(int a[10][10],int b[10][10],int n){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){c[i][j] = 0;for(int k = 1; k <= n; k++){int add = a[i][k]*1ll*b[k][j]%mod;c[i][j] += add;if(c[i][j] >= mod) c[i][j] -= mod;}}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++) a[i][j] = c[i][j];}}void power(int a[10][10],int b,int n){int res[10][10];for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i==j) res[i][j] = 1;else res[i][j] = 0;}}while(b){if(b%2) mul(res,a,n);mul(a,a,n);b /= 2;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++) a[i][j] = res[i][j];}}int main(){int T;scanf("%d",&T);while(T--){int n = 3;int m;int d = 1;scanf("%d",&m);int invn = power(n,mod-2);// f[i][j]: can guess i time, now at jf[0][1] = 1;f[0][0] = 0;for(int i = 1; i <= 1; i++){for(int j = 0; j < 2; j++){f[i][j] = 0;if(j){// stayf[i][j] = (f[i][j] + f[i-1][j]*1ll*invn)%mod;// runif(i>=2) f[i][j] = (f[i][j] + f[i-2][0]*1ll*invn%mod*1ll*(n-1)%mod)%mod;}else{// stayf[i][j] = (f[i][j] + f[i-1][j]*1ll*invn)%mod;if(i>=2){f[i][j] = (f[i][j] + f[i-2][0]*1ll*invn%mod*1ll*(n-2)%mod)%mod;f[i][j] = (f[i][j] + f[i-2][1]*1ll*invn%mod*1ll*(1)%mod)%mod;}}}}//printf("%d\n",f[m][1]);vector<long long> aa = {0,0,1,0,0,0,0,1,(n-2)*1ll*invn%mod,invn,invn,0,(n-1)*1ll*invn%mod,0,0,invn,};int tot = 0;for(int i = 1; i <= 4; i++){for(int j = 1; j <= 4; j++) a[i][j] = aa[tot++];}power(a,m-1,4);int ans = 0;vector<int> dp = {-1,f[0][0],f[0][1],f[1][0],f[1][1]};for(int i = 1; i <= 4; i++){int add = dp[i]*1ll*a[4][i]%mod;ans = (ans + add)%mod;}int fail = 1-ans;if(fail < 0) fail += mod;fail = power(fail,d);ans = 1-fail;if(ans < 0) ans += mod;printf("%d\n",ans);}return 0;}