結果
問題 | No.492 IOI数列 |
ユーザー |
|
提出日時 | 2017-03-10 23:14:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 942 bytes |
コンパイル時間 | 780 ms |
コンパイル使用メモリ | 79,984 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 08:34:47 |
合計ジャッジ時間 | 1,494 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream> #include <map> #include <vector> #define int long long #define MOD 1000000007 using namespace std; typedef vector<int> vec; typedef vector<vec> mat; mat mul(mat &A,mat &B){ mat C(A.size(),vec(B.size())); for(int i = 0;i < A.size();i++){ for(int k = 0;k < B.size();k++){ for(int j = 0;j < B[0].size();j++){ C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } mat pow(mat A,int n){ mat B(A.size(),vec(A.size())); for(int i = 0;i < A.size();i++){ B[i][i] = 1; } while(n > 0){ if(n & 1) B = mul(B,A); A = mul(A,A); n >>= 1; } return B; } signed main(){ int n,cnt = 1; cin >> n; mat A(2,vec(2)),tmp(2,vec(2)); A[0][0] = 100; A[0][1] = 1; A[1][0] = 0; A[1][1] = 1; tmp = pow(A,n - 1); cout << (tmp[0][0] + tmp[0][1]) % MOD << endl; n %= 11; if(n == 0) cout << 0; else for(int i = 0;i < n;i++){ if(i == 0) cout << 1; else cout << "01"; } cout << endl; return 0; }