P10116 [LMXOI Round 1] Random 题解（评分：7.6）

· · 题解

前言

不知道 Random 是不是指一首曲子。

有趣但是简单的数数题，感觉比 T2 简单。

都推式子？那我就从组合意义考虑吧！

Solution

考虑我们在统计 B 在操作完的所有可能序列中的出现次数，这个是很烦的，比如：

A=[1,2,1,2,1],B=[1,2,1]

发现有重叠部分，但是事实上这里对答案的贡献为 2，这是不好快速统计的。

如果考虑操作序列去匹配 B 来更新答案是困难的，那么正难则反，考虑 B 序列要出现在某一位置能匹配多少种操作序列。

为什么这是正确的？

因为同一个操作序列中如果多次出现 B 要多次更新答案，反过来在多个位置匹配到同一个操作序列，也会多次更新答案，而且次数相等。

这时候我们惊喜地发现两件事：

第一、B 序列出现在任意位置匹配的操作序列数相等，因为每次操作选择任意位置的概率相等。

所以我们只需要计算 B 出现在 [1,m] 的情况，乘上 (n-m+1) 即可。

第二、类似的，B 序列每个数具体是啥，对答案没有影响，因为修改位置是独立的，我修改某一个位置影响不到别的位置，而且修改为每个数的概率也相等。

所以我们压根不用输入第二行。

那么现在，修改的位置选择共 n^q 种情况，修改成的数有 k^q 种情况，分开计算，再乘起来即可。

修改成的数

要求：对应的 m 个位置最后一次出现的时候必须修改成对应的数。

换句话说，不管我前面的修改位置怎么选，总有 m 个操作我的修改成的数是固定的，而剩下的，要么修改位置大于 m 我压根不管（我只统计 B 出现于 [1,m] 的答案）、要么后面这个位置还要改对，总之我想改成哪个数无所谓。

共有 1^m\times k^{q-m} 中合法情况。

修改位置

要求：1 到 m 每个位置至少被选中过一次。

有多少种情况？我又不会了。

老规矩考虑正难则反，我统计不是每一个位置都出现过的情况。

即：我考虑有 i 个位置没有出现过，选择这 i 个位置有 \binom{m}{i} 种选法，然后每次选位置，除了这 i 个位置皆可选，共 (n-i)^q 种情况。

然后用小学学过的容斥原理，i 为奇数时减去，i 为偶数时加上，就结束了。

最后，答案为：

(n-m+1)\times k^{q-m}\times (n^q-\sum_{i=1}^{m}(-1)^i\binom{m}{i}(n-i)^q)

式子和其他题解有一点不同。

实现是简单的，\binom{m}{i} 递推，逆元用快速幂实现。

后记

听我劝谏：人生苦短，正难则反……

Play like you never did before!

AC code

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int qp(int x,int y)
{
    int ans=1;
    for(int i=1,j=x;i<=y;i*=2,j=(j*j)%mod) if(y&i) ans=(ans*j)%mod;
    return ans;
}
int n,m,q,k,i,j,c[3141592],ans,anf;
signed main()
{
    cin>>n>>m>>q>>k;
    if(q>=m)
    {
        ans=((n-m+1)*qp(k,q-m))%mod;
        anf=qp(n,q);
        c[1]=c[m-1]=m;c[0]=c[m]=1;
        for(i=2;i<=(m+1)/2;i++) c[i]=c[m-i]=((c[i-1]*(m+1-i))%mod*qp(i,mod-2))%mod;
        for(i=1;i<=m;i++)
        {
            if(i%2)
                anf=(anf-qp(n-i,q)*c[i])%mod;
            else
                anf=(anf+qp(n-i,q)*c[i])%mod;
        }
        anf=(anf+mod)%mod;
        ans=(ans*anf)%mod;
    }
    cout<<ans;
    return 0;
}