「解题报告」AGC013E Placing Squares

想了一会然后看题解，翻到日文题解然后又关了，然后突然会了，怎么回事

第一眼生成函数！做不了。

考虑经典拆贡献方法，把平方的贡献变成从区间中选两个数的方案数。这样我们可以用一个 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;
}