bzoj 5298: [Cqoi2018]交错序列

题意

我们称一个仅由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的余数。

前言

今早听说CQOI今年出得很差，（其实早就听说了），于是就去看了一下
做了一下这题，感觉思路还算是可以，至少我省选前都不是很会化开二项式，唉。。。

题解

暴力枚举个数+组合数学是很难化下去的
于是我们考虑化另外一个式子
$x^a{y}^b=(n?y{)}^a{y}^b=y^b\sum (?1{)}^{a?i}{n}^i{y}^{a?i}=\sum (?1{)}^{a?i}{n}^i{y}^{a+b?i}$
我们只需要求出合法的$y^i$就好了
这个的化可以考虑DP
$f[i][j][k]$表示长度是$i$，结尾是$k$，求的是$y^j$
然后讨论一下转移就好了
显然可以使用矩阵乘法优化
但是有一点要注意，矩乘的时候不要随便mod，要不会被卡常数。。
因为m不大，最后mod一次就够了。。
优化这个mod常数可以小很多

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
LL f[105][200];//长度为这个   i次方   结尾是什么 
LL C[105][105];
LL n,a,b,MOD;
struct qq
{LL s[190][190];LL n,m;//大小 
};
qq operator * (qq x,qq y)
{qq c;c.n=x.n;c.m=y.m;for (LL u=0;u<=c.n;u++)//第一个提供行 for (LL i=0;i<=c.m;i++)//第二个提供列{c.s[u][i]=0;for (LL j=0;j<=x.m;j++)c.s[u][i]=c.s[u][i]+x.s[u][j]*y.s[j][i];c.s[u][i]%=MOD;}return c;
}
qq pow (qq x,LL y)
{qq lalal;memset(lalal.s,0,sizeof(lalal.s));for (int u=0;u<=x.n;u++)	lalal.s[u][u]=1;while (y!=0){if (y&1) lalal=lalal*x;x=x*x;y>>=1;}return lalal;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&a,&b,&MOD);LL o=a+b+1;for (LL u=0;u<=100;u++)	C[u][0]=1;for (LL u=1;u<=100;u++)for (LL i=1;i<=100;i++)C[u][i]=(C[u-1][i]+C[u-1][i-1])%MOD;qq c;	for (LL u=0;u<=a+b;u++)c.s[u][u]=1,c.s[u+o][u]=1;for (LL u=0;u<=a+b;u++)for (LL i=0;i<=u;i++)c.s[i][u+o]=C[u][i];c.n=a+b+o;c.m=a+b+o;	c=pow(c,n);LL ans=0,lalal=1;for (LL i=0;i<=a;i++){LL t=a-i;if (t&1) ans=ans-C[a][i]*lalal%MOD*(c.s[0][a+b-i]+c.s[0][a+b-i+o])%MOD;else ans=ans+C[a][i]*lalal%MOD*(c.s[0][a+b-i]+c.s[0][a+b-i+o])%MOD;ans=ans%MOD;lalal=lalal*n%MOD;}if (ans<0) ans=ans+MOD;printf("%lld\n",ans);return 0;
}