Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

NOIP2020 微信步数

Posted on

为了不让自己颓废，这篇博客必须写了。

Solution

首先考虑什么时候会是$-1$，手玩一下就会发现：$-1$只有一种情况会出现，就是当且仅当做完第一轮$n$次操作时没能将这个点弄死，并且回到了原点，这种情况比较好判断。

然后考虑有解的情况。

首先发现最多的情况下会有$10$维，这意味着我们直接枚举的复杂度大概在$nw^{10}$左右，这显然是不可能的，我们考虑拆贡献，我们首先将所有的点都拿出来，经行操作，每次贡献了之后将出界的点都删除，每一次贡献的值显然就是此时剩余的点的数量。

如果这样暴力维护的话大概会有$45pts$。

考虑优化，可以发现，中间有很大一部分的轮数（记$n$次操作为一轮，下同）它们所经历的删点的操作基本类似的，我们将第二次操作的情况拿出来，记第二轮第$j$维会死$b_j$个节点，第一轮结束后第$j$维还剩$a_j$个节点，令$T= \min_{i=1}^k\frac{a_i-f_i}{b_i}$，其中$f_i$是最后一轮（可能并不需要经行完，所以需要单独拎出来）剩余的点数。

这样答案就应该等于：
$$
\sum_{i=1}^n\sum_{x=0}^T\prod_{j=1}^ka_j-x\times b_j-f_j
$$
这个显然是不包括第一次和最后一次的贡献的。

我们将最后一项展开，这是一个关于$x$的$k$次多项式，将系数算出来即可，没有必要用多项式，$k$很小。

这样复杂度就是：$O(nm^2)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c){ putchar(c); }
template <>
inline void write(const char *s) { while(*s) putchar(*s ++); }
template<class T, class ...ARC>
inline void write(T res, ARC ...com){ write(res), write(com...);}
const int N = 5e5 + 5, K = 11, mod = 1e9 + 7, Inf = 0x3f3f3f3f;
struct Node{
    int l, r;
}seg[N][K];
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return res;
}
inline int calc(int x, int k) // 拉格朗日插值
{
    static int fac[N];
    int res = 0;
    if(x <= k + 2)
    {
        for(int i = 1;i <= x;i ++)
            res = (res + qpow(i, k)) % mod;
    }
    else{
        fac[0] = 1;
        for(int i = 1;i <= k + 1;i ++) 
            fac[i] = 1ll * fac[i - 1] * i % mod;
        int t = 1;
        for(int i = 1;i <= k + 2;i ++)
            t = 1ll * t * (x - i) % mod;
        int v0 = ((k + 2) & 1) ? 1 : -1;
        for(int i = 1, sum = 0;i <= k + 2;i ++)
        {
            sum = (sum + qpow(i, k)) % mod;
            res = (res + 1ll * v0 * sum * t % mod * qpow(x - i, mod - 2) % mod * qpow(1ll * fac[i - 1] * fac[k + 2 - i] % mod, mod - 2) % mod) % mod;
            v0 = -v0;
        }
        res = (res % mod + mod) % mod;
    }
    return res;
}
int n, k, c[N], d[N], sum[K];
int w[K], delta[K];
int v1[K], v2[K], val[K][K];
int ans = 0;
inline void solve1()
{
    for(int i = 1;i <= k;i ++)
        v1[i] = w[i] - (seg[n][i].r - seg[n][i].l);
    for(int i = 0, sum;i <= n;i ++)
    {
        sum = 1;
        for(int j = 1;j <= k;j ++)
            sum = 1ll * sum * max(0, w[j] - (seg[i][j].r - seg[i][j].l)) % mod;
        ans = (ans + sum) % mod;
    }
}
inline void solve2()
{
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= k;j ++)
        {
            seg[i][j].l = min(0, seg[i][j].l + delta[j] - seg[n][j].l);
            seg[i][j].r = max(0, seg[i][j].r + delta[j] - seg[n][j].r);
        }
    for(int i = 1;i <= k;i ++)
        v2[i] = seg[n][i].r - seg[n][i].l;
    int last = -1;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= k;j ++) val[0][j] = 0;
        val[0][0] = 1;
        int T = Inf;
        for(int j = 1;j <= k;j ++)
        {
            int x = v1[j] - (seg[i][j].r - seg[i][j].l);
            if(x <= 0) return ;
            if(v2[j] > 0) T = min(T, x / v2[j]);
            for(int K = 0;K <= k;K ++)
            {
                val[j][K] = 1ll * val[j - 1][K] * x % mod;
                if(K > 0) val[j][K] = (val[j][K] - 1ll * val[j - 1][K - 1] * v2[j] % mod) % mod;
            }
        }
        ans = (ans + 1ll * val[k][0] * (T + 1) % mod) % mod;
        if(T != last)
        {
            last = T;
            for(int j = 1;j <= k;j ++) sum[j] = calc(T, j);
        }
        for(int j = 1;j <= k;j ++)
            ans = (ans + 1ll * sum[j] * val[k][j] % mod) % mod;
    }
}
int main()
{
    read(n, k);
    for(int i = 1;i <= k;i ++) read(w[i]);
    for(int i = 1;i <= n;i ++)
    {
        read(c[i], d[i]);
        delta[c[i]] += d[i];
        for(int j = 1;j <= k;j ++) seg[i][j] = seg[i - 1][j];
        seg[i][c[i]].l = min(seg[i][c[i]].l, delta[c[i]]);
        seg[i][c[i]].r = max(seg[i][c[i]].r, delta[c[i]]);
    }
    bool flag = 0;
    for(int i = 1;i <= k;i ++)
        if(delta[i] != 0 || seg[n][i].r - seg[n][i].l >= w[i])
        {
            flag = 1;
            break;
        }
    if(!flag) return puts("-1"), 0;
    solve1();
    solve2();
    write((ans % mod + mod) % mod);
    return 0;
}