自动搬运

查看原文

来自洛谷，原作者为

	ljc1301 两个引理，两个故事

搬运于2025-08-24 22:11:07，当前版本为作者最后更新于2019-07-20 10:31:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是个结论题……而且结论还很好猜……

可以观察，$n$那么大，而刚开始只有$f(i)=i$和$f(i)=i^2$，可以猜一个结论：

一次函数洗牌之后的期望还是一次函数，二次函数洗牌之后的期望还是二次函数。

而洗牌两次后的期望，和用洗牌一次后的期望作为权值，再洗第二次牌得到的期望，结果应该是一样的。这个很好证，因为期望是线性可加的，而每次洗牌后，一个特定位置上的值，是每个位置原来的权值乘以特定的常数（这个常数在下面的证明过程中有推导）相加，只涉及到一些变量期望的线性相加，所以是可以的。注意，这点虽然比较显然，但有些时候不一定是对的，所以这种东西还要先思考一下。

那前面这个结论是不是对的呢？可以写个这样的程序试试，测一下样例，对拍一下，好像还真是这样。那不是就做完了吗？具体做法：每一次选三个好算的算出来，然后把二次函数给算出来（可以待定系数解方程，也可以直接拉格朗日插值），不就可以了吗？选的时候可以选最开始的三个（这样可以二阶差分），也可以选前两个加最后一个，因为这个洗牌的过程可以想成在第一堆和第二堆中任选一个放到牌堆顶，也就是随机打乱（这个在证明2中有说明），然后，把第一堆的拿出来安原来的顺序排好，把第二堆按原来的顺序排好。这样就会发现算最后一个和算第一个是一样好算的。

记第$i$个数是$x_i$，洗牌后第一个数的期望$x_i'=\frac Anx_1+\frac{n-A}nx_{A+1}$，最后一个数的期望$x_n'=\frac Anx_A+\frac{n-A}nx_n$（有$\frac An$的概率是抽到第一堆，$\frac{n-A}n$的概率是抽到第二堆，而且肯定是最后一个），第二个数的期望$x_2'=\frac An(\frac{A-1}{n-1}x_2+\frac{n-A}{n-1}x_{A+1})+\frac{n-A}n(\frac A{n-1}x_1+\frac{n-A-1}{n-1}x_{A+2})$，前者是对应第一个抽到的是第一堆，后者是对应第一个抽到的是第二堆。

这就可以愉快地把这题A了。代码在最后（代码1）。

当然有个非常关键的问题，这个结论为什么是对的？

证明1

我们证明这样一个东西：一个序列$\{a_i\}$（等一下，上面是$x$怎么就变$a$了……懒得改了）满足$a_i=f(i)$，其中$f(i)$为多项式，则对于洗牌后的序列$\{a_i'\}$，存在一个多项式$f'(i)$使得$a_i'=f'(i)$且$\deg f\geqslant\deg g$，这样就能保证选$\deg f+1$个数插值后的结果就是$f'$。为了方便，记$\deg f=m$。

大量公式警告

我们先要知道转移式。考虑$a_j\ (j\leqslant A)$对$a_i'$的贡献，即$a_j$乘以洗牌后第$i$张是原先的第$j$张得概率。考虑某一种情况的概率大概长这样（某一特殊但平凡的情况）：$\frac An\cdot\frac {A-1}{n-1}\cdot\frac {n-A}{n-2}\cdot\cdots\cdot\frac{A-j+1}{n-i+2}\cdot\frac{n-A-i+j+1}{n-i+1}$。观察发现虽然每个分数都没什么规律，每次乘的分数也不是固定的，但是容易发现分子是$A^\frac{j}{}(n-A)^\frac{i-j}{}$，分母是$n^\frac{i}{}$。而$a_i'$前面有$i-1$个数，当中有$j-1$的数是第一堆的，所以要再乘一个$\binom{i-1}{j-1}$。$j>A$时同理。

那么就有

$$a_i'=\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}A^\frac{j}{}(n-A)^\frac{i-j}{}\frac1{n^\frac i{}}+\sum_{j=1}^{n-A}a_{A+j}\dbinom{i-1}{j-1}A^\frac{i-j}{}(n-A)^\frac j{}\frac1{n^\frac{i}{}} $$

其实前后两个式子形式上还是没什么区别，我们就先看前一部分。化简它。

$$\begin{aligned}&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}A^\frac{j}{}(n-A)^\frac{i-j}{}\frac1{n^\frac i{}}\\=&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{A!}{(A-j)!}\cdot\frac{(n-A)!}{(n-A-i+j)!}\cdot\frac{(n-i)!}{n!}\\=&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{(n-i)!}{(A-j)!(n-A-i+j)!}\cdot\frac{A!(n-A)!}{n!}\\=&\frac{A!(n-A)!}{n!}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{(n-i)!}{(A-j)!(n-A-i+j)!}\\=&\frac1{\dbinom nA}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\end{aligned} $$

