[AGC013-E][DP][矩阵乘法]Placing Squares

Description

给你一个大小为m的集合S，S中不包含n。
现在对于一个正整数序列a1?ak(k并不是给定的)，如果不存在si属于集合S，且sk=n，就是合法的，其中s表示a的前缀和。
这样的序列贡献是 $\Pi a[i{]}^2$ ，求所有合法序列的贡献和。
$m<=10^5，n<=10^9$

题解

一开始净往整数拆分想了…
模型转化
有一个长度为$n$的序列，你可以放分隔符。如果$i$不可用的话$i$和$i+1$中间不能放分隔符
两个分隔符中间要放两个不同颜色的球，可以放在同一位置
求方案数
于是可以用一个$dp[i][0/1/2]$表示在$i$这个位置，这里和上一个分隔符组成的区间以及放了$0/1/2$个球的方案数
转移很简单自己写一下就知道了…
由于分隔符只有$10^5$个，分转移写成矩阵然后分隔符那里暴力做一下

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
const LL mod=1e9+7;
const int MAXM=100005;
int a[MAXM],n,m;
void ad(LL &x,LL y){
    x+=y;if(x>=mod)x-=mod;}
struct matrix
{
    LL m[3][3];matrix(){
    memset(m,0,sizeof(m));}friend matrix operator *(matrix u1,matrix u2){
    matrix ret;for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)for(int k=0;k<=2;k++)ad(ret.m[i][k],u1.m[i][j]*u2.m[j][k]%mod);return ret;}
}nxt,temp,st;
matrix pow_mod(matrix u1,int b)
{
    matrix ans;for(int i=0;i<=2;i++)ans.m[i][i]=1;while(b){
    if(b&1)ans=ans*u1;u1=u1*u1;b>>=1;}return ans;
}
void vio()
{
    matrix u1;u1.m[0][0]=st.m[0][0];u1.m[0][1]=(st.m[0][0]*2+st.m[0][1])%mod;u1.m[0][2]=(st.m[0][1]+st.m[0][2]+st.m[0][0])%mod;st=u1;
}
int main()
{
    n=read(),m=read();for(int i=1;i<=m;i++)a[i]=read();st.m[0][0]=1;nxt.m[0][0]=nxt.m[2][0]=1;nxt.m[0][1]=nxt.m[2][1]=2;nxt.m[1][1]=1;nxt.m[1][2]=1;nxt.m[2][2]=2;nxt.m[0][2]=1;int lst=0;for(int i=1;i<=m;i++){
    temp=pow_mod(nxt,a[i]-lst);st=st*temp;vio();lst=a[i]+1;}temp=pow_mod(nxt,n-lst);st=st*temp;pr2(st.m[0][2]);return 0;}