「S2OI Round 1」三叉求和

· · 题解

前言

评级建议：上位蓝或下位紫。

解法貌似跟官解并不一样。

思路

考虑拆贡献，对于节点 i 的儿子节点 3i+j，其对于路径剩余的点的贡献是固定的，依次为（令 3i+j 的深度为 k）：

j\cdot 3^0, j\cdot 3^1, \dots, j\cdot 3^{d-k}

原因是简单的，因为 a_{3i+j}=3a_i+j，那么设之前对 i 的贡献为 b_i，则如今对 3i+j 的贡献为 3b_i。

由于，要求对于路径上所有点的权值和为 k，只需要将每个点对 路径上剩余点的贡献的和 加和。

而每个点对路径上剩余点的贡献的和可通过等比数列求和公式进一步化简：

\begin{align*} S &= j\cdot 3^0+ j\cdot 3^1+ j\cdot 3^2+ \dots+ j\cdot 3^{d-k}\\ 3S &= \qquad\quad\ j\cdot 3^1+ j\cdot 3^2+ \dots+ j\cdot 3^{d-k}+j\cdot 3^{d-k+1}\\ S &= j\cdot \frac{3^{d-k+1}-1}{2} \end{align*}

设路径经过的点选择的儿子节点分别为 q_1,q_2,\dots,q_{d}（\forall i \in [1,d], q_i\in [0,3)），则限制为

\begin{align*} k &= \sum_{i=1}^{d} q_i \frac{3^{d-i+1}-1}{2}\\ 2k &= \sum_{i=1}^{d} q_i 3^{d-i+1}-q_i\\ 2k+\sum_{i=1}^{d} q_i &= \sum_{i=1}^{d} q_i 3^{d-i+1}\\ \end{align*}

令 S=\sum_{i=1}^{d} q_i，则等价于 2k+S 在三进制下的各数位之和为 S。

问题转化为对于 S\in [1,2d]，k 有多少种赋值方式，使得 2k+S 在三进制下的各数位之和为 S。

这是容易 DP 的！枚举 S，然后令 f_{i,j,k} 表示前 i 位，2k+S 在三进制下数位之和为 j，进位为 k。这里 k\in[0,2]，因为 S 每位最大为 2，2k 每位最大为 4，k 最大为 2，和为 8，进位仍为 2。

转移是 O(1) 的，但是状态是 O(n^2)，外层还需枚举 S。总复杂度为 O(n^3)，期望得分 70。

考虑如何去掉外层的枚举，不难发现，在这个转移中 S 是可以加入状态第二维的。

令 f_{i,j,k} 表示前 i 位，2k+S 在三进制下的数位之和减去 S 为 j，进位为 k。转移时，只需要额外枚举 S 在第 i 位为 0/1/2 即可。

时间复杂度 O(n^2)，期望得分 100。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using i64 = long long;
using pii = pair<int, int>;

const int maxn = 2005, mod = 1e9 + 7;

int n;
string s;
int dp[2][14005][3], pw[maxn];

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> s;
    reverse(s.begin(), s.end());
    while (s.size() < max(8, n + 1)) s += '0';

    pw[0] = 1;
    for (int i = 1; i < 8; i ++)
        pw[i] = pw[i - 1] * 3;

    memset(dp, 0, sizeof dp);
    dp[1][7000][0] = 1;
    for (int i = 0; i < s.size(); i ++) {
        for (int j = 0; j <= 7000 + i * 2; j ++)
            for (int k : {0, 1, 2}) dp[i & 1][j][k] = 0;
        for (int j = 0; j <= 7000 + i * 2; j ++)
            for (int k : {0, 1, 2}) {
                if (!dp[~i & 1][j][k]) continue;
                for (int t : {0, 1, 2}) {
                    if (s[i] != '?') {
                        int u = 2 * (s[i] - '0') + t + k;
                        if (u % 3 && (!i || i > n) || i >= 8 && t) continue;
                        (dp[i & 1][j + u % 3 - t * pw[i]][u / 3] += dp[~i & 1][j][k]) %= mod;
                    } else {
                        for (int o : {0, 1, 2}) {
                            int u = 2 * o + t + k;
                            if (u % 3 && (!i || i > n) || i >= 8 && t) continue;
                            (dp[i & 1][j + u % 3 - t * pw[i]][u / 3] += dp[~i & 1][j][k]) %= mod;
                        }
                    }
                }
            }
    }

    cout << dp[~s.size() & 1][7000][0] << endl;

    return 0;
}