好像化简不了了……但我们好像忘了一个条件？$a_i$可以表示成至多$m$次（本题$m\leqslant2$）的多项式！这又有什么用呢？

注意到，这里的转移，都是某个位置的数。乘上一个和这个数无关的常数，也就是说，它是线性的，就是将输入的一些数据线性相加（即乘一个常数后相加）的结果，和原先这些输入后分别得到的结果，进行相同的线性相加，得到的结果是一样的（这也不难验证）。若对于所有小于$m$次的多项式$f(x)$都可以表示成$\sum_{k=0}^mc_kf_k(x)$，其中$c_k$为常数，$f_k$是次数为$k$的多项式，我们就只需要证明当$a_i=f_k(i)$时，$a_i'$可以被表示成至多$k$次的多项式即可。

现在，只需要找到一个便于我们证明的$f_k$即可。首先想到的可能是$f_i(x)=x^i$，但这里的系数都是阶乘和二项式，所以更应该尝试下降幂（我们知道$m$次下降幂多项式可以和$m$次多项式一一对应），尝试后发现好像$f_k(x)=(x-1)^\frac k{}$最方便（可能一个理由是下标从$0$开始更自然？我随便说的。），而且我们知道，一个任意的$m$次多项式，总是可以被表示成$m$次的下降幂多项式。那么将$a_j=(j-1)^\frac k{}$带入并来一些操作得：

$$\begin{aligned}&\frac1{\dbinom nA}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^A(j-1)^\frac k{}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^A\frac{(j-1)!}{(j-1-k)!}\cdot\frac{k!}{k!}\cdot\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^Ak!\dbinom{j-1}{k}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{j-1}{k}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\end{aligned} $$

而二项式当中有个东西：

$$\begin{aligned}\dbinom ab\dbinom ca&=\frac{a!}{b!(a-b)!}\cdot\frac{c!}{a!(c-a)!}\\&=\frac{c!}{b!(c-b)!}\cdot\frac{(c-b)!}{(a-b)!(c-a)!}\\&=\dbinom cb\dbinom{c-b}{a-b}\end{aligned} $$

所以令$j-1=a,\ k=b,\ i-1=c$，则有

$$\begin{aligned}&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{j-1}k\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{i-1}k\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_{j=1}^A\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}j\dbinom{n-i}{A-j-1-k}\end{aligned} $$

（倒数第二行可以把限制去掉因为显然$j-1-k\geqslant0,\ j\leqslant A$，即$A\geqslant j\geqslant1+k\geqslant1$时后一串不为0。最后一行是把$j$用$j+1+k$代替。）我们又提出了一项！继续。二项式当中还有一个东西：

$$\sum_j\dbinom nj\dbinom m{k-j}=\dbinom{n+m}k$$

这个式子为什么是对的呢？考虑组合意义。设有$n$个红球，$m$个蓝球，左式为对于每个$j$，当红球取$j$个，蓝球取$k-j$个的方案数之和，相当于总共$n+m$个球中取$k$个球的方案数，即为右式。

令$i-1-k=n,\ n-i=m,\ A-1-k=k$（这里右式的$n,m,k$为上式中的），继续：

$$\begin{aligned}&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}j\dbinom{n-i}{A-j-1-k}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{i-1-k+n-i}{A-1-k}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{n-k-1}{A-k-1}\end{aligned} $$

我们把和式打开了！继续稍微化简一下：

$$\begin{aligned}&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{n-k-1}{A-k-1}\\=&k!\frac{(i-1)!}{k!(i-1-k)!}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\\=&\frac{(i-1)!}{(i-1-k)!}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\\=&(i-1)^\frac k{}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\end{aligned} $$

搞出来了！？也就是说当$a_i=(i-1)^\frac k{}$时，$a_i'$的一部分是$\begin{aligned}(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}$ ，也是$k$次的下降幂。结合前面的说明，可得当$a_i$是$m$次多项式时，$a_i'$的这一部分也是不多于$m$次的多项式。

而另一部分呢？（虽然同理但还有一些差别。）设$b_i=a_{A+i}$，比较一下式子，当$b_i=(i-1)^\frac k{}$时，还是有$a_i'$的另一部分是$\begin{aligned}(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{n-A-k-1}}{\binom n{n-A}}\end{aligned}$（其实下面分母也是$\begin{aligned}\binom nA\end{aligned}$），所以$a_i'$就是至多$m$次的多项式。 证毕。

