Placing Squares
关键是将问题从抽象的“正方形面积”转为具象的形式：一段长度为 \(d\) 的区间，有两个不同的小球要放进去，则总放置方案就是 \(d^2\) ，且不同的区间间方案是通过乘法原理结合的，刚好是题目中 \(\prod d^2\) 的形式。
于是我们可以设计 DP：设 \(f_{i,j}\) 表示前 \(i\) 个格子中，最后一段中有 \(j\) 个球。明显 \(j\in[0,2]\)。
常规的位置可以直接矩阵快速幂解决；然而对于题目中给出的特殊位置，需要用特殊的矩阵处理。
因此复杂度 \(O(3^3m\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100100];
const int mod=1e9+7;
struct Matrix{
int g[3][3];
int*operator[](int x){return g[x];}
Matrix(){memset(g,0,sizeof(g));}
friend Matrix operator*(Matrix x,Matrix y){
Matrix z;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
(z[i][j]+=1ll*x[i][k]*y[k][j]%mod)%=mod;
}
}
}
return z;
}
}A,B,R;
Matrix ksm(Matrix x,int y){
Matrix z;
z[0][0]=z[1][1]=z[2][2]=1;
for(;y;y>>=1,x=x*x) if(y&1) z=z*x;
return z;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
a[m+1]=n;
A[0][1]=2,A[0][2]=A[1][2]=1;
A[2][0]=1,A[2][1]=A[2][2]=2;
A[0][0]=A[1][1]=1;
B[0][1]=2,B[0][2]=B[1][2]=1;
B[0][0]=B[1][1]=B[2][2]=1;
R=ksm(A,a[1]);
for(int i=1;i<=m;i++){
R=R*B;
R=R*ksm(A,a[i+1]-a[i]-1);
}
printf("%d",R[0][2]);
return 0;
}