結果
問題 | No.569 3 x N グリッドのパスの数 |
ユーザー |
|
提出日時 | 2017-06-01 18:08:39 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 231 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 21:40:31 |
合計ジャッジ時間 | 1,868 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include <stdio.h> #define M 12 const int mod = 1000000007; int dp[2][M][M]; const int T[M][M] = { {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1}, }; void mult(const int A[M][M], const int B[M][M], int C[M][M]){ int i, j, k; for(i=0;i<M;i++){ for(j=0;j<M;j++){ long long int tmp = 0; for(k=0;k<M;k++){ tmp = (tmp + (long long int) A[i][k] * B[k][j]) % mod; } C[i][j] = tmp; } } } void modpow(long long int n, int A[2][M][M]){ int i, j; int tmp[2][M][M]; int b = 0; int c = 0; for(i=0;i<M;i++){ for(j=0;j<M;j++){ tmp[0][i][j] = i == j; } } while(n){ if(n&1) mult(tmp[b], A[c], tmp[b^1]), b^=1; mult(A[c], A[c], A[c^1]), c^=1; n /= 2; } for(i=0;i<M;i++){ for(j=0;j<M;j++){ A[0][i][j] = tmp[b][i][j]; } } } int main(){ int i, j; long long int n; scanf("%lld", &n); for(i=0;i<M;i++){ for(j=0;j<M;j++){ dp[0][i][j] = T[i][j]; } } modpow(n+1, dp); printf("%d\n", dp[0][0][M-1]); return 0; }