当然，有了这个式子也可以写一份代码，就是每次记录下降幂多项式的系数（初始条件可能要手算一下），然后可以直接转移，每一项按照这个式子给出的，乘上一个系数，就不用插值了。当然要注意，要将$a_i$的多项式平移后才是$b_i$（设$a_i=f(i)$，则$b_i=a_{A+i}=f(A+i)$。这个平移可能又要手算一下）。可以参考代码2（如果懒得手算就参考一下代码里的那些系数）。

这个证明算是比较完整了，但好像还有点问题，最后这个式子好像有点过于简单？有没有更好的证明方法？

证明2

为了方便起见，根据我们上面的讨论，我们只要证明：一堆牌有$A$张，其中$a_i=(i-1)^\frac k{}\ (1\leqslant i\leqslant A)$；另一堆牌有$n-A$张，其中所有牌的数都为$0$，则洗完牌后每张的期望为$\begin{aligned}a_i'=(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}\ (1\leqslant i\leqslant n)$。（因为前面说的“一部分”其实就是第一堆对答案的贡献，而我们这里直接把第二堆的贡献省略，下面也不讨论第二堆的贡献，因为就是$0$）。

那么，因为这个洗牌的过程是线性的，我们可以所有的权值都缩小到原来的$\frac1{k!}$，我们知道$\begin{aligned}\frac{(i-1)^\frac k{}}{k!}=\frac{(i-1)!}{k!(i-1-k)!}=\binom{i-1}{k}\end{aligned}$，则我们只需要证明当$\begin{aligned}a_i=\binom{i-1}k\end{aligned}$时，$\begin{aligned}a_i'=\frac{\binom{i-1}k\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}$即可。

我们先证明一个前面提到过的结论（这里写得清晰一些）：这样的洗牌相当于，把所有的混在一起，然后把每一堆中的元素，按在原来堆中的顺序，在新堆中排好。可能有点抽象，举个例子：

为了方便讨论，这里和下面都用颜色代表所属的堆。假设两堆牌是$\color{red}1,\color{red}2,\color{red}3$和$\color{blue}4,\color{blue}5,\color{blue}6$，那么随机打乱后有可能是这样的：$\color{red}2,\color{red}1,\color{blue}5,\color{blue}4,\color{red}3,\color{blue}6$，然后$\color{red}2,\color{red}1,\color{red}3$排成$\color{red}1,\color{red}2,\color{red}3$，$\color{blue}5,\color{blue}4,\color{blue}6$排成$\color{blue}4,\color{blue}5,\color{blue}6$，然后按$\color{red}2,\color{red}1,\color{blue}5,\color{blue}4,\color{red}3,\color{blue}6$的颜色插回去变成$\color{red}1,\color{red}2,\color{blue}4,\color{blue}5,\color{red}3,\color{blue}6$。差不多就是这个意思。

证明的话考虑洗牌的过程，我们不考虑每一张牌具体是哪一张，而只考虑颜色，有$\frac X{X+Y}$的概率抽到红色，而红色有$X$张，所以抽到红色的特定一张的概率是$\frac X{X+Y}\cdot\frac1X=\frac1{X+Y}$，蓝色同理，而剩下牌的数量刚好是$X+Y$，就相当于，每一次都随机摸一张牌。这不就和随机打乱一样了吗。而洗牌前后相对位置不变，所以我们确定了颜色之后，就可以确定每一张牌的数。这个性质可以当结论记一下。

有了这个很好的性质，该怎么用呢？

先考虑有多少种情况，显然，根据颜色打乱后有$\begin{aligned}\binom nA\end{aligned}$中等概率的情况，我们只要算出所有情况下$a_j'$的和，先看一下$a_i$对$a_j'$的贡献。

因为$\begin{aligned}a_i=\binom{i-1}k\end{aligned}$，我们把它看成，在$1$到$i-1$中，把其中$k$个做上标记的方案数。考虑对$a_j'$的贡献时，要把$a_i$强行放到$a_j'$上，此时（洗牌后的排队中）$1$到$j-1$还要再选$i-1$个红的，后面$j+1$到$n$中还要选$A-i$个红的，然后统计方案数，而$\begin{aligned}a_i=\binom{i-1}k\end{aligned}$，所以它的贡献还要再乘上$a_i$，也就是相当于再在$1$到$j-1$中的$i-1$个红的，还要再选$k$个做标记，贡献其实是这样一个方案数。理一下，其实就是相当于在$1$到$j-1$中，有$k$个做了标记，还有$i-k-1$个红的，而在$j+1$到$n$中，有$A-i$个红的。

当我们考虑整个的贡献时，因为$1\leqslant i\leqslant A$，所以在$j$前后可以有所有情况的红色的个数，所以相当于在$1$到$j-1$中标记$k$个，在剩下没有标记且不是$j$的位子上（一共有$n-k-1$个位置），选$A-k-1$个红的，所以总的和是$\begin{aligned}\binom{j-1}k\binom{n-k-1}{A-k-1}\end{aligned}$。

