CSP模拟-19

Neck Deep / 2023-08-13 / 原文

D.西安行原 AGC013E

思路

DP.最朴素的DP是\(\Theta(n^2)\)的，考虑i是当前DP到的点，j是当前线段的起点.考虑分类讨论

数据范围很抽象，所以考虑用矩阵加速。首先试着把它转换成线性的

赋予它一个新的组合意义:

把每条线段看作一个整体\(a_i\)

因为题最后求的是\(\prod_{i=1}^{num}a_i^2\),

所以把每个a复制一份，把他俩看成两个本质不同的球球

把每条线段抽象成一个最多能装下且必须要装满2个球的容器，先不论长度。

(要且只分成两份是因为求的是a^2)

转移

我们定义\(f_{i,j}\)表示当前DP到i点，当前这最后一个线段放了j个球

分成两个矩阵，一个是能作为断点的m1，一个是不能的m2

关于m1:

\[f_{i,0}=f_{i-1,0}+f_{i-1,2} \]

\[f_{i,1}=2f_{i-1,0}+f_{i,1}+2f_{i-1,2} \]

\[f_{i,2}=f_{i-1,0}+f_{i-1,1}+2f_{i-1,2} \]

关于m2:

\[f_{i,0}=f_{i-1,0} \]

\[f_{i,1}=2f_{i-1,0}+f_{i,1} \]

\[f_{i,2}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2} \]

图示

竖线表示断开，两种小球分别为黑、白。
图中在相同位置堆起来的，表示多种可能。

分别构造出了m1和m2，那么DP就变成了n-m个m1和m个m2相乘

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define il inline
const int N=300010;
const int mod=1e9+7;
#define int long long
#define Croll(i,l,r) for(int i=l;i<=r;++i)
//////////
struct mat
{
    int sq[3][3];
    mat()
    {
        sq[0][0]=sq[0][1]=sq[0][2]=0;
        sq[1][0]=sq[1][1]=sq[1][2]=0;
        sq[2][0]=sq[2][1]=sq[2][2]=0;
    }
}I,m1,m2;
mat qp(mat,int);
mat operator*(mat,mat);
//////////
int n,m,f[N][3];
int w[N],vis[N];
//////////
il int read();
void Wonder_of_U();
//////////
main()
{
    Wonder_of_U();
    n=read();m=read();
    Croll(i,1,m)w[i]=read();
    mat ans;
    if(!m)ans=qp(m1,n);
    else
    {
        ans=I;
        Croll(i,1,m)
        {
            if(i==1)ans=ans*qp(m1,w[i]);
            else ans=ans*qp(m1,w[i]-w[i-1]-1);
            ans=ans*m2;
        }
        ans=ans*qp(m1,n-w[m]-1);
    }
    cout<<ans.sq[0][2]<<endl;
    return 0;
}
mat qp(mat x,int k)
{
    mat res=I;
    while(k)
    {
        if (k & 1)res=res*x;
        x=x*x;k>>=1;
    }
    return res;
}
void Wonder_of_U()
{
    I.sq[0][0]=I.sq[1][1]=I.sq[2][2]=1;
    m1.sq[0][0]=1;m1.sq[0][1]=2;m1.sq[0][2]=1;
    m1.sq[1][0]=0;m1.sq[1][1]=1;m1.sq[1][2]=1;
    m1.sq[2][0]=1;m1.sq[2][1]=2;m1.sq[2][2]=2;
    m2.sq[0][0]=1;m2.sq[0][1]=2;m2.sq[0][2]=1;
    m2.sq[1][0]=0;m2.sq[1][1]=1;m2.sq[1][2]=1;
    m2.sq[2][0]=0;m2.sq[2][1]=0;m2.sq[2][2]=1;
}
mat operator*(mat a,mat b)
{
    mat ans;
    Croll(i,0,2)Croll(j,0,2)
    {
        Croll(k,0,2)
            ans.sq[i][j]+=a.sq[i][k]*b.sq[k][j];
        ans.sq[i][j]%=mod;
    }
    return ans;
}
il int read()
{
    int f=1,x=0;char w=getchar();
    while(w<'0'||w>'9')
    {if(w=='-')f=-1;w=getchar();}
    while(w>='0'&&w<='9')
    {x=(x<<3)+(x<<1)+(w^48);w=getchar();}
    return f*x;
}