P4456 [CQOI2018] 交错序列
Llx2022
·
·
题解
P4456 [CQOI2018] 交错序列
题意
求长度为 n 的所有交错序列的贡献总和。
形式化上，即求 \sum x^ay^b，其中 x 为交错序列中 1 的个数，y 为 0 的个数，a，b 是给定的常系数。
# **分析**
观察 $x^ay^b$，由于 $x+y=n$，那么考虑二项式定理。
$$
\begin{aligned}
x^ay^b&=(n-y)^ay^b\\
&=\sum_{i=0}^a\binom{a}{i}n^i(-y)^{a-i}y^b\\
&=\sum_{i=0}^a\binom{a}{i}(-1)^{a-i}n^iy^{a+b-i}\\
\end{aligned}
$$
现在对于这个式子我们只有 $y$ 不确定，那么我们可以考虑 $dp$，发现我们需要的是合法的 $1$ 的个数，$[0,a+b]$ 范围内的不同 $y^{a+b}$ 的值。
那直接设状态 $f_{i,j,0/1}$ 表示当前到 $i$ 位，最后一位为 $0/1$，当前合法序列中 $1$ 的个数的 $j$ 次方的所有总和，即 $\sum j^i$，**为什么存总和**，这是因为组成 $j$ 个 $1$ 的方案有很多种，并且都是互不影响的，若带回原式，运用结合律就是最后的结果。
因此可以设计**转移方程**。
- 若当前位为 $0$ 对答案无贡献，直接考虑继承。
$$
f_{i,j,0}=f_{i-1,j,1}+f_{i-1,j,0}
$$
- 若当前位为 $1$ 那么上一位只能是 $0$，并且 $1$ 的个数加 $1$。
我们考虑 $1$ 的个数加 $1$ 的贡献，$j \rightarrow j+1$，则新贡献为 $(j+1)^j$，还是考虑二项式定理。
$$
\begin{aligned}
(j+1)^j&=\sum_{i=0}^j\binom{j}{i}j^i1^{j-i}\\
&=\sum_{i=0}^j\binom{j}{i}j^i
\end{aligned}
$$
后面 $j^i$ 正是我们状态方程保存的结果，因此直接从上一个转移就好。
$$
f_{i,j,1}=\sum_{k=0}^j\binom{j}{k}f_{i-1,k,0}
$$
我们发现第一位总与上一位有关，第二维也是呈线性的，因此可以考虑矩阵优化 $dp$，转移自然就去掉了第 $1$ 维。
我们考虑构造初始矩阵 $f$，加速矩阵 $g$，答案矩阵 $ans$。
加速矩阵 $g$ 拆分为四个部分。
- 左上角单位矩阵（$0$ 到 $0$）
- 左下角单位矩阵（$1$ 到 $1$）
- 右上角组合数矩阵（$0$ 到 $1$）
- 右下角全 $0$ 矩阵（不合法）
$$
\begin{matrix}
\left(
\begin{array}{cccccccc}
&f_{0,0} &f_{1,0} &f_{2,0} &f_{a+b,0}&f_{0,1}&f_{1,1}&f_{2,1}&f_{a+b,1}
\end{array}
\right)
\left(
\begin{array}{ccc}
1 &0 &0 &{j\choose i} &{j+1\choose i} &{j+3\choose i}\\
0 &1 &0 &{j\choose i+1} &{j+1\choose i+1} &{j+3\choose i+1}\\
0 &0 &1 &{j\choose i+2} &{j+1\choose i+2} &{j+3\choose i+2}\\
1 &0 &0 &0 &0 &0\\
0 &1 &0 &0 &0 &0\\
0 &0 &1 &0 &0 &0\\
\end{array}
\right)\\
=
\left(
\begin{array}{c}
f'_{0,0}&f'_{1,0}&f'_{2,0}&f'_{a+b,0}&f'_{0,1}&f'_{1,1}&f'_{2,1}&f'_{a+b,1}
\end{array}
\right)
\end{matrix}
$$
**矩阵略有不完善，望见谅。**
那么答案就是 $fg^n=ans$，并带回初始推出的式子。
矩阵计算和矩阵快速幂，综合时间复杂度为 $O((a+b)^3\log n)$。
约为 $182^3\times 24 = 144685632\approx10^8$ 可过。
# **Code**
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int N=183;//(a+b+1)*2
int n,a,b,mod;
struct matrix{
int n,m,f[N][N];
matrix(int n,int m):n(n),m(m){
memset(f,0,sizeof f);
}
int *operator[](int i){
return f[i];
}
const int *operator[](int i)const{
return f[i];
}
matrix operator*(const matrix &b)const{
matrix res(n,b.m);
for(int i=0;i<n;i++){
for(int k=0;k<m;k++){
for(int j=0;j<b.m;j++){
res[i][j]+=1ll*f[i][k]*b[k][j]%mod;
res[i][j]%=mod;
}
}
}
return res;
}
};
int C[N][N];
int pown[N];
void init(int n){
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-1]+C[i-1][j])%mod;
}
}
}
void initpown(int a,int n){
pown[0]=1;
for(int i=1;i<=a;i++){
pown[i]=1ll*pown[i-1]*n%mod;
}
}
int main(){
cin>>n>>a>>b>>mod;
init(a+b);
initpown(a,n);
int d=(a+b+1)*2;
matrix mul(d,d);
/*
0->0 0->1
[1, 0, C(j,i),C(j+1,i) ]
[0, 1, C(j,i+1),C(j+1,i+1)]
[1, 0, 0, 0]
[0, 1, 0, 0]
1->0 1,1(无)
*/
int c=a+b+1;
for(int i=0;i<=a+b;i++){
mul[i][i]=1;
mul[i+c][i]=1;
for(int j=i;j<=a+b;j++){
mul[i][j+c]=C[j][i];
}
}
matrix ans(1, d);
ans[0][0]=1;
while(n){
if(n&1) ans=ans*mul;
mul=mul*mul;
n>>=1;
}
int res=0;
for(int i=0;i<=a;i++){
int p=a+b-i;
int coefficient=((a-i)&1?-1:1);
long long fac=1ll*C[a][i]*coefficient*pown[i]%mod;
long long cnt=(ans[0][p]+ans[0][p+c])%mod;
res=(res+cnt*fac)%mod;
}
cout<<(res+mod)%mod;
return 0;
}
```