これは割とすんなり。
https://yukicoder.me/problems/no/1847
問題
整数L,Nと、整数の集合Kが与えられる。
各要素1~NのいずれかからなるL要素の整数列のうち、K中のいずれかの要素xに対しxがちょうどx個連続している箇所があるものを求めよ。
解法
行列累乗で解く。
状態としては下記が考えられる。b>aであるbは同一視してよいことを考えると、状態数はO(max(K)^2)程度である。
- 問題の条件をすでに満たしている
- 満たしていない場合、末尾にaがb個連続している
あとは状態遷移を行列で表現して行列累乗しよう。
ll L; int N,M; int ok[11]; const ll mo=1000000007; const int MAT=151; struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};}; Mat mulmat(Mat& a,Mat& b,int n=MAT) { ll mo2=4*mo*mo; int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) { r.v[x][y] += a.v[x][z]*b.v[z][y]; if(r.v[x][y]>mo2) r.v[x][y] -= mo2; } FOR(x,n) FOR(y,n) r.v[x][y]%=mo; return r; } Mat powmat(ll p,Mat a,int n=MAT) { int i,x,y; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(i,n) r.v[i][i]=1; while(p) { if(p%2) r=mulmat(r,a,n); a=mulmat(a,a,n); p>>=1; } return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>N>>M; FOR(i,M) { cin>>x; ok[x]=1; } Mat A; A.v[140][140]+=N; for(i=1;i<=N;i++) { A.v[i*12+1][0]++; for(j=1;j<=i+1;j++) { for(x=1;x<=N;x++) if(x!=i) { if(j==i&&ok[i]) { A.v[140][i*12+j]++; } else { A.v[x*12+1][i*12+j]++; } } A.v[i*12+min(i+1,j+1)][i*12+j]++; } } A=powmat(L,A); ll ret=A.v[140][0]; for(i=1;i<=N;i++) if(ok[i]) ret+=A.v[i*12+i][0]; cout<<ret%mo<<endl; }
まとめ
とはいえちょっとデバッグに手間取った。