首先声明！！！

  • 1、题解为本人原作，如有使用注明出处。
  • 2、如有改进地方欢迎批评指正~

题目一：Problem - 1925D - Codeforces

介绍一种二项式组合数方法：

众所周知，$期望 = 概率 * 值$。
我们设期望为 $E$，总概率为 $p$，总值为 $sum$。则：
$$
E=p\times sum
$$

由于 $k$ 的次数是固定的，则设
$$
s=\sum_{i=1}^m{f_i}
$$

且 $s$ 每回合每个固定增加 $1$ （类似于等差数列求和的过程），则有：
$$
sum\gets s+sum
$$
$$
s\gets s+m
$$

解决完 $sum$ 后，我们还剩下 $p$ 没有搞定，那么总概率 $p$ 怎么求呢？

因为每一个个体选中的概率是相等的，且都为
$$
\frac{1}{C_{n}^{2}}=\frac{2}{n(n-1)}
$$

所以我们可以先设选中的概率为 $x$，没被选中的概率为 $y$。

根据二项式定理得：
$$
p=\sum_{i=1}^k{C_{k}^{i}}x^iy^{k-i}
$$

$$
x=\frac{2}{n(n-1)},y=1-x
$$

因为事件是独立的，每个值对应着对应的概率，则总式为：

$$
sum_i\gets s+sum_{i-1}
$$

$$
\sum_{i=1}^k{E} \gets C_{k}^{i}x^iy^{k-i}\times sum_i
$$

$$
s\gets s+m
$$

最后我们把公式实现一下就搞定了，时间复杂度为：
$$
O(m+k\log mod)
$$

注意：有数据点当 $n$ 为 100000 时，数据会爆 longlong，所以算 $x$ 时先取模（我就是因为这个而 wa6 了 ~T_T~）。

MainCode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>f[i];
    
    int s=0;
    for(int i=1;i<=m;i++) s=(s+f[i])%mod;
    
    int sum=0,res=0,p=(n-1)*n/2%mod;   //p记得取模
    int x=qmi(p,mod-2),y=(1-x+mod)%mod;  
    for(int i=1;i<=k;i++){
        sum=(s+sum)%mod;
        res=(res+C(k,i)*qmi(x,i)%mod*qmi(y,k-i)%mod*sum%mod)%mod;
        s=(s+m)%mod;
    }
    cout<<res<<'\n';
}

题目二：Problem - 2020E - Codeforces

题目大意：给定序列 $a$ 和概率序列 $p$，求和在 $a$ 序列中选取的集合总数异或和的平方。

解题分析：

一、首先集合总数为 $2^n$，每个集合都代表着每个元素选和不选两种情况，并且观察数据量，$a$ 序列中的元素很小，只有 1-1023，由此考虑用 $dp$ 背包思想来考虑此题，时间复杂度 $O(2^{10}n)$。

二、$dp[i][j]$ 代表在选取前 $i$ 个元素的集合里，异或和为 $j$ 的概率。因为 $a$ 序列元素的范围是 1-1023，所以异或和也不会超过 1023，$dp$ 数组开 $dp[N][2^{10}]$。

三、设上一个状态为 $t$，当前状态为 $j$，即：

$$
j = a[i] \oplus t
$$

已知 $j$，由异或的性质移项得：

$$
t = a[i] \oplus j
$$

四、转移方程：

  • 不选的情况：

$$
dp_{i,j} = dp_{i-1,j} \times (1-p[i])
$$

  • 选的情况：

$$
dp_{i,j} = dp_{i,j} + dp_{i-1,t} \times p[i]
$$

最后 $(f(S))^2$ 即把 0-1023 平方求和，并且把转移方程实现下就 ok 啦 （记得取模）。

交了第一发 mle

$code$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=0;i<=n;i++) for(int j=0;j<1<<10;j++) dp[i][j]=0;
    
dp[0][0]=1;     // 什么都不选概率为1
for(int i=1;i<=n;i++){
    for(int j=0;j<1<<10;j++){
        int t=a[i]^j;
        dp[i][j]=dp[i-1][j]*(1-p[i]*qmi(10000,mod-2)%mod+mod)%mod;
        dp[i][j]=(dp[i][j]+dp[i-1][t]*p[i]%mod*qmi(10000,mod-2)%mod)%mod;
    }
}
    
ll sum=0;
for(int i=0;i<1<<10;i++) sum=(sum+dp[n][i]*i%mod*i%mod)%mod;
cout<<sum<<'\n';

第一发一交，发现 mle 了，把 define int long long 换了也不行，因此我意识到还得优化空间。

稍微思考了一下，发现这个就是经典滚动数组优化，可以优化掉一维，但是前一个状态得另外用一个数组 pre 来记录，因为异或会改变原来的状态，并且不是有序的。

交了第二发 tle2

$code$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=0;i<1<<10;i++) dp[i]=pre[i]=0;
    
pre[0]=1;     // 什么都不选概率为1
for(int i=1;i<=n;i++){
    for(int j=0;j<1<<10;j++){
        int t=a[i]^j;
        dp[j]=pre[j]*(1-p[i]*qmi(10000,mod-2)%mod+mod)%mod;
        dp[j]=(dp[j]+pre[t]*p[i]%mod*qmi(10000,mod-2)%mod)%mod;
    }
    for(int j=0;j<1<<10;j++) pre[j]=dp[j];
}
    
int sum=0;
for(int i=0;i<1<<10;i++) sum=(sum+(ll)dp[i]*i%mod*i%mod)%mod;
cout<<sum<<'\n'

交了第二发 tle2，那就是把我 log 复杂度也卡了，赶紧先预处理一下 $p$ 序列先。。。。

交了第三发tle13

b 溃了，居然还会 t，不会卡我 define int long long 了吧，我将信将疑改了再交一发。

交了第四发 AC

$code$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>p[i],p[i]=p[i]*qmi(10000,mod-2)%mod;
for(int i=0;i<1<<10;i++) dp[i]=pre[i]=0;
    
pre[0]=1;     // 什么都不选概率为1
for(int i=1;i<=n;i++){
    for(int j=0;j<1<<10;j++){
        int t=a[i]^j;
        dp[j]=(ll)pre[j]*(1-p[i]+mod)%mod;
        dp[j]=(dp[j]+(ll)pre[t]*p[i]%mod)%mod;
    }
    for(int j=0;j<1<<10;j++) pre[j]=dp[j];
}
    
ll sum=0;
for(int i=0;i<1<<10;i++) sum=(sum+(ll)dp[i]*i%mod*i%mod)%mod;
cout<<sum<<'\n';

布什戈门，3890ms 通过，这个题还会卡常？也许我这个还不是正解，恰巧被我冲过去了。

$ps$：交 c++20 能够冲到 890ms，很神秘。