【DP】【矩阵加速】AGC013 E Placing Squares

分析：

有点巧妙的DP题。。。虽然题解给的方法很玄妙，但其实暴力硬推也能推出一样的DP转移式。

首先，把模型转换一下，定义为：在数轴上放一些隔板（起始位置和终止位置必须放），每对相邻的隔板之间，都放一个红色和蓝色的小球。小球可以放在隔板间的任意一个位置，甚至可以重合，这样它的方案数就正好是我们要求的答案。。。。

所以可以设$DP[i][0,1,2]$分别表示前i个格子，在当前这个区间中，已经放了0,1,2个小球的方案数。

首先是在第i和i-1格的空隙不放隔板的方案。
$DP[i][0]=DP[i?1][0]$
$DP[i][1]=DP[i?1][0]+DP[i?1][1]$
$DP[i][2]=DP[i?1][0]+DP[i?1][1]?2+DP[i?1][2]$

然后还有放隔板的方案（此时要求这个点未被标记）
$DP[i][0]=DP[i?1][2]$
$DP[i][1]=DP[i?1][2]$
$DP[i][2]=DP[i?1][2]$

对于这两种转移，在每两个相邻的标记位置之间，使用矩阵乘法快速搞掉，然后在转移一次（第一种情况）。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define SF scanf #define PF printf #define MAXN 100010 #define MOD 1000000007 using namespace std; typedef long long ll; int pos[MAXN]; int n,m; struct node{
     ll x[3][3]; void operator *=(const node &a) {
     ll c[3][3]={
     0};for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)(c[i][j]+=x[i][k]*a.x[k][j])%=MOD;for(int i=0;i<3;i++)for(int j=0;j<3;j++)x[i][j]=c[i][j];} }e,a,e1,e2; void fsp(node &x,node y,int t){
     node y1=y;while(t){
     if(t&1)x*=y1;y1*=y1;t>>=1; } } ll A[3],B[3]; int main(){
     SF("%d%d",&n,&m);for(int i=1;i<=m;i++)SF("%d",&pos[i]);e.x[0][0]=e.x[1][1]=e.x[2][2]=e.x[1][2]=e.x[0][2]=1;e.x[0][1]=2;e2.x[0][0]=e2.x[1][1]=e2.x[2][2]=e2.x[2][0]=1;e1=e;e1*=e2;m++;pos[m]=n;B[0]=1;for(int l=1;l<=m;l++){
     int s=pos[l]-pos[l-1]-1;memset(a.x,0,sizeof a.x);for(int i=0;i<3;i++)a.x[i][i]=1;fsp(a,e1,s);a*=e;for(int i=0;i<3;i++){
     A[i]=0;for(int j=0;j<3;j++)A[i]=(A[i]+B[j]*a.x[j][i])%MOD;}for(int i=0;i<3;i++)B[i]=A[i];}PF("%lld",B[2]); }