题解

问题分析

题目要求计算小C从k维场地的所有位置出发，按固定路线重复行走直至走出场地的总步数。若存在某位置永远走不出去，输出-1。

核心挑战：

1. 无限循环判断：若路线周期（n步）的总位移为零，且位移范围始终在场地内，则可能无限循环。
2. 总步数计算：需累加所有位置的首次走出场地的步数，由于场地规模极大（(w_i \leq 10^9)），直接枚举位置不可行，需通过数学建模简化计算。

核心思路

1. 总步数转化：总步数等价于“活到第t步的位置数量”的总和（(t \geq 1)）。一个位置“活到第t步”指该位置出发后，前t步均未走出场地。

2. 周期与位移分析：路线按n步为周期重复，定义：

   • 前缀位移：前i步的累计位移（(1 \leq i \leq n)）。
   • 周期总位移：n步后每个维度的总位移（(tt[k])）。
   • 位移范围：前i步中每个维度的最小（(L[i][k])）和最大（(R[i][k])）累计位移。

3. 无限循环判断：若存在维度k，其周期总位移(tt[k] = 0)，且位移范围满足(R[i+n][k] - L[i+n][k] + 1 \leq w[k])对所有i成立，则该维度永远不会超出场地，可能无限循环，输出-1。

4. 有效位置计数：对于每个i（(1 \leq i \leq n)），计算经过(m)个完整周期（(m \geq 0)）后再走i步仍在场内的位置数量，求和即为总步数的一部分。由于数量是关于m的多项式（次数为k），用拉格朗日插值高效计算和。

详细步骤

1. 预处理位移信息

• 计算每个维度的周期总位移(tt[k])（n步后累计位移）。
• 计算前(i)步（(1 \leq i \leq 2n)）的累计位移的最小(L[i][k])和最大(R[i][k])值（覆盖两个周期，便于处理周期重复）。

2. 无限循环判断

• 对每个维度k，若(tt[k] = 0)，且对于所有i，位移范围(R[i+n][k] - L[i+n][k] + 1 \leq w[k])，则存在位置永远走不出去，输出-1。

3. 计算总步数

• 分情况处理：对每个i（(1 \leq i \leq n)），考虑两种情况：

  • m=0：仅走i步，未经过完整周期。有效位置需满足每个维度k的初始位置(s_k)满足(1 - L[i][k] \leq s_k \leq w[k] - R[i][k])，计数为各维度有效范围的乘积。
  • m≥1：经过m个完整周期后再走i步。此时每个维度k的位移范围为(L[i+mn][k] = L[i+n][k] + m \cdot tt[k])（若(tt[k] > 0)）或(R[i+n][k] + m \cdot tt[k])（若(tt[k] < 0)），有效位置数量是关于m的k次多项式，用拉格朗日插值计算其在有效m范围内的和。

• 累加结果：将所有i的贡献累加，得到总步数。

拉格朗日插值的应用

由于有效位置数量是关于m的k次多项式（k≤10），可通过以下步骤计算和：

1. 取(k+2)个点（(m=0,1,...,k+1)），计算多项式在这些点的值。
2. 用拉格朗日插值公式拟合多项式，再计算其在有效m范围内的和。

代码解析

1. 预处理：计算(tt[k])、(L[i][k])、(R[i][k])，存储前缀位移的最值。
2. 无限循环判断：检查各维度是否满足周期总位移为零且范围始终在场地内。
3. 有效位置计数：对每个i，计算m=0的贡献，再用拉格朗日插值计算m≥1的贡献，累加得总步数。

复杂度分析

• 时间复杂度：(O(nk + K^3))，其中n为路线步数，k为维度（k≤10）。预处理位移信息耗时(O(nk))，拉格朗日插值拟合k次多项式耗时(O(K^3))（K=k+2），整体高效。
• 空间复杂度：(O(nk + K^2))，存储位移信息和插值所需的逆元表。

示例说明（样例1）

• 输入：n=3，k=2，w=[3,3]，路线为(1,1)→(2,-1)→(1,1)。
• 周期总位移(tt[1] = 1+1=2)，(tt[2] = -1)（非零，无无限循环）。
• 对i=1（走1步），m=0时有效位置需满足维度1：(1 - 1 \leq s_1 \leq 3 - 1)（即1≤s₁≤2），维度2：(1 - 0 \leq s_2 \leq 3 - 0)（即1≤s₂≤3），计数为2×3=6，贡献6步。
• 累加所有i和m的贡献，总步数为21，与样例一致。