而我们知道总的情况数是$\begin{aligned}\binom nA\end{aligned}$，所以$\begin{aligned}a_j'=\frac{\binom{j-1}k\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}$，和前面我们要证明的式子一模一样！

所以我们用了一个非常巧妙的方法证出来了，我觉得这个证明方法还是非常神奇的（我想了好久）。

---

好了，说了这么多，可以上代码了。

代码1：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kcz=998244353;
const int maxn=10000005;
ll a,b,c,f[maxn];
int n;
inline ll qpow(ll a,ll k)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=res*a%kcz;
        if(k>>=1) a=a*a%kcz;
    }
    return res;
}
inline ll calc(ll x) { return ((a*x+b)%kcz*x+c)%kcz; } // 算第x个数的期望
int main()
{
    int m,tp,i;
    ll _,__,t1,t2,t3,t,___,sqn;
    freopen("landlords.in","r",stdin),freopen("landlords.out","w",stdout);
    scanf("%d%d%d",&n,&m,&tp),sqn=n*(ll)n%kcz;
    _=qpow(n-1,kcz-2),__=qpow(n,kcz-2),___=qpow((-sqn+3*n-2)%kcz,kcz-2);
    if(tp==1) a=c=0,b=1;
    else a=1,b=c=0; // x_i=ai^2+bi+c
    while(m--)
    {
        scanf("%lld",&t);
        if(t==0 || t==n) continue;
        t1=(calc(1)*t+calc(t+1)*(n-t))%kcz*__%kcz; // 第一个
        t2=((calc(2)*(t-1)+calc(t+1)*(n-t))%kcz*t+(calc(1)*t+calc(t+2)*(n-t-1))%kcz*(n-t))%kcz*__%kcz*_%kcz; // 第二个
        t3=(calc(t)*t+calc(n)*(n-t))%kcz*__%kcz; // 第n个
        a=((2-n)*t1+(n-1)*t2-t3)%kcz*___%kcz;
        b=((sqn-4)*t1+(1-sqn)*t2+3*t3)%kcz*___%kcz;
        c=((4*n-2*sqn)*t1+(sqn-n)*t2-2*t3)%kcz*___%kcz; // 极其丑的差值
    }
    for(i=1;i<=n;i++)
        f[i]=(calc(i)+kcz)%kcz;
    scanf("%d",&m);
    while(m--)
        scanf("%lld",&t),printf("%lld\n",f[t]);
    fclose(stdin),fclose(stdout);
    return 0;
}

代码2：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kcz=998244353;
const int maxn=10000005;
ll a,b,c,a_,b_,c_,fac[maxn],inv[maxn],inv_fac[maxn];
int n;
inline ll f(ll x) { return (a+b*(x-1)+c*(x-1)%kcz*(x-2))%kcz; } // 算第x个数的期望
inline ll C(int n,int m) { return (m>=0 && m<=n)?fac[n]*inv_fac[m]%kcz*inv_fac[n-m]%kcz:0; } // 判一下0的情况
inline ll invC(int n,int m) { return inv_fac[n]*fac[m]%kcz*fac[n-m]%kcz; }
int main()
{
    int i,q,op,A;
    ll t;
    freopen("landlords.in","r",stdin),freopen("landlords.out","w",stdout);
    scanf("%d%d%d",&n,&q,&op);
    if(op==1) a=b=1,c=0; // a_i=a+b*(i-1)+c*(i-1)*(i-2)
    else a=1,b=3,c=1;
    fac[0]=inv_fac[0]=inv[1]=fac[1]=inv_fac[1]=1;
    for(i=2;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%kcz;
        inv[i]=-(kcz/i)*inv[kcz%i]%kcz;
        inv_fac[i]=inv_fac[i-1]*inv[i]%kcz;
    }
    while(q--)
    {
        scanf("%d",&A);
        a_=(a+b*A+c*A%kcz*(A-1ll))%kcz; // 平移x->x+A
        b_=(b+c*2*A)%kcz;
        c_=c;
        t=invC(n,A);
        a=(a*C(n-1,A-1)+a_*C(n-1,n-A-1))%kcz*t%kcz; // 更新系数
        b=(b*C(n-2,A-2)+b_*C(n-2,n-A-2))%kcz*t%kcz;
        c=(c*C(n-3,A-3)+c_*C(n-3,n-A-3))%kcz*t%kcz;
    }
    scanf("%d",&q);
    while(q--)
        scanf("%d",&i),printf("%lld\n",(f(i)+kcz)%kcz);
    fclose(stdin),fclose(stdout);
    return 0;
}