题解

考虑\(dp\)

\[ dp[i]=\sum_{i=0}^{i-1}dp[j]*(i-j)^2 \]

我们可以设\((i-j)\)为\(x\),那么随着\(i\)向右移动一格，每个\(x\)都是会增长\(1\)的。

\[ dp[i]=\sum_{i=0}^{i-1}dp[j]*(x+1)^2 \]

\[ dp[i]=\sum_{i=0}^{i-1}dp[j]*(x^2+2x+1) \]

为了转移，我们需要将这三段分开维护。

注意，当没有障碍点的时候，转移需要再加上一个\(dp[i]\)。

转移的时候构造矩阵就可以了。

代码

#include
    
     using namespace std;typedef long long ll;const int mod=1e9+7;int n,m;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}inline void MOD(ll &x){x=x>=mod?x-mod:x;}struct matrix{    ll a[3][3];    matrix(){memset(a,0,sizeof(a));}    inline matrix operator *(const matrix &b)const{        matrix c;        for(int i=0;i<3;++i)            for(int j=0;j<3;++j){                c.a[i][j]=0;                for(int k=0;k<3;++k)                    MOD(c.a[i][j]+=a[i][k]*b.a[k][j]%mod);            }        return c;    }    inline void print(){        for(int i=0;i<3;++i){            for(int j=0;j<3;++j)cout<
     
      <<" ";puts("");        }        puts("");    }}a1,a2,ans;inline matrix solve(matrix a,matrix b,int c){    while(c){        if(c&1)a=a*b;        b=b*b;        c>>=1;    }    return a;}int main(){    n=rd();m=rd();    a1.a[0][0]=1;a1.a[1][0]=1;a1.a[1][1]=1;a1.a[2][0]=1;a1.a[2][1]=2;a1.a[2][2]=1;    a2=a1;a2.a[0][2]++;a2.a[1][2]++;a2.a[2][2]++;    ans.a[0][2]=1;    int x=0,pre=1;    for(int i=1;i<=m;++i){        x=rd();        ans=solve(ans,a2,x-pre);        ans=ans*a1;        pre=x+1;    }    ans=solve(ans,a2,n-pre);    cout<<(ans.a[0][0]+ans.a[0][1]+ans.a[0][2])%mod;    return 0;}