Codeforces #554 Div2 F. Neko Rules the Catniverse

こういうの解ける気しないなぁ。
https://codeforces.com/contest/1152/problem/F2

問題

N,K,Mが与えられる。
以下の条件を満たす数列Aは何通り作れるか。

• Aの長さはK
• Aの値は1以上N以下の整数で、全て異なる
• 1≦A[i+1]≦A[i]+Mを満たす

解法

1～NのうちK個の要素を降順に並べた数列Bを考える。
このBのPermutationとしてAを作るとき、1≦A[i+1]≦A[i]+Mを満たすように作るにはどうするか考えてみよう。

Nから降順にBにK個選んでいくことを考える。
今B[i-1]まで選び終わっており、次にnを加えるかどうかを考える。
B[i]がB[i-1]の直前に来る(A[j]=B[i]、A[j+1]=B[i-1]となるようなjがある)には、B[i]はB[i-1]が選ばれた後M個以内に選ばれなければならない。
さらに、i-1に限らず、B[i]がB[i-k]の直前に来る(A[j]=B[i]、A[j+1]=B[i-k]となるようなjがある)には、B[i]はB[i-k]が選ばれた後M個以内に選ばれていればよい。
これを言い換えると、B[i]としてnを取り入れるとき、Aにおいてどこに入れるかは、n+1,n+2...,n+MのうちBに取り入れたものの直前か、もしくはAの末尾となる。

よって状態として以下を考えよう。
f(n+1,x,mask) := Nからn+1までのうちBにx個取り入れているとき、(n+1)～(n+M)のうち取り入れたものはmaskに示す通り

ここから状態遷移は以下のようになる。

• nをBに取り入れない場合、f(n,x,mask>>1) += f(n+1,x,mask)
• nをBに取り入れる場合、f(n,x+1,(mask>>1)||(1<

x,maskの状態は(K+1)*(2^M)通りなので、(K+1)*(2^M)次の行列を作れば行列累乗でf(1,K,*)を求められる。

int N,K,M;
ll mo=1000000007;
ll ret;
const int MAT=220;
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;
}

Mat A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	int mask;
	
	cin>>N>>K>>M;
	
	Mat A;
	FOR(j,K+1) {
		FOR(mask,1<<M) {
			//not take
			A.v[(j<<M)|(mask>>1)][(j<<M)|(mask)]+=1;
			//take
			if(j<K) A.v[((j+1)<<M)|(1<<(M-1))|(mask>>1)][(j<<M)|(mask)]+=1+__builtin_popcount(mask);
		}
	}
	
	A=powmat(N,A,(K+1)<<M);
	ll ret=0;
	FOR(mask,1<<M) ret+=A.v[(K<<M)|mask][0];
	cout<<ret%mo<<endl;
	
	
}

解法

この挿入DPは思いつかないわ…。