0606

Cap1taL · 2025-06-06 19:34:57 · 个人记录

NFLS T2 (AT_arc128_f)

有 N 张编号为 1 到 N 的卡片。第 i 张卡片上写着整数 A_i。这里，N 是偶数。

Snuke 和 Robot 将玩一个游戏，规则如下。

游戏主宣布一个排列 (p_1,p_2,\cdots,p_N)，给 Snuke 和 Robot。
然后，Snuke 和 Robot 轮流进行，Snuke 先开始。每个回合的规则如下。
- Snuke 的回合：选择一张剩余卡片并烧掉。
- Robot 的回合：选择具有最大 p_i 的卡片 i 并烧掉。
当没有卡片剩余时游戏结束。

游戏的最终得分是 Snuke 吃掉的卡片上整数的总和。Snuke 将以最佳方式玩以最大化得分。

有 N! 个排列 p 的 (1,2,\cdots,N)。找到所有这些排列的最终得分总和，模 998244353。

1 \leq N \leq 10^6
1 \leq A_i \leq 10^9
All values in input are integers.

NFLS 还要求支持动态修改 A_i

题解

好题，学到很多

先不考虑动态修改 a_i

为方便令 n\leftarrow \frac{n}{2}

首先发现我们可以把每个 a_i 的贡献拎出来。

具体地，若 a_i 在 (2n)! 个排列中的 X 个里被烧掉了，那么显然它贡献的得分是 a_iX

同时我们发现这样一来我们不关心 a_i 是什么了，我们只关心相对大小关系

于是，如果能求出 f_i 表示第 i 大的数被用掉的排列数量，对 a 降序排序，答案显然就是 \sum_{i=1}^{2n}f_ia_i，这样修改也是好做的。

问题转化成如何求出 f_i

值域是 2n 还是太难做了，考虑求出前 k 大的数被用掉的总次数 g_k=\sum_{i=1}^kf_i

这样一来，我们可以把所有 \ge k 的数看作 1，把所有 \lt k 的数看作 0，转变成了一个 01 问题，g_k 就等于对于所有含有 k 个 1 且长度为 2n 的 01 序列做上述游戏，被 Snuke 选中的 1 的总数。同时我们不关心 01 内部的具体数值，因此 g_k 还要乘上 k!(2n-k)!

对式子的推导暂时到头了，现在我们需要来挖掘这个游戏的性质。容易发现前 2 个数里 Snuke 最多选 1 个，前 4 个里最多选 2 个，以此类推，前 2i 个数里最多选 i 个。如果把 Snuke 选择的数看作 -1，没选的看作 +1，那我们需要保证所有前缀和均不小于 -1。

然而这样还是太抽象了，一个思路是倒着考虑后缀限制。为了第 i 个选择的数的前缀和合法，它前面必须不选至少 i-1 个数。因此第 i 个数的选择范围是 [2i-1,n]。

所以我们对于一个确定的 01 序列有了一个确定的算法来求出会选几个 1

每 2 个 01 打包，不妨设每包有 c_i 个 1，则一共有 n 个包，\sum_i^nc_i=k
倒着从 n 到 1 遍历 i
先累加 cnt_1\leftarrow cnt_1+c_i
根据上面的结论，现在我们不得不取一个数。尝试 cnt_1 是否大于 0，如果是就可以取一个 1，否则就得取 0 了。

枚举所有 01 现在就可以做到 O(2^{2n}n) 的时间求出 g_k 了，比 O(n!) 好多了。我们尝试进一步优化

追踪 cnt_1 的变化，每次操作相当于 cnt_1\leftarrow\max(0,cnt_1+c_i-1)。我们把它搬到平面网格上。

转化成：

