結果

問題 No.3202 Periodic Alternating Subsequence
ユーザー askr58
提出日時 2025-07-11 22:07:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 241 ms / 2,000 ms
コード長 1,183 bytes
コンパイル時間 3,657 ms
コンパイル使用メモリ 289,584 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 22:08:11
合計ジャッジ時間 9,352 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include <atcoder/modint>
using mint=atcoder::modint1000000007;
int main(){
	string s;
	cin>>s;
	ll k;
	cin>>k;
	vector<vector<vector<mint>>> mat(2,vector<vector<mint>>(6,vector<mint>(6)));
	for(int i=0;i<6;i++){
		mat[0][i][i]=1;
		mat[1][i][i]=1;
	}
	mat[0][0][3]=1;mat[0][1][3]=1;mat[0][1][4]=1;mat[0][2][3]=1;mat[0][2][4]=2;mat[0][2][5]=1;
	mat[1][3][0]=1;mat[1][4][0]=1;mat[1][4][1]=1;mat[1][5][0]=1;mat[1][5][1]=2;mat[1][5][2]=1;
	vector<vector<mint>> t(6,vector<mint>(6));
	for(int i=0;i<6;i++)t[i][i]=1;
	auto prod=[](vector<vector<mint>> x,vector<vector<mint>> y)->vector<vector<mint>>{
		vector<vector<mint>> res(6,vector<mint>(6));
		for(int i=0;i<6;i++)for(int j=0;j<6;j++)for(int k=0;k<6;k++){
			res[i][j]+=x[i][k]*y[k][j];
		}
		return res;
	
	};
	int n=s.size();
	for(int i=0;i<n;i++)t=prod(mat[s[i]-'0'],t);
	vector<vector<mint>> res(6,vector<mint>(6));
	for(int i=0;i<6;i++)res[i][i]=1;
	while(k>0){
		if(k&1){
			res=prod(t,res);
		}
		t=prod(t,t);
		k>>=1;
	}
	vector<mint> v(6);
	for(int i=0;i<6;i++)for(int j=0;j<6;j++)v[i]+=res[i][j];
	cout<<(v[2]-2*v[1]+v[0]+v[5]-2*v[4]+v[3]).val()<<endl;
}
0