想了一会然后看题解，翻到日文题解然后又关了，然后突然会了，怎么回事
第一眼生成函数！做不了。
考虑经典拆贡献方法，把平方的贡献变成从区间中选两个数的方案数。这样我们可以用一个 DP 来计数。
设 \(f_{i, j}\) 表示到了第 \(i\) 格，已经选了 \(j\) 个数的方案数。如果没有限制，那么就直接枚举下一个格子选 \(0/1/2\) 个的方案数，或者进行一次划分。转移容易写成矩阵形式。然后有限制的位置只需要把划分的转移去掉就行了，中间部分矩阵快速幂一下。
好弱智。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, P = 1000000007;
int n, m, a[MAXN];
struct Matrix {
int a[3][3];
Matrix() { memset(a, 0, sizeof a); }
int* operator[](int b) { return a[b]; }
const int* operator[](int b) const { return a[b]; }
Matrix operator*(Matrix b) {
Matrix c;
for (int k = 0; k < 3; k++) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % P;
}
}
}
return c;
}
Matrix pow(int b) {
Matrix a = *this, ans;
ans[0][0] = ans[1][1] = ans[2][2] = 1;
while (b) {
if (b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
} x, y;
int main() {
x[0][0] = 1, x[0][1] = 2, x[0][2] = 1;
x[1][0] = 0, x[1][1] = 1, x[1][2] = 1;
x[2][0] = 1, x[2][1] = 2, x[2][2] = 2;
y[0][0] = 1, y[0][1] = 2, y[0][2] = 1;
y[1][0] = 0, y[1][1] = 1, y[1][2] = 1;
y[2][0] = 0, y[2][1] = 0, y[2][2] = 1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
a[m + 1] = n;
Matrix p = x.pow(a[1]);
for (int i = 1; i <= m; i++) {
p = p * y;
p = p * x.pow(a[i + 1] - a[i] - 1);
}
printf("%d\n", p[0][2]);
return 0;
}