起始位于 (0,0)
每次可以向右上、右、右下三个方向前进（分别对应 c_i-1 等于 \{-1,0,1\}）
一共走 n 步
向右的方案系数是 2（对应 c_i=1，此时包内方案有 01 和 10 两种）
向右上、右下的方案系数是 1
如果走到了 x 轴下方，我们强行向上回到 x 轴，并称这一步 "失败"（对应无法从 cnt_1 中取 1 的情况）
否则，我们称这一步 "成功 "（对应从 cnt_1 中取 1 的情况）

这样一来，每条路径都对应了一种 cnt_1 的变化序列。这个变化序列所对应的 01 序列数量就是每步的方案系数乘积，取出 1 的数量就是 "成功" 的步数。

~~因此现在可以枚举所有路径，可能比 2^{2n}n 要快一些~~

这一步转化其实很有意思。

枚举的是所有 01 序列
根据每个 01 序列来计算一系列 cnt_1 的变化
根据 cnt_1 的变化来求出我们取了多少 1

我们需要的只是最后的答案，而 01 序列和 cnt_1 的变化并非一一对应，而是多对一的关系。这一步转化使得我们不必再枚举 01 序列，转而考虑更好刻画的 cnt_1 变化问题——我们把后者成功放到了网格图上考虑，更直观了

现在要继续进一步优化。这个低于 x 轴拉回的限制太抽象了，考虑直接不拉回会怎么样。容易发现，被拉回的步数等价于不拉回时的最小值。于是变成：

起始位于 (0,0)
每次可以向右上、右、右下三个方向前进（分别对应 c_i-1 等于 \{-1,0,1\}）
一共走 n 步
终点必须是 (n,k-n)（因为 \sum_{i=1}^nc_i=k，所以向上总贡献是 k，向下总贡献是 n，落点在 k-n）
向右的方案系数是 2（对应 c_i=1，此时包内方案有 01 和 10 两种）
向右上、右下的方案系数是 1
对应的 01 序列数量就是每步的方案系数乘积
设走过的最小值为 L，则取出 1 的数量就是 n+L
这个路径对 g_k 的贡献是 k!(2n-k)!(n+L)(每步方案系数乘积)

如果在给定 n,k,L 的情况下，我们能快速计算所有路径的方案系数乘积之和，我们就做完了。不妨设其为 S(n,k,L)

钦定最小值是 L 不好考虑，我们尝试对于最小值 \ge L 的路径求出答案后差分，设其为 F(n,k,L)

为了解决掉这个最小值 \ge L 的限制，可以利用折线法做一个小容斥。

设不限制最小值时的答案为 G(n,k)，即从 (0,0) 按刚才的方法走到 (n,k-n) 的所有路径的方案系数乘积之和。我们需要从这里面去掉最小值 \lt L 的路径的答案。

对于每个最小值 \lt L 的路径，它一定会经过 y=L-1 这条直线。找到它第一次访问 y=L-1 的点，称其为 P，我们沿 y=L-1 对陈路径在 P 后的部分，终点变为 (n,2(L-1)-(k-n))。我们发现，所有从 (0,0) 到新终点的路径都对应一条原问题的非法路径。证明可以直接考虑翻转回去。

于是 F(n,k,L)=G(n,k)-G(n,2L+2n-k-2)

问题最后变成怎么快速计算 G(n,k)。事实上我们要计算的是

[x^{k-n}](x^{-1}+2+x)^n

很巧妙的一个式子，每步的选择变为了多项式每项的选择，纵坐标转化成了 x 的幂次，方案系数转化为了 x 的系数。

[x^{k-n}](x^{-1}+2+x)^n=[x^{k-n}]x^{-n}(1+2x+x^2)^n\\ =[x^{k}](1+2x+x^2)^n\\ =[x^{k}](x+1)^{2n}\\

我趣，二项式定理

G(n,k)=[x^{k-n}](x^{-1}+2+x)^n=[x^{k}](x+1)^{2n}={2n\choose k}

F(n,k,L)=G(n,k)-G(n,2L+2n-k-2)={2n\choose k}-{2n\choose 2L+2n-k-2}={2n\choose k}-{2n\choose k+2-2L}

