結果
問題 |
No.3202 Periodic Alternating Subsequence
|
ユーザー |
|
提出日時 | 2025-07-11 22:28:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 413 ms / 2,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 3,548 ms |
コンパイル使用メモリ | 289,688 KB |
実行使用メモリ | 36,304 KB |
最終ジャッジ日時 | 2025-07-11 22:28:48 |
合計ジャッジ時間 | 12,246 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll =long long; #include<atcoder/modint> using namespace atcoder; using mint=modint1000000007; using vm=vector<mint>; using vvm=vector<vm>; vvm M1={ {1,0,0,0,0,0,0}, {1,1,0,0,0,0,1}, {0,0,1,0,0,0,0}, {1,0,1,1,0,0,1}, {0,0,0,0,1,0,0}, {1,0,2,0,1,1,1}, {0,0,0,0,0,0,1} }; vvm M0={ {1,1,0,0,0,0,1}, {0,1,0,0,0,0,0}, {0,1,1,1,0,0,1}, {0,0,0,1,0,0,0}, {0,1,0,2,1,1,1}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; vvm E={ {1,0,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,1,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; vvm mul(vvm A,vvm B){ ll n=A.size(); vvm C(n,vm(n,0)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ C[i][j]+=A[i][k]*B[k][j]; } } } return C; } const ll INF=1e15; void solve(){ string T; cin>>T; ll N=T.size(),K; cin>>K; vector<vector<mint>> cum(N+1,vector<mint>(2,0)),sum(N+1,vector<mint>(2,0)),dum(N+1,vector<mint>(2,0)); vvm D=E; for(int i=0;i<N;i++){ if(T[i]=='1')D=mul(M1,D); else D=mul(M0,D); } vvm AN=E; while(K>0){ if(K%2){ AN=mul(AN,D); } K/=2; D=mul(D,D); } cout<<(AN[5][6]+AN[4][6]).val()<<endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; // cin>>T; while(T--)solve(); }