[ABC251Ex] Fill Triangle Solution

更好的阅读体验戳此进入

题面

存在序列 $a_n$$a_n$，将其压缩后给定。具体地，给定序列 $P$$P$ 以如下形式：$((a_1,c_1),(a_2,c_2),\cdots ,(a_m,c_m))$$((a_1, c_1), (a_2, c_2), \cdots, (a_m, c_m))$，表示序列 $a$$a$ 中有 $c_1$$c_1$ 个 $a_1$$a_1$，$c_2$$c_2$ 个 $a_2$$a_2$，以此类推，且按序拼接。令序列 $a_n$$a_n$ 为三角金字塔 $B$$B$ 的第 $n$$n$ 层，即 $B(n,i)=a_i$$B(n, i) = a_i$。特别地，该三角金字塔的递推式为 $B(i,j)=(B(i+1,j)+B(i+1,j+1))mod7$$B(i, j) = (B(i + 1, j) + B(i + 1, j + 1)) \bmod{7}$。给定 $k$$k$，求该三角金字塔第 $k$$k$ 层的序列。

Solution

首先可以尝试随意给定一个序列 $a_n$$a_n$ 并打表，或手推一下，假设 $n=5$$n = 5$，有：

不难发现这玩意每一项实际上就是二项式系数，或者说杨辉三角。并且还能发现，对于每一行的元素，它们的系数均相同，不同的只是将下标整体向右平移了一位。

此时我们便可以根据这个性质，求出对于第 $k$$k$ 层，第 $x$$x$ 列的元素，有：

显然我们想要算出 $k$$k$ 层的所有元素，但是直接套这个式子暴力算是肯定过不了的。考虑优化。

显然序列 $a$$a$ 是由一段一段的相同元素构成的，而我们的查询就是在 $a$$a$ 里的查询一个区间然后按序将组合数乘上去。当我们从 $B(k,x)$$B(k, x)$ 到 $B(k,x+1)$$B(k, x + 1)$ 的时候，通过我们之前的结论可知需要将下标向右平移一位，而所有组合数的值不变，大概的过程如图：

观察发现，这个东西平移之后，对于大多数的 $(\genfrac{}{}{0ex}{}{n-k}{i})\times a_{x+i}$${n - k \choose i} \times a_{x + i}$ 变成 $(\genfrac{}{}{0ex}{}{n-k}{i})\times a_{x+i+1}$${n - k \choose i} \times a_{x + i + 1}$，都存在 $a_{x+i}=a_{x+i+1}$$a_{x + i} = a_{x + i + 1}$，而对于这些的贡献是完全不变的。不难想到这个变化操作的复杂度最多是 $O(m)$$O(m)$ 的。所以当我们确定了 $B(k,1)$$B(k, 1)$ 之后，后面的 $B(k,2)$$B(k, 2)$ 到 $B(k,k)$$B(k, k)$ 就都可以每次 $O(m)$$O(m)$ 求解，故这步的复杂度优化为 $O(mk)$$O(mk)$。

具体地当我们移动询问区间的时候，遍历所有段，如果某一段的右端点在当前区间内，那么显然指向这一段的组合数会移动到下一段中，所以需要减掉前面的加上现在的。注意移动这步实际上是 $O(mk\log n)$$O(mk \log n)$ 的，而且这只 $\log$$\log$ 不小，所以会 TLE，则我们考虑预处理 Lucas。显然直接预处理 ${10}^9$$10^9$ 范围肯定不行，于是这里有个高妙的思路，我们本身的模数为 $7$$7$，那么我们可以先让值对 $7^k$$7^k$ 取模，然后再对 $7$$7$ 取模，这个显然是等价的。而如果我们搞一个 ${10}^5$$10^5$ 左右的 $7^k$$7^k$ 的话，那么一步 Lucas 之后需要求的组合数就都在 ${10}^5$$10^5$ 以内了，所以这个时候我们只需要预处理 ${10}^5$$10^5$ 以内的组合数，那么对于每次求 Lucas 直接拆一次但是不递归，直接查值乘起来取模即可，这样复杂度就是 $O(1)$$O(1)$ 了，或者说 $O(2)$$O(2)$，于是复杂度会变成 $O(mk)$$O(mk)$。同时不难发现，存在 $ $

