bzoj 5298: [Cqoi2018]交错序列

Description

我们称一个仅由0、1构成的序列为"交错序列"，当且仅当序列中没有相邻的1（可以有相邻的0）。例如，000，001

，101，都是交错序列，而110则不是。对于一个长度为n的交错序列，统计其中0和1出现的次数，分别记为x和y。

给定参数a、b，定义一个交错序列的特征值为x^ayb。注意这里规定任何整数的0次幂都等于1（包括0^0=1）。

显然长度为n的交错序列可能有多个。我们想要知道，所有长度为n的交错序列的特征值的和，除以m的余数。(m是

一个给定的质数)例如，全部长度为3的交错串为：000、001、010、100、101。

Solution

看到 \(x^ay^b\) 容易想到要展开,然后就发现变成了

\[y^b*\sum_{i=0}^{a}(-1)^{a-i}*C_{a}^{i}*n^{i}*y^{a-i}
\]

\[\sum_{i=0}^{a}(-1)^{a-i}*C_{a}^{i}*n^{i}*y^{a+b-i}
\]

这样就只需要统计 \(\sum y^{a+b-i}\) 了

\(f[i][j][0/1]\) 表示这一位填 \(0/1\) 的特征值的 \(j\) 次方之和

如果增加一个 \(1\),\(y^{j}\) 就要变成 \((y+1)^{j}\),二项式定理展开做个差

发现就是 \(\sum_{k=0}^{j-1}C_{j}^{k}*y^k\)

而 \(f[i][k]\) 就是 \(y^k\)

转移系数就确定了,矩阵快速幂优化一下就好了

千万不要像我一样拆成了 \(x^a*(n-x)^b\),转移复杂一些,常数大的过不去

#include<bits/stdc++.h>

using namespace std;

const int N=205;

int n,a,b,mod,c[N][N],m,d;

inline void priwork(){

	for(int i=0;i<N;i++){

		c[i][0]=1;

		for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

	}

}

struct mat{

	int a[N][N];

	mat(){}

	inline mat operator *(const mat &p)const{

		mat ret;

		for(int i=0;i<m;i++)

			for(int j=0;j<m;j++){

				ret.a[i][j]=0;

				for(int k=0;k<m;k++)

					if(a[i][k] && p.a[k][j])

						ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*p.a[k][j])%mod;

			}

		return ret;

	}

}S,T;

inline void solve(){

	for(int i=0;i<d;i++){

		T.a[i+d][i]=1;T.a[i][i]=1;

		for(int j=i;j<d;j++)T.a[i][j+d]=c[j][i];

	}

	int k=n;

	S.a[0][0]=1;

	while(k){

		if(k&1)S=S*T;

		T=T*T;k>>=1;

	}

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  int ans=0;

  memset(S.a,0,sizeof(S.a));memset(T.a,0,sizeof(T.a));

  cin>>n>>a>>b>>mod;d=a+b+1;m=d*2;

  priwork();solve();

  for(int i=0;i<d;i++)S.a[0][i]=(S.a[0][i]+S.a[0][i+d])%mod;

  for(int i=0,t=1;i<=a;i++,t=1ll*t*n%mod)

	  ans=(ans+1ll*((a-i)&1?-1:1)*c[a][i]*t%mod*S.a[0][a+b-i])%mod;

  if(ans<0)ans+=mod;

  cout<<ans<<endl;

  return 0;

}

巴特西

bzoj 5298: [Cqoi2018]交错序列

Description

Solution

最新文章

热门文章