S(n,k,L)=F(n,k,L)-F(n,k,L+1)={2n\choose k-2L}-{2n\choose k+2-2L}

那很爽了，我们可以计算 g_k

g_k=k!(2n-k)!\sum_{L=-n}^{\min(k-n,0)}(n+L)S(n,k,L)\\ =k!(2n-k)!\sum_{L=-n}^{k-n}(n+L)\left({2n\choose k-2L}-{2n\choose k+2-2L}\right)\\

注意 L 的取值范围。L\le 0 显然，L\le k-n 是因为 n+L 需要 \le k，因为一共只有 k 个 1，不能选更多了。

后面推式子部分是简单的。注意到 \sum_L 内是一个相减的形式，刚好可以随着 L 增加两两抵消，最后做个前缀和就可以了。

修改的部分也是简单的。因为修改的差值很小，考虑每次给 a_x+1 怎么做，发现只有 O(1) 个变化，暴力做就可以了。总复杂度 O(n+q|y|)

int fac[5000001];
int inv[5000001];
int C(int n,int m){
    if(n<m) return 0;
    return mul(fac[n],inv[m],inv[n-m]);
}
int g[MAXN];
int f[MAXN];
int G(int n,int k){
    return C(2*n,k);
}
int F(int n,int k,int L){
    return rmv(G(n,k),G(n,2*(L-1)-(k-n)+n));
}
int S(int n,int k,int L){
    return rmv(F(n,k,L),F(n,k,L+1));
}

int n,q;
int a[MAXN];
void gen(){
    static int c[5000005];
    static int s[5000005];
    foru(i,0,2*n){
        c[i]=C(2*n,i);
    }
    s[0]=c[0],s[1]=c[1];
    foru(i,2,5*n){
        s[i]=add(s[i-2],c[i]);
    }
    auto qry=[](int l,int n)->int {
        int ret=s[l+2*(n-1)];
        if(l>=2)    mmv(ret,s[l-2]);
        return ret;
    };
    foru(k,1,n){
        mdd(g[k],mul(n,C(2*n,2*n-k)));
        mmv(g[k],mul(n,C(2*n,2*n+k+2)));
        mmv(g[k],mul(n-k,C(2*n,2*(n-k)+k)));
        mdd(g[k],mul(n+1,C(2*n,2*(n+1)+k)));
        mmv(g[k],qry(k+2*(n-k+1),(n+1)-(n-k+1)+1));
        // foru(L,n-k+1,n+1){
        //  mmv(g[k],c[2*L+k]);
        // }
        mll(g[k],fac[k],fac[2*n-k]);
    }
    foru(k,n+1,2*n){
        mdd(g[k],mul(n,C(2*n,k)));
        mmv(g[k],mul(n,C(2*n,2*n+k+2)));
        mmv(g[k],mul(0,C(2*n,2*(0)+k)));
        mdd(g[k],mul(n+1,C(2*n,2*(n+1)+k)));
        mmv(g[k],qry(2+k,n));
        // foru(L,1,n+1){
        //  mmv(g[k],c[2*L+k]);
        // }
        mll(g[k],fac[k],fac[2*n-k]);
    }
    foru(i,1,2*n){
        f[i]=rmv(g[i],g[i-1]);
    }
}