于是现在的问题就仅剩如何求 $B(k,1)$$B(k, 1)$，也就是求：

首先还是考虑之前的思路，一定会有很多段的相同的 $a$$a$，假设我们存在一段 $[l,r]$$[l, r]$ 满足 $\mathrm{\forall }i\in [l,r),a_i=a_{i+1}$$\forall i \in [l, r), a_i = a_{i + 1}$，那么显然此处的值即为：

所以这个东西显然需要快速处理一段组合数，可以考虑做一个组合数的前缀和，这样即可 $O(1)$$O(1)$ 查询一段组合数的求和，然后乘上 $a_l$$a_l$ 即可，这样每次的复杂度也就是 $O(m)$$O(m)$ 了。当然我们肯定不能对于 $n-k$$n - k$ 以内的每个数求前缀和，所以可以对 $m$$m$ 段相同的分别求出对应的前缀和，然后查询即可。求的时候前面段的直接求和，最后剩下的不足一段的单独计算即可。

于是现在问题再次转化为如何快速求这种形式的组合数前缀和，可以参考该题：LG-P4345 [SHOI2015]超能粒子炮·改。

具体地，对于求 $F(n,k)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})modp$$F(n, k) = \sum_{i = 0}^k {n \choose i} \bmod p$，且 $p$$p$ 为质数，可以尝试通过 Lucas 进行处理（后面的式子最终都需要取模，这里省略）：

然后发现对于前面的 $\lfloor {\displaystyle \frac{i}{p}}\rfloor$$\lfloor \dfrac{i}{p} \rfloor$，这个就是个数论分块，也可以按照这个思想，将原式化为：

然后继续转化：

此时对比我们之前设的 $F(n,k)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})modp$$F(n, k) = \sum_{i = 0}^k {n \choose i} \bmod p$，所以原式可以再次化为：

然后我们只要随便与处理一下 $p$$p$ 以内的 $F$$F$，这样 $F(nmodp,p-1)$$F(n \bmod{p}, p - 1)$ 和 $F(nmodp,kmodp)$$F(n \bmod{p}, k \bmod{p})$ 即可 $O(1)$$O(1)$ 查表，然后组合数直接用 Lucas 暴力算一下即可，对于 $F(\lfloor {\displaystyle \frac{n}{p}}\rfloor ,\lfloor {\displaystyle \frac{k}{p}}\rfloor -1)$$F(\lfloor \dfrac{n}{p} \rfloor, \lfloor \dfrac{k}{p} \rfloor - 1)$ 递归下去即可。

考虑这个东西的复杂度，用主定理推导一下即可：

$O(n)$$O(n)$ 处理一下组合数，则 $f(n)$$f(n)$ 的复杂度只有 Lucas 的一只 $\log$$\log$，所以最终这里单次求解的复杂度为 $O({\log }^{2}n)$$O(\log^2 n)$，然后我们要处理 $m$$m$ 个，则最终这步的复杂度为 $O(m{\log }^{2}n)$$O(m \log^2 n)$。最终复杂度为 $O(mk+m{\log }^{2}n+k\log n)$$O(mk + m \log^2 n + k \log n)$，显然能过。

至此我们就终于完成了这道题。

Code

xxxxxxxxxx
115
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (7)
23
#define SPL (117649) //7^6
24

25
template < typename T = int >
26
inline T read(void);
27

28
int f[10][10];
29
int N, M, K;
30
int origin(0);
31
int sumf[210];
32
int lucas_div[SPL + 10], lucas_mod[SPL + 10];
33
struct Blk{int l, r; int val;} blk[210];
34

