Solution CF2089C2 Key of Like (Hard Version)

· · 题解

记当前有 a 个锁，a+b 个钥匙。

考虑第一个人。每对钥匙和锁的配对成功概率都是 \frac1{a+b}。不妨假设第一个人选了第一个锁和钥匙。

接下来考虑第一个人没选中轮到第二个人，有三种可能：

因此我们发现实际上第二个人绝对会选择第一个锁或钥匙（分别简记为选锁和钥匙）然后任意选择其它的配对。由于每个人会等概率选取所有成功概率相同的操作，并且选钥匙则有 a-1 个锁配对，选锁则有 a+b-1 个钥匙配对。所以选钥匙和锁的概率分别为 \frac{a-1}{2a+b-2} 和 \frac{a+b-1}{2a+b-2} 种方案。

轮到第二个人且选中的概率是 \frac{a+b-1}{a+b}\cdot\frac1{a+b-1}=\frac1{a+b}，和第一个人相同。

考虑第三个人，还是三种情况。例如如果还是第一个锁与其它钥匙配对，则概率为 \frac1{a+b-2}，并且可以证明这个方案是唯一最大的。感性理解可以认为其利用了最多的信息。第一个钥匙和锁配对同理。因此轮到第三个人且选中的概率同样是 \frac1{a+b}。

于是发现从第二个人之后，每个人都会重复和上个人一样的操作。考虑到某个人成功配对了，我们将配对的钥匙和锁去掉后发现没有任何关于剩下的东西的信息，即之前的操作不会干扰后续的概率！因此我们就把问题转化为 a\gets a-1，b 不变的情况。

另一种情况是第二个人选了钥匙后到第 a 个人仍然没有配对成功，那么说明是假钥匙。只将这个钥匙去掉，前后仍然没有影响，因此转移到 a 不变，b\gets b-1 的子问题。注意的是转化后的问题人的编号会发生循环移位。

接下来就可以 dp 了：记 f_{a,b,i} 表示 a 个锁，a+b 个钥匙，第 i 个人期望成功多少次。

一种情况是从 f_{a-1,b,i-j}（i-j 是在模 n 意义下的）转移过来，选钥匙则 j 的上界为 a，否则为 a+b。转移的概率为 \frac1{a+b} 乘上第二个人选钥匙或锁的概率。可以前缀和优化转移。

另一种情况只在选钥匙时生效，即 \frac b{a+b} 的概率转移到 f_{a,b-1,i-a}。

同时还要加上恰好在 i 人上完成配对的概率，为 \frac{\sum_{c=0}^{a-1}[i==c]}{a+b}，容易 O(1) 计算。

因此我们发现 dp 可以做到 O(nlk)，可以通过此题。

const int P=1000000007;
int inv[20005];
il void init(int n){
    inv[1]=1;forto(i,2,n)inv[i]=1ll*(P-P/i)*inv[P%i]%P;
}
int n,l,k,f[5005][30][105];
il void addto(int &x,int y){x+=y;if(x>=P)x-=P;}
il void delto(int &x,int y){x-=y;if(x<0)x+=P;}
il void work(){
    n=read(),l=read(),k=read();
    int cnt,s1,s2;ll v1,v2;
    forto(a,1,l)forto(b,0,k){
        s1=s2=0;
        forv(i,n)addto(s1,1ll*(a/n+(i>=n-a%n))*f[a-1][b][i]%P),addto(s2,1ll*((a+b)/n+(i>=n-(a+b)%n))*f[a-1][b][i]%P);
        v1=1ll*(a-1)*inv[2*a+b-2]%P*inv[a+b]%P,v2=1ll*(a+b-1)*inv[2*a+b-2]%P*inv[a+b]%P;
        if(a==1&&b==0)v1=inv[a+b],v2=0;
        forv(i,n){
            addto(f[a][b][i],v1*s1%P),addto(f[a][b][i],v2*s2%P);
            addto(f[a][b][i],v1*(a/n+(i<a%n))%P),addto(f[a][b][i],v2*((a+b)/n+(i<(a+b)%n))%P);
            if(b)addto(f[a][b][i],v1*b%P*f[a][b-1][(i-a%n+n)%n]%P);
            addto(s1,f[a-1][b][i]),delto(s1,f[a-1][b][(i-a%n+n)%n]);
            addto(s2,f[a-1][b][i]),delto(s2,f[a-1][b][(i-(a+b)%n+n)%n]);
        }
    }
    forv(i,n)printf("%d ",f[l][k][i]);puts("");
    forto(a,0,l)forto(b,0,k)forv(i,n)f[a][b][i]=0;
}

signed main(){
    init(20000);
    int t=read();while(t--)work();
    return 0;
}