【NOI2019】斗主地【期望】【组合数学】【下降幂】【插值】
题意：
有nnn张牌，从上往下的第iii张牌权值是f(i)=itypef(i)=i^{type}f(i)=itype。
进行mmm次洗牌操作，每次操作给定aia_iai，将从上往下的前aia_iai张牌分成一堆，后面bib_ibi张牌分成第二堆。如果两堆的牌数分别为X,YX,YX,Y，则有XX+Y\frac{X}{X+Y}X+YX的概率将第一堆的最下面一张牌放在第三堆的最上面，否则将第二堆的最下面放到第三堆的最上面，直到两边都没有牌，第三堆为最终结果。
最后qqq次询问从上往下第cic_ici张牌的期望权值 模 998244353998244353998244353。
n≤107,m,q≤5×105,type∈{1,2}n\leq 10^7,m,q\leq5\times 10^5,type\in\{1,2\}n≤107,m,q≤5×105,type∈{1,2}
题本身不错，但结论太好猜，而且要证明必须要先猜出来，出在NOI还是比较失败的
结论1 第kkk次洗牌可以看成把第k−1k-1k−1次洗牌后每张牌的期望看成权值洗牌
根据期望的线性性应该很容易理解。
式子证明：
设第k−1k-1k−1次洗牌后第iii张牌是原来的第jjj张牌的概率是P(i,j)P(i,j)P(i,j)
第kkk次洗牌后第iii张牌对应第k−1k-1k−1次的第jjj张牌的概率为P′(i,j)P'(i,j)P′(i,j)
那么第kkk次后对应原来的编号是
P′′(i,j)=∑k=1nP′(i,k)P(k,j)P''(i,j)=\sum_{k=1}^nP'(i,k)P(k,j)P′′(i,j)=k=1∑nP′(i,k)P(k,j)
第k−1k-1k−1次后第iii张牌的期望是
E(i)=∑j=1nP(i,j)F(j)E(i)=\sum_{j=1}^nP(i,j)F(j)E(i)=j=1∑nP(i,j)F(j)
把它看成权值洗第kkk次
E′(i)=∑j=1nP′(i,j)E(j)=∑j=1nP′(i,j∑k=1nP(j,k)f(k)=∑j=1n∑k=1nP′(i,k)P(k,j)f(j)=∑j=1nP′′(i,j)f(j)E'(i)=\sum_{j=1}^nP'(i,j)E(j)\\ =\sum_{j=1}^nP'(i,j\sum_{k=1}^nP(j,k)f(k)\\=\sum_{j=1}^n\sum_{k=1}^nP'(i,k) P(k,j)f(j)\\=\sum_{j=1}^nP''(i,j)f(j)E′(i)=j=1∑nP′(i,j)E(j)=j=1∑nP′(i,jk=1∑nP(j,k)f(k)=j=1∑nk=1∑nP′(i,k)P(k,j)f(j)=j=1∑nP′′(i,j)f(j)
结论2 题目中洗牌的方式相当于(nai)\binom n {a_i}(ain)种方案等概率随机选择一种。
即：这(nai)\binom n {a_i}(ain)种方案出现的概率都相等
考虑一个长度为nnn 、有aia_iai个000的010101序列sss，000表示取第一堆，111表示取第二堆，它和最终洗牌后的牌堆情况一一对应，每个位置选择的概率只和它后缀中000和111的数量有关。
考虑交换两个相邻的000和111，设它们的下标是iii和i+1i+1i+1，不妨设si=0,si+1=1s_i=0,s_{i+1}=1si=0,si+1=1
1∼i−11\sim i-11∼i−1和i+2∼ni+2\sim ni+2∼n的位置后缀010101数量都没有变化，贡献的概率都是一样的。
设i+2∼ni+2\sim ni+2∼n中有xxx个000和yyy个111
交换前这两位的概率是 x+1x+y⋅y+1x+y−1\frac{x+1}{x+y}\cdot\frac{y+1}{x+y-1}x+yx+1⋅x+y−1y+1
交换后的概率是y+1x+y⋅x+1x+y−1\frac{y+1}{x+y}\cdot\frac{x+1}{x+y-1}x+yy+1⋅x+y−1x+1
所以交换后的概率都是相等的
进而得到所有情况的概率都相等
Q: 按这种思路，为什么按12\frac{1}{2}21的概率选一堆就不是均匀随机了呢？
A: 如果可以完全保证12\frac 1221的概率，那么也是均匀随机的。但问题出在一堆选完之后，就只能选剩下的一堆，概率实际上不是12\frac 1221，导致最终结果不均匀。而本题中选完之后概率就是000，并没有特殊情况。
结论3 无论洗多少次牌，牌堆中第iii张牌的期望权值都是关于iii的不超过typetypetype次的多项式。
采用归纳法，假设第m−1m-1m−1次后是个typetypetype次的多项式，需要证明再洗一次仍然是typetypetype次多项式。
设在m−1m-1m−1次后第iii张牌的期望是E(i)E(i)E(i)，mmm次后是E′(i)E'(i)E′(i)。我们尝试用EEE来表示出E′(i)E'(i)E′(i)，即计算出概率P′(i,j)P'(i,j)P′(i,j)
因为是等概率随机的，计算概率就等价于计算方案数。记 am=Aa_m=Aam=A，以下的推导中均省略分母中的(nA)\binom nA(An)
不妨设j≤amj\leq a_mj≤am，即只考虑分到第一堆的牌的贡献，分到第二堆是同理的
我们要让jjj落到iii的位置上，那么在iii前面选择的第一堆的牌需要恰好j−1j-1j−1张，iii后面通过组合数算出贡献的方案
即
P′(i,j)=(i−1j−1)(n−iA−j)P'(i,j)=\binom{i-1}{j-1}\binom{n-i}{A-j}P′(i,j)=(j−1i−1)(A−jn−i)
那么可以得到
E′(i)=∑j=1A(i−1j−1)(n−iA−j)E(j)E'(i)=\sum_{j=1}^A\binom{i-1}{j-1}\binom{n-i}{A-j}E(j)E′(i)=j=1∑A(j−1i−1)(A−jn−i)E(j)
你把两个组合数拆一下，发现完全没有像常数的意思，不说typetypetype次了，都有点怀疑是不是多项式。
但还有个重要的性质没用：E(j)E(j)E(j)本身也是typetypetype次的多项式
当然前面一堆组合数，带几个单项式进去显然没有任何作用。
但看到多项式又有组合数，你想到了什么？阶乘幂啊！
把E(j)E(j)E(j)转成下降幂多项式，然后考虑每个下降幂单项式jk‾(k≤type)j^{\underline k}(k\leq type)jk(k≤type)的贡献
∑j=1A(i−1j−1)(n−iA−j)jk‾\sum_{j=1}^A\binom{i-1}{j-1}\binom{n-i}{A-j}j^{\underline k}j=1∑A(j−1i−1)(A−jn−i)jk
……等等，前面的分母都有(j−1)!(j-1)!(j−1)!了，我们干脆拆成(j−1)k‾(j-1)^{\underline k}(j−1)k好了
∑j=1A(i−1j−1)(n−iA−j)(j−1)k‾\sum_{j=1}^A\binom{i-1}{j-1}\binom{n-i}{A-j}(j-1)^{\underline k}j=1∑A(j−1i−1)(A−jn−i)(j−1)k
看着难受，除一个k!k!k!转成组合数
∑j=1A(i−1j−1)(n−iA−j)(j−1k)\sum_{j=1}^A\binom{i-1}{j-1}\binom{n-i}{A-j}\binom{j-1}{k}j=1∑A(j−1i−1)(A−jn−i)(kj−1)
∑j=1A(i−1j−1)(n−iA−j)(j−1k)\sum_{j=1}^A\binom{i-1}{j-1}\binom{n-i}{A-j}\binom{j-1}{k}j=1∑A(j−1i−1)(A−jn−i)(kj−1)
=∑j=1A(i−1j−1)(j−1k)(n−iA−j)=\sum_{j=1}^A\binom{i-1}{j-1}\binom{j-1}{k}\binom{n-i}{A-j}=j=1∑A(j−1i−1)(kj−1)(A−jn−i)
=∑j=1A(i−1k)(i−k−1i−j)(n−iA−j)=\sum_{j=1}^A\binom{i-1}{k}\binom{i-k-1}{i-j}\binom{n-i}{A-j}=j=1∑A(ki−1)(i−ji−k−1)(A−jn−i)
=(i−1k)∑j=1A(i−k−1i−j)(n−iA−j)=\binom{i-1}{k}\sum_{j=1}^A\binom{i-k-1}{i-j}\binom{n-i}{A-j}=(ki−1)j=1∑A(i−ji−k−1)(A−jn−i)
=(i−1k)∑j=1A(i−k−1j−k−1)(n−iA−j)=\binom{i-1}{k}\sum_{j=1}^A\binom{i-k-1}{j-k-1}\binom{n-i}{A-j}=(ki−1)j=1∑A(j−k−1i−k−1)(A−jn−i)
引理
∑i(ni)(mk−i)=(n+mk)\sum_i\binom ni\binom m{k-i}=\binom{n+m}ki∑(in)(k−im)=(kn+m)
理性愉悦
构造
(x+1)n(x+1)m=(x+1)n+m(x+1)^n(x+1)^m=(x+1)^{n+m}(x+1)n(x+1)m=(x+1)n+m
比较xkx^kxk项系数得证
感性愉悦
有n+mn+mn+m件物品选择kkk件，等价于分成nnn和mmm两堆，在前一堆选任意iii件，在另一堆选剩下的k−ik-ik−i件。
=(i−1k)(n−k−1A−k−1)=\binom{i-1}{k}\binom{n-k-1}{A-k-1}=(ki−1)(A−k−1n−k−1)
左边就是关于iii的kkk次下降幂多项式，也就是kkk次多项式，右边是个无关的常数。因为k≤typek\leq typek≤type，所以得到的仍然是typetypetype次的多项式。
因为type≤2type\leq 2type≤2，所以维护333个点值就可以O(1)O(1)O(1)算出任意位置的答案。这里由于懒得写阶乘，维护的是第000项、第一个公差、二阶公差。
在洗牌的时候先插值算出两堆的前333个，然后暴力枚举求出洗牌后前333个的期望。
另外注意题目中从上到下和从下到上的表述。
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> using namespace std; const int MOD=998244353; typedef long long ll; inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD;p>>=1;}return ans; } int A,B,C; inline int calc(int x){return (A+(ll)B*x+(ll)x*(x-1)/2%MOD*C)%MOD;} int main() {int n,m,type;scanf("%d%d%d",&n,&m,&type);if (type==1) A=n+1,B=MOD-1;else A=(n+1ll)*(n+1)%MOD,B=(MOD-2*n-1),C=2;int inv[3]={qpow(n,MOD-2),qpow(n-1,MOD-2),qpow(n-2,MOD-2)};while (m--){int k;scanf("%d",&k);k=n-k;int a[3]={calc(1),calc(2),calc(3)},b[3]={calc(k+1),calc(k+2),calc(k+3)},c[3]={};for (int S=0;S<8;S++){int cnt[2]={},v=1,x=k,y=n-k;for (int i=0;i<3;i++) {if ((S>>i)&1) ++cnt[1],v=(ll)v*y%MOD*inv[i]%MOD,--y;else ++cnt[0],v=(ll)v*x%MOD*inv[i]%MOD,--x;}if (cnt[0]>k||cnt[1]>n-k) continue;cnt[0]=cnt[1]=0;for (int i=0;i<3;i++){if ((S>>i)&1) c[i]=(c[i]+(ll)v*b[cnt[1]])%MOD,++cnt[1];else c[i]=(c[i]+(ll)v*a[cnt[0]])%MOD,++cnt[0];}}C=((c[2]-2*c[1]+c[0])%MOD+MOD)%MOD;B=((c[1]-c[0]-C)%MOD+MOD)%MOD;A=(c[0]-B+MOD)%MOD;}int q;scanf("%d",&q);while (q--){int x;scanf("%d",&x);printf("%d\n",calc(n-x+1));}return 0; }总结
以上是生活随笔为你收集整理的【NOI2019】斗主地【期望】【组合数学】【下降幂】【插值】的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 2020数伏第一天是哪天
- 下一篇： 【NOI2019】 机器人 【区间dp】