35
int qpow(int a, int b){
36
    int ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43
int fact[10], inv[10];
44
void Init(void){
45
    fact[0] = 1;
46
    for(int i = 1; i < MOD; ++i)fact[i] = fact[i - 1] * i % MOD;
47
    inv[MOD - 1] = qpow(fact[MOD - 1], MOD - 2);
48
    for(int i = MOD - 2; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
49
}
50
int GetC(int n, int m){
51
    if(n < m)return 0;
52
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
53
}
54
int Lucas(ll n, ll m){
55
    if(n < MOD && m < MOD)return GetC(n, m);
56
    return Lucas(n / MOD, m / MOD) * GetC(n % MOD, m % MOD) % MOD;
57
}
58
int O1Lucas(ll m){
59
    return (lucas_div[m / SPL] * lucas_mod[m % SPL]) % MOD;
60
}
61
void InitF(void){
62
    for(int i = 0; i <= MOD - 1; ++i)f[i][0] = f[0][i] = 1;
63
    for(int i = 1; i <= MOD - 1; ++i)
64
        for(int j = 1; j <= MOD - 1; ++j)
65
            f[i][j] = (f[i][j - 1] + Lucas(i, j)) % MOD;
66
}
67
int F(ll n, ll k){
68
    if(n < 0 || k < 0)return 0;
69
    if(n < MOD && k < MOD)return f[n][k];
70
    return (f[n % MOD][MOD - 1] * F(n / MOD, k / MOD - 1) % MOD + Lucas(n / MOD, k / MOD) * f[n % MOD][k % MOD] % MOD) % MOD;
71
}
72

73
int main(){
74
    Init(), InitF();
75
    N = read(), M = read(), K = read();
76
    for(int i = 0; i <= SPL; ++i)lucas_div[i] = Lucas((N - K) / SPL, i), lucas_mod[i] = Lucas((N - K) % SPL, i);
77
    int curl(1);
78
    for(int i = 1; i <= M; ++i)blk[i].val = read(), blk[i].l = curl, blk[i - 1].r = blk[i].l - 1, curl += read();
79
    blk[M].r = N; int lim = N - K + 1;
80
    for(int i = 1; i <= M; ++i)
81
        sumf[i] = (F(N - K, blk[i].r - 1) - F(N - K, blk[i].l - 2) + MOD) % MOD;
82
    for(int i = 1; i <= M; ++i){
83
        int l = blk[i].l, r = blk[i].r;
84
        if(l > lim)break;
85
        if(r <= lim)(origin += sumf[i] * blk[i].val % MOD) %= MOD;
86
        else (origin += (F(N - K, lim - 1) - F(N - K, l - 2) + MOD) % MOD * blk[i].val % MOD) %= MOD;
87
    }printf("%d ", origin);
88
    int cl = 1, cr = lim;
89
    for(int i = 2; i <= K; ++i){
90
        for(int m = 1; m <= M; ++m){
91
            int r = blk[m].r;
92
            if(cl <= r && r <= cr)
93
                origin = (origin - O1Lucas(r - cl) * blk[m].val % MOD + O1Lucas(r - cl) * blk[m + 1].val % MOD + MOD) % MOD;
94
        }++cl, ++cr;
95
        printf("%d ", origin);
96
    }printf("\n");
97
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98
    return 0;
99
}
100

101
template < typename T >
102
inline T read(void){
103
    T ret(0);
104
    int flag(1);
105
    char c = getchar();
106
    while(c != '-' && !isdigit(c))c = getchar();
107
    if(c == '-')flag = -1, c = getchar();
108
    while(isdigit(c)){
109
        ret *= 10;
110
        ret += int(c - '0');
111
        c = getchar();
112
    }
113
    ret *= flag;
114
    return ret;
115
}

UPD

update-2022_12_02 初稿