void solve(bool SPE){ 
    n=RIN/2,q=RIN;
    foru(i,1,2*n){
        a[i]=RIN;
    }

    fac[0]=1;
    foru(i,1,5000000){
        fac[i]=mul(fac[i-1],i);
    }
    inv[5000000]=qpow(fac[5000000],mod-2);
    ford(i,5000000-1,0){
        inv[i]=mul(inv[i+1],i+1);
    }

    gen();

    int ans=0;
    static int b[MAXN];
    foru(i,1,2*n){
        b[i]=a[i];
    }
    sort(b+1,b+1+2*n,[](int x,int y)->bool {
        return x>y;
    });
    foru(i,1,2*n){
        // cerr<<b[i]<<end
        mdd(ans,mul(f[i],b[i]));
    }

    static pair<int,int> rg[1000005];
    foru(i,1,1000000){
        rg[i]={INT_MAX,INT_MIN};
    }
    foru(l,1,2*n){
        int r=l;
        while(r+1<=2*n && b[r+1]==b[l]){
            r++;
        }
        // cerr<<b[l]<<' '<<l<<' '<<r<<endl;
        rg[b[l]]={l,r};
        l=r;
    }

    auto PUSH=[&ans](int x,int rk)->void {
        assert(rg[x].fi==INT_MAX || rg[x].fi-1==rk || rg[x].se+1==rk);
        mdd(ans,mul(f[rk],x));
        chkmax(rg[x].se,rk);
        chkmin(rg[x].fi,rk);
    };
    auto POP=[&ans](int x,bool L)->void {
        assert(rg[x].fi!=INT_MAX);
        if(L){
            mmv(ans,mul(f[rg[x].fi],x));
            rg[x].fi++;
        }else{
            mmv(ans,mul(f[rg[x].se],x));
            rg[x].se--;
        }
        if(rg[x].fi>rg[x].se)   rg[x]={INT_MAX,INT_MIN};
    };
    auto ADD=[&](int x)->void {
        // cerr<<"ADD "<<rg[x].fi<<' '<<rg[x].se<<endl;
        assert(rg[x+1].se==INT_MIN || rg[x+1].se+1==rg[x].fi);
        assert(rg[x].fi!=INT_MAX);
        PUSH(x+1,rg[x].fi);
        POP(x,true);
    };
    auto RMV=[&](int x)->void {
        // cerr<<"RMV "<<rg[x].fi<<' '<<rg[x].se<<endl;
        PUSH(x-1,rg[x].se);
        POP(x,false);
    };

    auto out=[]()->void {
        cerr<<"OP"<<endl;
        foru(i,1,1000000){
            if(rg[i].fi==INT_MAX)   continue;
            cerr<<i<<' '<<rg[i].fi<<' '<<rg[i].se<<endl;
        }
    };
    // out();

    while(q--){
        int x=RIN,y=RIN;
        if(y>0){
            foru(i,a[x],a[x]+y-1){
                // cerr<<i<<endl;
                // assert(1<=i && i<=999999);
                ADD(i);
            }
        }
        if(y<0){
            ford(i,a[x],a[x]+y+1){
                // cerr<<i<<endl;
                // assert(2<=i && i<=1000000);
                RMV(i);
            }
            // exit(1);
        }
        a[x]+=y;
        printf("%d\n",ans);
        // out();
    }

    return ;
}

这题有几个关键的步骤

提取出 a_i，发现只需要求出 f_k，同时在这之后的修改也是简单的。
针对第 k 大求 f_k 困难，转化成最前 k 大求 g_k，此时可以把序列变成 01，只关心一个数是否属于前 k 大，是从 n! 变为 2^n 的关键一步。
- 实际上如果不追求进一步优化，对 f_k 也可以用类似的思路？k 变为 1，所有比它大的变为 2，比他小的是 0，也可以减小枚举量。但进一步优化会很抽象，不如 01 序列更好考虑了。
在 01 序列上运行算法，发现 01 序列与最为关键的 cnt_1 的变化不是一一对应关系，而是多对一的关系。枚举量进一步缩小到只枚举到 cnt_1 的变化路径
对困难的 \max(0,cnt_1+c_i-1) 做转化，变为了更好考虑的 cnt_1 最小值
差分，需要计算最小值为 L 的答案，转为计算最小值 \ge L 的答案
折线法进一步转化
处理组合数

比赛的时候死在第二步了😰️练过这种题以后应该就好一些了