結果
問題 | No.1879 How many matchings? |
ユーザー | serufe_ni |
提出日時 | 2022-03-22 20:42:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,338 bytes |
コンパイル時間 | 1,695 ms |
コンパイル使用メモリ | 175,156 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-10 14:57:02 |
合計ジャッジ時間 | 2,353 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define REP(i,m,n) for(int i=(m);i<(n);i++) #define rep(i,n) REP(i,0,n) #define int long long typedef vector<vector<ll> > mat; const int mod = 1000000007; int n; int martxB[2][2] = {1, 1, 1, 0}; int martxA[2] = {1, 1}; int ans[2]; typedef vector<ll> vec; mat mul(mat &A,mat &B){ mat C(A.size(),vec(B[0].size())); rep(i,A.size()){ rep(j,B[0].size()){ rep(k,B.size()){ C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%mod)%mod; } } } return C; } mat pow(mat A,ll k){ mat B(A.size(),vec(A.size())); rep(i,A.size())B[i][i]=1; while(k>0){ if(k&1)B=mul(B,A); A=mul(A,A); k>>=1; } return B; } void multiply(int x[][2], int y[][2]) { int res[2][2]; memset(res, 0, sizeof res); for (int i = 0; i < 2; i ++) { for (int j = 0; j < 2; j ++) { for (int k = 0; k < 2; k ++) { res[i][j] = (x[i][k] * y[k][j] + res[i][j]) % mod; } } } memcpy(x,res,sizeof res); } void Qpow(int x[][2], int k) { int res[2][2]; memset(res, 0, sizeof res); for (int i = 0; i < 2; i ++) { res[i][i] = 1; } while (k) { if (k % 2) { multiply(res, x); } multiply(x, x); k /= 2; } memcpy(x, res, sizeof res); } signed main () { cin >> n; if (n <= 2) { cout << 1; return 0; } if(n%2){ vector<vector<ll> >k(4,vector<ll>(4)); k[0][0]=2,k[0][1]=1,k[0][2]=-2,k[0][3]=-1; rep(j,3){ k[j+1][j]=1; } vector<ll>a(4); a[0]=15; a[1]=7; a[2]=3; a[3]=1; ll ans=0; if(n/2>=4){ auto c=pow(k,n/2-3); rep(j,4){ ans=(ans+a[j]*c[0][j]%mod)%mod; } if(ans<0)ans+=mod; }else{ ans=a[3-n/2]; } cout<<ans<<endl; return 0; } Qpow(martxB, n / 2 - 1); for (int i = 0; i < 2; i ++) { for (int k =0; k < 2; k ++) { ans[i] = (ans[i] + martxB[i][k] * martxA[k] % mod ) % mod; } } cout << ans[0] << endl; }