CF1967C题解

标签：下标 CF1967C 题解 long int 节点 dp define

CF1906D

这里更容易进入且有翻译

题意

对于数组 \(a\)，有函数 \(f(a)\)，设数组 \(s = f(a)\)，则对于每一个 \(s_i\)，都有：

\[s_i = \left(\sum^{i}_{j = (i \operatorname{\& } (i - 1)) + 1}{a_j}\right) \]

其中 \(\&\) 表示按位与运算。

对于一个正整数 \(k\)，函数 \(f^k(a)\) 定义如下：

\[ f^k(a)= \begin{cases} f(a)&k=1\\\\ f(f^{k-1}(a))&k > 1 \end{cases}\]

给你正整数 \(n, k\) 和一个长度为 \(n\) 的数组 \(b\) 表示 \(f^k(a)\)，求一个符合题意的数组 \(a\)，可以证明答案总是存在的。

解析

理解题意便可以看出，各个下标数值之间的关系形成一片森林，下标 \(\operatorname{lowbit}\) 值（二进制形式下数字为 1 的最低数位对应值，如 \(\operatorname{lowbit}(12) = 4\)）越小，其对应节点在树上深度越大。明显每个 \(a_i\) 仅对其自身和在该树上的祖先有贡献，且对自身的贡献为 1，对其有贡献的仅有自身及其后代。

打表可看出对于下标 \(i\) 和其祖先 \(j\)，贡献 \(c_{i, j}\) 的大小仅与下标 \(i, j\) 在树上的节点深度差有关，我们可以预处理在 \(k\) 次函数计算后不同深度差下后代节点对祖先节点的贡献。设 \(dp_{i, j}\) 表示深度差为 \(i\) 时进行在 \(f^j(a)\) 中后代节点对祖先节点的贡献。初始时除了 \(dp_{1, 0} = 1\)，其余 \(dp_{i, j} = 0\), 有转移方程：

\[dp_{i, j} = \sum_{l = 1}^{i}{dp_{l, j - 1}} \]

由于 \(k\) 较大但 \(i\) 的范围较小，我们可以考虑通过矩阵加速优化计算 \(dp_{i, k}\) 的过程。

预处理完贡献值后，自底向上倒推，在祖先节点中减去当前节点的贡献，最后该祖先节点 \(i\) 保留的值就是原本 \(a_i\) 的值。复杂度大概为 \(O({\log}^3{n} \log{k} + n\log{n})\)

代码

#include <bits/stdc++.h>
#include <unordered_map>
#define LL long long
#define ll long long
#define double long double
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pdd pair<double, double>

using namespace std;

//nxt数组用于记录下标的父节点下标，N为矩阵大小
LL a[200005], b[200005], pre[25][25], nxt[200005], N, mod = 998244353;

//矩阵加速
void mqpow(int n)
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            pre[i][j] = (i == j);

    LL M[25][25], cur[25][25];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            M[i][j] = (i >= j);

    while (n)
    {
        if (n & 1)
        {
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    cur[i][j] = 0;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    for (int k = 1; k <= N; k++)
                        cur[i][j] = (cur[i][j] + pre[i][k] * M[k][j] % mod) % mod;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    pre[i][j] = cur[i][j];
        }
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                cur[i][j] = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                for (int k = 1; k <= N; k++)
                    cur[i][j] = (cur[i][j] + M[i][k] * M[k][j] % mod) % mod;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                M[i][j] = cur[i][j];

        n >>= 1;
    }
}

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

    //预处理nxt数组
    for (int i = 1; i <= 200000; i++)
    {
        int idx = 0, cur = i;
        while (!(cur & (1 << idx)))
            cur |= 1 << idx++;
        while (cur & (1 << idx))
            idx++;
        nxt[i] = cur ^ ((1 << (idx + 1)) - 1);
    }

    int T, n;
    LL k;
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        N = log2(n) + 1;
        for (int i = 1; i <= n; i++)
            cin >> b[i];

        mqpow(k); //预处理深度差产生的贡献系数
        for (int i = 1; i <= N; i++)
            for (int j = 1; j * (1 << (i - 1)) <= n; j += 2) //从叶子节点（lowbit值为1下标）开始倒推
            {
                int cur = j * (1 << (i - 1));
                a[cur] = b[cur]; //节点保留值即为答案
                for (int l = nxt[cur], m = 2; l <= n; l = nxt[l], m++)
                    b[l] = (b[l] + mod - a[cur] * pre[m][1] % mod) % mod; //从祖先节点中减去当前节点的贡献
            }

        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << "\n";
    }
}

最后祝各位顺利AC。>w<

标签：下标,CF1967C,题解,long,int,节点,dp,define
From： https://www.cnblogs.com/ItsAiHAn/p/18180069