#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ul unsigned
#define ll long long
#define ull unsigned ll
#define db double
#define ldb long db
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pbI push_back
#define inf 1e18
#define mdI int mid=(l+r)>>1
#define lowbit(x) ((x)&(-(x)))
#define ppc(x) __builtin_popcount(x)
#define rep(a,b,c) for(signed a=b;a<=c;a++)
#define vep(a,b,c) for(signed a=b;a>=c;a--)
#define gint __int128
#define MOD 1000000007//998244353
#define MAXN 500010
int qread() {
    char o = getchar();
    int f = 1, x = 0;

    for (; !isdigit(o); o = getchar())
        if (o == '-')
            f *= -1;

    for (; isdigit(o); o = getchar())
        x = x * 10 + o - '0';

    return f * x;
}
void chmi(signed &x, signed y) {
    x = min(x, y);
}
void chmx(signed &x, signed y) {
    x = max(x, y);
}
void chmd(ll &x, ll y) {
    x = (x + y) % MOD;
}
ll qp(ll a, ll b, ll p = MOD) {
    ll bs = a, rs = 1;

    while (b) {
        if (b & 1)
            rs = rs * bs % p;

        bs = bs * bs % p;
        b >>= 1;
    }

    return rs;
}
bool FLA;
int n, K;
int w[11], tt[11], T[11];
signed L[MAXN << 1][11], R[MAXN << 1][11];
int c[MAXN], d[MAXN];
int b1[MAXN], k1[MAXN];
#define x1 genshin
#define y1 impact
int x1[MAXN], y1[MAXN];
int iv[12][12];//忘了K要+1，数组开大
ll Lagrange(int x) {
    ll ans = 0;
    rep(i, 0, K + 1) { //差点忘了K要+1，求和升次
        ll coe = y1[i];

        rep(j, 0, K + 1)if (j != i)
            coe = coe * (x - j + MOD) % MOD * iv[i][j] % MOD;

        chmd(ans, coe);
    }
    return ans;
}
bool FLB;
signed main() {
    cerr << ((&FLB) - (&FLA)) / 1024.0 / 1024 << endl;
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    cin >> n >> K;
    rep(i, 1, K)w[i] = qread();
    rep(i, 1, n) {
        c[i] = qread(), d[i] = qread();
        tt[c[i]] += d[i];
    }
    rep(i, 0, K + 1) {
        rep(j, 0, K + 1) {
            if (i != j)
                iv[i][j] = qp((MOD + i - j) % MOD, MOD - 2);
        }
    }
    rep(i, 1, 2 * n) {
        int j = (i - 1) % n + 1;
        T[c[j]] += d[j];
        rep(k, 1, K) {
            L[i][k] = min(L[i - 1][k], (signed)T[k]);
            R[i][k] = max(R[i - 1][k], (signed)T[k]);
        }
    }
    int ans = 0;
    rep(i, 1, n) {
        int coe = 1;
        rep(j, 1, K) {
            int V = w[j] - (R[i][j] - L[i][j] + 1) + 1;

            if (V <= 0)
                coe = 0;

            coe = coe * V % MOD;
        }
        chmd(ans, coe);
        int Fm = 1e10;
        rep(j, 1, K) {
            if (!tt[j]) {
                b1[j] = (w[j] - (R[i + n][j] - L[i + n][j] + 1) + 1);
                k1[j] = 0;
                continue;
            }

            int F = (w[j] - (R[i + n][j] - L[i + n][j] + 1) + 1) / abs(tt[j]);
            b1[j] = w[j] - (R[i + n][j] - L[i + n][j] + 1) + 1, k1[j] = abs(tt[j]);

            if (b1[j] < 0)
                Fm = -1;

            Fm = min(Fm, F);
        }

        if (Fm == 1e10) {
            puts("-1");    //小心忘记return 0，考场上自己一定要自己造数据，比如多测不换行惨案
            return 0;
        }

        if (Fm < 0)
            continue;

        /*
        从0始加到Fm,\prod (b1-k1x)
        显然直接上Lagrange更优
        */
        int Ans = 0;
        rep(j, 0, K + 1) {
            int coe = 1;
            rep(k, 1, K) {
                coe = coe * (b1[k] - k1[k] * j % MOD + MOD) % MOD;
            }
            chmd(Ans, coe);
            x1[j] = j, y1[j] = Ans;
        }
        chmd(ans, Lagrange(Fm));
        //rep(j,0,K){
        //    assert(Lagrange(j)==y1[j]);
        //}
        /*
        rep(j,0,Fm){
            int coe=1;
            rep(k,1,K){
                coe=coe*(b1[k]-k1[k]*j)%MOD;
            }
            chmd(ans,coe);
        }
        */
    }
    int coe = 1;
    rep(i, 1, K)coe = coe * w[i] % MOD;
    chmd(ans, coe);
    cout << ans;
}
/*
这就跟算两次是一样的，我们计算活到第i步的点数
这样子的好处就是维度可以分离了
考虑一个维度答案是多少
我们关心其占用长度
在大于第一个循环后
显然是等差数列。
*/