【BZOJ5298】[CQOI2018]交错序列（动态规划，矩阵快速幂）

题面

题解

考虑由(x)个(1)和(y)个(0)组成的合法串的个数。
显然就是把(1)当做隔板插入进去，那么有(y+1)个位置可以放(1)，所以方案数就是({y+1choose x})。
而(x^ay^b)的贡献可以直接快速幂算，所以问题变成了求组合数。然后(Lucas)一下就可以得到(TLE)的好成绩了。复杂度(O(nlogn))（事实上只要有快速幂就会(T)）

那就换种做法吧。。。来(dp)。
把(x^ay^b)展开其中一个部分，即((n-y)^ay^b)，大力展开之后变成了(displaystyle y^bsum_{i=0}^a{achoose i}(-y)^{a-i}n^{i})。再化简一下就是(displaystyle sum_{i=0}^a{achoose i}(-1)^{a-i}y^{a+b-i}n^i)，因此只需要对于每一个(i)，求(y^{a+b-i})的和就好了。
设(f[i][j][0/1])表示现在考虑到了第(i)位，这一位填的数是(0/1)的特征值的(j)次方和。
那么这样子考虑在这一位上填上了一个(1)，那么(y^j)变成了((y+1)^j)，二项式定理展开+做差之后，得到的就是((y+1)^j=sum_{i=0}^{j} {jchoose i}y^i)。
这样子就可以使用矩乘来进行转移，时间复杂度大概是(O((2(a+b+1))^3log))。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 10000100
int a,b,n,N,ans,MOD,C[200][200],pw[200];
int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
struct Matrix
{
	int s[200][200];
	void clear(){memset(s,0,sizeof(s));}
	void pre(){clear();for(int i=0;i<N;++i)s[i][i]=1;}
	int*operator[](int x){return s[x];}
}G;
Matrix operator*(Matrix &a,Matrix &b)
{
	Matrix ret;ret.clear();
	for(int i=0;i<N;++i)
		for(int k=0;k<N;++k)
			if(a[i][k])
				for(int j=0;j<N;++j)
					ret[i][j]=(ret[i][j]+1ll*a[i][k]*b[k][j])%MOD;
	return ret;
}
Matrix fpow(Matrix a,int b)
{
	Matrix s;s.clear();s[0][0]=1;
	while(b){if(b&1)s=s*a;a=a*a;b>>=1;}
	return s;
}
int main()
{
	scanf("%d%d%d%d",&n,&a,&b,&MOD);
	for(int i=0;i<=a+b;++i)C[i][0]=1;
	for(int i=1;i<=a+b;++i)
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	pw[0]=1;for(int i=1;i<=a+b;++i)pw[i]=1ll*pw[i-1]*n%MOD;
	int l=a+b+1;N=l<<1;
	for(int i=0;i<=a+b;++i)
	{
		G[i+l][i]=G[i][i]=1;
		for(int j=0;j<=i;++j)G[j][i+l]=C[i][j];
	}
	Matrix A=fpow(G,n);
	for(int i=0,d=(a&1)?MOD-1:1;i<=a;++i,d=MOD-d)
		ans=(ans+1ll*C[a][i]*d%MOD*(A[0][a+b-i]+A[0][a+b-i+l])%MOD*pw[i])%MOD;
	printf("%d
",ans);
	return 0;	
}