1.P7116 [NOIP2020] 微信步数

概括题目：每个格子都当作一个起点，然后按着固定的方案走，看看每个起点多少步会走出这个场地
然后统计起点加起来一共多少步

第一个转化：
1.与其思考每个起点，不如思考每一步
例如走了这步之后，哪些起点还活着
活着的就是对这步有贡献的

因为题目是k维，
假设第i维有[1,-li],[n-ri+1,n]这么多人走出去了
（因为每一步都是+1/-1，所以寄掉人数一点连续）

那贡献就是所有(ri-li+1)相乘

然后我们发现，因为走的方案是固定的，所以每一轮(就是走n步)，每一维度的li和ri变化也是固定的，就是说他们有周期
因此从第二轮开始
下面的i是维度
设第一轮后还活着ai个起点，每轮死bi个，最后一轮1-i步死了fi个
那第x+2轮就是
ai-x*bi-fi
把所有维度乘起来就是答案
但是你还要枚举x，就是进行了几轮
$\sum_{i=1}^{n} \sum_{x=0}^{T} \prod_{j=1}^{m} (a_j - x \times b_j - f_i)$
如果老老实实枚举就跟暴力没啥区别
展开后发现可以用拉格朗日插值法
于是我们要用拉格朗日插值

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 500005;

// 快速幂计算x^n mod mod
LL pow_mod(LL x, LL n) {
    LL res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        n >>= 1;
        x = x * x % mod;
    }
    return res;
}

LL fac[N]; // 阶乘数组，用于拉格朗日插值

// 计算1^m + 2^m + ... + n^m (mod mod)
LL cal(LL n, LL m) {
    LL res = 0;
    // 当n较小时直接计算
    if (n <= m + 2) {
        for (int i = 1; i <= n; i++) {
            res = (res + pow_mod(i, m)) % mod;
        }
    } else {
        // 使用拉格朗日插值法计算
        fac[0] = 1;
        // 预处理阶乘
        for (int i = 1; i <= m + 1; i++) {
            fac[i] = fac[i - 1] * i % mod;
        }
        // 计算连乘积t = (n-1)(n-2)...(n-(m+2))
        LL t = 1;
        for (int i = 1; i <= m + 2; i++) {
            t = t * (n - i) % mod;
        }
        LL y = 0;
        int flag = (m + 2) % 2 ? 1 : -1; // 符号控制

        // 拉格朗日插值计算
        for (int i = 1; i <= m + 2; i++) {
            y = (y + pow_mod(i, m)) % mod; // 计算前i项的m次方和
            // 核心插值公式
            res += flag * y * t % mod * pow_mod(n - i, mod - 2) % mod 
                 * pow_mod(fac[i - 1] * fac[m + 2 - i] % mod, mod - 2) % mod;
            flag = -flag; // 符号翻转
        }
        res = (res % mod + mod) % mod; // 保证结果非负
    }
    return res;
}

// 变量定义
int w[20], e[20], l[N][20], r[N][20]; // w:维度大小，e:总偏移量，l/r:左右边界
int a[20], b[20], h[20]; // a:存活数量，b:每轮死亡数量，h:预计算的和
LL f[20][20]; // 动态规划数组，用于多项式计算
int c[N], d[N]; // 输入数据：c是维度，d是偏移量
int n, m; // n:步数，m:维度数

int main() {
    // 输入处理
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &c[i], &d[i]);
        e[c[i]] += d[i]; // 累计总偏移量
        // 复制上一步的边界
        for (int j = 1; j <= m; j++) {
            l[i][j] = l[i - 1][j];
            r[i][j] = r[i - 1][j];
        }
        // 更新当前维度的左右边界
        l[i][c[i]] = min(l[i][c[i]], e[c[i]]);
        r[i][c[i]] = max(r[i][c[i]], e[c[i]]);
    }

    // 检查是否无解（一轮后回到原点且没有起点死亡）
    bool lose = 1;
    for (int i = 1; i <= m; i++) {
        if (e[i] != 0 || r[n][i] - l[n][i] >= w[i]) {
            lose = 0;
        }
    }
    if (lose) return puts("-1"), 0;

    // 计算第一轮后各维度存活数量
    for (int j = 1; j <= m; j++) {
        a[j] = w[j] - (r[n][j] - l[n][j]);
    }

    LL ans = 0;
    // 计算第一轮的贡献
    for (int i = 0; i <= n; i++) {
        LL s = 1;
        for (int j = 1; j <= m; j++) {
            s = s * max(0, (w[j] - (r[i][j] - l[i][j]))) % mod;
        }
        ans = (ans + s) % mod;
    }

    // 更新第二轮开始的死亡范围
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            r[i][j] = max(0, r[i][j] + e[j] - r[n][j]);
            l[i][j] = min(0, l[i][j] + e[j] - l[n][j]);
        }
    }

    // 计算每轮各维度死亡数量
    for (int j = 1; j <= m; j++) {
        b[j] = r[n][j] - l[n][j];
    }

    // 计算第二轮开始的贡献
    int last = -1;
    for (int i = 1; i <= n; i++) {
        // 初始化动态规划数组
        for (int j = 0; j <= m; j++) f[0][j] = 0;
        f[0][0] = 1;

        int t = INF;
        // 计算多项式系数
        for (int j = 1; j <= m; j++) {
            int x = a[j] - r[i][j] + l[i][j];
            if (x <= 0) goto M1;  // 第二轮就暴毙了，跳过

            if (b[j] > 0) t = min(t, x / b[j]); // 计算最大轮数

            // 动态规划计算多项式系数
            for (int k = 0; k <= m; k++) {
                f[j][k] = f[j - 1][k] * x % mod;
                if (k > 0)
                    f[j][k] = (f[j][k] + f[j - 1][k - 1] * -b[j]) % mod;
            }
        }

        // 计算贡献
        ans += f[m][0] * (t + 1) % mod; // 常数项贡献

        // 预计算幂和
        if (t != last) {
            last = t;
            for (int j = 1; j <= m; j++) h[j] = cal(t, j);
        }

        // 累加多项式各项贡献
        for (int j = 1; j <= m; j++) {
            ans += h[j] * f[m][j] % mod;
        }
    }

M1:;
    // 处理结果并输出
    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}