P7976 「Stoi2033」园游会

· · 题解

首先根据题意，这个题可以直接对每个数字取模后的杨辉三角进行前 n+1 行求和（因为第 1 行）后的结果正常情况 16 分跑路，53 分就需要一些优化了。

首先，根据经验（事实上推导一下也很简单），在常规杨辉三角中，第 n 行的和是 2^n，所以我们可以试一下在取模后的杨辉三角有没有类似的规律。

经过打表观察（下面有个小表），这个杨辉三角每一行的和也是 2 的某次方，只是次数不是线性增加的。

但是我们再仔细观察一下，我们发现可以把每 3 个数字分成一组，然后发现每个三元组 \{x, y, z\} 都会出现 y = x \times 2 = z \times 2 的情况，下面列举一部分（可以自己尝试打出前 100 的表，这样更容易发现规律）。

1 2 1 
2 4 2 
1 2 1 
2 4 2 
4 8 4 
2 4 2 
1 2 1 
2 4 2 
1 2 1

（表 1）

再小瞄一眼，就会发现，事实上，行与行之间也有相似的结论，即我们可以把第一行 3 个数字当做一个矩阵 A，然后第二行就是 2 \times A，以此类推，我们可以把之前的那个表每一行换成对应矩阵的倍数，如下：

1 
2 
1 
2 
4 
2 
1 
2 
1

（表 2）

再对他进行一定的变形

1 2 1 
2 4 2
1 2 1

（表 2）

我们可以惊奇地发现，这和之前原始那个表 2 的前 3 行完全一致，也就是说，我们可以猜测一下，后续都有相似的规律（读者可以自己打表试试）。

知道了规律就开始尝试实现一下，既然是 3 个一组进行层层递进，不难联想到 3 进制数，下面以 19 这一数据为例解释一下算法。

由于我们要求的是前 n + 1 行的和，所以我们要算出我们的数组中前 20 个数字的和。

首先，把 20 转换为 3 进制数，即 202。为了方便，我们把表 1 做对应的叫做第 1 层，表 2 所对应的叫做第 2 层。第 2 层里面每一个数对应的都是第 1 层里面的 3 个数，所以 202 中的首位上的 2 对应的就是第 3 层上的前两个数字的和，后两位数字对应的就是第三层中的第三个数字所对应的第二层的区域了，第二位上的 0 对应的就是第 2 层上的 0 个数字，而最后一位的 2 就对应的是第 2 层里面第一个数字所对应的数字之和了。

下面可以形象化的理解一下：

所以我们可以先预处理出每一行每个数字对应的基础权值（如，第一层的权值必然是 1 ，第二层的权值是 4，第三层的权值是 16）是多少，然后再乘上他的倍数，就可以算出答案。

我们再以 n = 34 为例。首先，把 n + 1 = 35 分解成 3 进制数。

然后第 4 层的基础权值是 64，第 1 个数是 1，所以第 4 层的值就是 1 \times 64，第 3 层同理，是 0，第 2 层同理，但是由于在第 4 我们是从第 2 个数字进来的，所以最后还需要乘一个 2 的倍数，所以就是 4 \times 3 \times 2 = 24，再看最后一层权值乘对应前缀和乘累计的倍数 1 \times 3 \times 2 \times 1 \times 1 = 6，就是最后一层的值。最后加和一下，就是答案了。

所以我们直接先分解 3 进制然后再计算就可以了。

上代码！（超短诶，简单易懂，建议配合样例数据食用）

#include<bits/stdc++.h>
using namespace std;
typedef long long lol;
typedef pair<int, int> pii;
typedef pair<int, lol> pil;
typedef pair<double, double> pdd;
typedef unsigned int uin;

const int mod = 1732073999, N = 305;
int t, f[3] = {1, 2, 1}, p[3] = {0, 1, 3}, l[N], idx;
lol maxn, n, ex[N];

int main () {
    scanf ("%d%lld", &t, &maxn);

    ex[1] = 1;
    for (int i = 2; i < N; ++ i ) 
        ex[i] = ex[i - 1] * 4 % mod;

    while (t -- ) 
    {
        scanf ("%lld", &n);
        lol ans = 0, x = 1;
        ++ n, idx = 0;
        while (n) 
            l[++ idx] = n % 3, n /= 3;
        for (int i = idx; i >= 1; -- i ) 
            ans = (ans + p[l[i]] * x * ex[i]) % mod, x = x * f[l[i]] % mod;
        printf ("%lld\n", ans);
    }
    return 0;
}