AT2371 [AGC013E] Placing Squares
设 \(f_i\) 表示考虑到第 \(i\) 个点的贡献之和且不考虑坏点。不难发现转移方程为 \(f_n=\sum_{i=0}^n f_i\times (n-i)^2\)
则当第 \(n\) 个点是标记点的时候，\(f_{n+1}=\sum_{i=0}^{n-1} f_i\times (n-i+1)^2\)。
当第 \(n\) 个点不是标记点的时候，\(f_{n+1}=\sum_{i=0}^n f_i\times (n-i+1)^2=\sum_{i=0}^{n-1}f_i\times(n-i+1)^2+f_n\)。
设 \(x_n=\sum_{i=0}^{n-1} f_i,y_n=\sum_{i=0}^{n-1} f_i\times (n-i),z_n=\sum_{i=0}^{n-1} f_i\times (n-i)^2\)。
可以知道 \(f_n=z_n\)，\(f_{n+1}=x_n+2\times y_n+z_n+f_n\)。
考虑矩阵乘法的转移，假设当前已知 \(x_n,y_n,z_n\)。则
- 当第 \(n\) 个点是标记点的时候（ \(f_n=0\)）\[x_{n+1}=\sum_{i=1}^{n-1}f_i=x_n\\ y_{n+1}=\sum_{i=0}^{n-1} f_i\times (n-i+1)=\sum_{i=0}^{n-1} f_i\times(n-i)+\sum_{i=1}^{n-1}f_i=y_n+x_n\\ z_{n+1}=f_{n+1}=x_n+2\times y_n+z_n \]
当第 \(n\) 个点不是标记点的时候，
\[x_{n+1}=\sum_{i=0}^n f_i=\sum_{i=1}^{n-1}f_i + f_n=x_n+z_n\\ y_{n+1}=\sum_{i=0}^n f_i\times (n-i+1)=\sum_{i=0}^{n-1} f_i\times(n-i)+\sum_{i=1}^{n-1}f_i+f_n=y_n+x_n+z_n\\ z_{n+1}=f_{n+1}=x_n+2\times y_n+z_n+f_n=x_n+2\times y_n+2\times z_n \]转换为矩阵形式，当第 \(n\) 个点是标记点时
\[\begin{bmatrix}x_n&y_n&z_n\end{bmatrix}\times \begin{bmatrix}1&1&1\\0&1&2 \\0&0&1\end{bmatrix}=\begin{bmatrix}x_{n+1}&y_{n+1}&z_{n+1}\end{bmatrix} \]同理可以写出当第 \(n\) 个点不是标记点时
\[\begin{bmatrix}x_n&y_n&z_n\end{bmatrix}\times \begin{bmatrix}1&1&1\\0&1&2 \\1&1&2\end{bmatrix}=\begin{bmatrix}x_{n+1}&y_{n+1}&z_{n+1}\end{bmatrix} \]将两个标记点之间的直接矩阵快速幂加速即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<string>
#include<cstring>
#include<set>
#include<stack>
#include<queue>
#include<bitset>
using namespace std;
namespace IO{
template<typename T>inline void read(T &x){
x=0;
char ch=getchar();
bool flag=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^'0'),ch=getchar();
if(ch!='.'){
x=flag?-x:x;
return;
}
double Base=0.1;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x+Base*(ch^'0'),Base/=10.0,ch=getchar();
x=flag?-x:x;
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
const int DM[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
inline void putd(char ch,double x,int w){
if(x<0) putchar('-'),x=-x;
if(!w){
put(ch,(int)(x+0.5));
return;
}
int prex=(int)x;
x-=(int)x;
x*=DM[w];
x+=0.5;
int nowx=(int)x,now=0;
if(nowx>=DM[w]) nowx=0,prex++;
put('.',prex);
int xx=nowx;
if(!xx) now=1;
else while(xx) xx/=10,now++;
now=w-now;
while(now--) putchar('0');
put(ch,nowx);
}
inline void putstr(string s){
for(int i=0;i<s.length();i++) putchar(s[i]);
}
}
using namespace IO;
#define N 4
#define ll long long
#define mod 1000000007
struct matrix{
int mat[N][N];
matrix(){
memset(mat,0,sizeof(mat));
}
inline void e(){
memset(mat,0,sizeof(mat));
for(int i=1;i<=3;i++) mat[i][i]=1;
}
inline matrix operator*(const matrix &b)const{
matrix c;
for(int k=1;k<=3;k++)
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
c.mat[i][j]=(c.mat[i][j]+(ll)mat[i][k]*b.mat[k][j]%mod)%mod;
return c;
}
inline matrix operator^(const int &B)const{
int b=B;
matrix Base=*this,res;
res.e();
while(b){
if(b&1) res=res*Base;
Base=Base*Base;
b>>=1;
}
return res;
}
}base,bad,ans;
int n,m,lst;
int main(){
base.mat[1][1]=1;base.mat[1][2]=1;base.mat[1][3]=1;
base.mat[2][1]=0;base.mat[2][2]=1;base.mat[2][3]=2;
base.mat[3][1]=1;base.mat[3][2]=1;base.mat[3][3]=2;
bad.mat[1][1]=1;bad.mat[1][2]=1;bad.mat[1][3]=1;
bad.mat[2][1]=0;bad.mat[2][2]=1;bad.mat[2][3]=2;
bad.mat[3][1]=0;bad.mat[3][2]=0;bad.mat[3][3]=1;
ans.mat[1][1]=ans.mat[1][2]=ans.mat[1][3]=1;
read(n),read(m);
for(int i=1,x;i<=m;i++){
read(x);
int now=x-lst-1;
if(now) ans=ans*(base^now);
ans=ans*bad;
lst=x;
}
ans=ans*(base^(n-lst-1));
put('\n',ans.mat[1][3]);
return 0;
}