AGC013E Placing Squares

学了点不太常见的想法。你一看这个东西他就容斥兮兮的样子，做个容斥dp就转化为求\(m=0\)时的答案。

这个东西就是一堆段的长度平方乘积，那就考虑每一段的生成函数\(F(x)=\sum\limits_{i\geq 0}i^2x^i\)，那么答案的生成函数即为\(\sum\limits_{i\geq0}F^i(x)-1=\frac{F(x)}{1-F(x)}\)。这个东西常数项一定为\(0\)。

那么就手推一下，用二阶差分即可推出\(F(x)\)的封闭形式\(F(x)=\frac{x^2+x}{-x^3+3x^2-3x+1}\)。答案的生成函数的封闭形式即为\(\frac{x^2+x}{-x^3+2x^2-4x+1}\)。

\(G(x)=\frac{x^2+x}{-x^3+2x^2-4x+1}\)，\((-x^3+2x^2-4x+1)G(x)=x^2+x\)，这个东西就可以得出\(g_i\)的递推式。就两边取\([x^n]\)，其中\(n>2\)，就可以得出\(g_i=4g_{i-1}-2g_{i-2}+g_{i-3}\)初始值\(g_0=0,g_1=1,g_2=5\)，做个矩阵快速幂即可单点求值。

回来考虑这个容斥dp，设\(dp_i\)表示最后一段正好压在\(a_i\)位置，前面都不压的方案数。其实就是把每种不合法方案在第一次不合法的位置统计进去。最终答案即为\(g_n-\sum\limits_{i=1}^mdp_i\)。转移也显然\(dp_i=g_{a_i}-\sum\limits_{j=1}^{i-1}dp_jg_{a_i-a_j}\)。这玩意仔细一看发现没法分治fft。不过这个\(g_i=S\times A^{i-2}\)。\(S\)为初始向量，\(A\)为转移矩阵。dp式变为\(dp_i=S\times A^{a_i-2}(I-\sum\limits_{j=1}^{i-1}dp_j\times A^{-a_j})\)。可以发现这个转移矩阵可逆，手动求个\(A\)矩阵的逆，就再维护一个前缀和即可\(O(1)\)转移。总复杂度\(O(mlogn)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define N 1000102
const int p=1e9+7;
inline void upd(int &x,int y){x+=x+y>=p?y-p:y;}
struct node
{
	int s[3][3];
	friend node operator*(node a,node b)
	{node ret;memset(ret.s,0,sizeof(ret.s));
		for(int k=0;k<3;k++)for(int i=0;i<3;i++)if(a.s[i][k])
		for(int j=0;j<3;j++)if(b.s[k][j])upd(ret.s[i][j],1ll*a.s[i][k]*b.s[k][j]%p);return ret;
	}
	friend node operator+(node a,node b)
	{
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)upd(a.s[i][j],b.s[i][j]);return a;
	}
	friend node operator-(node a,node b)
	{
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)a.s[i][j]=(a.s[i][j]-b.s[i][j]+p)%p;return a;
	}
}dw,md,st,iv,su;
int n,m,a[N],dp[N];
inline node ksm(int k)
{
	if(k==0)return dw;
	node d;
	if(k>0)d=md;
	else d=iv,k=-k;
	node ret=dw;while(k){if(k&1)ret=ret*d;d=d*d;k>>=1;}return ret;
}
inline int cal(int x)
{
	if(x==1)return 1;
	if(x==2)return 5;
	node nd=st*ksm(x-2);
	return nd.s[0][0];
}
int main()
{
	dw.s[0][0]=dw.s[1][1]=dw.s[2][2]=1;
	md.s[0][0]=4;md.s[0][1]=md.s[2][0]=md.s[1][2]=1;md.s[1][0]=p-2;
	st.s[0][0]=5,st.s[0][1]=1;
	iv.s[0][2]=iv.s[1][0]=iv.s[2][1]=1;iv.s[2][2]=2,iv.s[1][2]=p-4;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		node nd=dw-su;
		nd=st*ksm(a[i]-2)*nd;
		dp[i]=nd.s[0][0];
		nd=ksm(-a[i]);
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)nd.s[j][k]=1ll*nd.s[j][k]*dp[i]%p;
		su=su+nd;
	}int ans=cal(n);
	for(int i=1;i<=m;i++)ans=(ans-1ll*dp[i]*cal(n-a[i])%p+p)%p;
	printf("%d\n",ans);
}

AGC013E Placing Squares

原文：https://www.cnblogs.com/LebronDurant/p/14493429.html