本文起因是 HDU ACM 2023 第九场 T8。

Coins

给定长度为 的序列 ，每次随机选取数对 满足 ，使得 ，若 则将其从 中删除，问期望几次操作使得 只有一个数。

---

我们来看一种很新的科技，考虑使用函数 刻画 的的期望，令 的一次操作之后得到 ， 满足 。

我们知道终态是唯一且不具有后继状态的，所以如果 存在，那么 就是我们的答案。

我们知道期望具有线性性，所以需要使得 仅包含线性运算，考虑定义 ，那么根据定义就有： 右边没啥意思，来看左边， 表示一次操作总的选择可能性， 表示有 种方案根本就没选到 ， 表示有 种可能性 作为第一操作数，后面一项表示 为第二操作数。

然后解方程： 设个 ，就有 。可以发现 是一个合法的构造，于是得到 。

然后计算即可。

CODE

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=__int128;
const int N=1000010,FSIZE=1<<26;
int tn;
ll n,a[N];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF,ST[100],*STC=ST;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
void write(ll x){
    for(!x&&(*OnF++=48);x;x/=10) *++STC=x%10^48;
    for(;STC!=ST;*OnF++=*STC--);
    *OnF++='\n';
}
ll f(ll x){return((1+x)*x>>1);}
void work(){
    ll sum=0,st=0;
    read(n);
    for(int i=1;i<=n;++i){
        read(a[i]);
        st+=f(a[i]);
        sum+=a[i];
    }
    write(f(sum)-st);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    for(read(tn);tn--;work());
    fwrite(WuF,1,OnF-WuF,stdout);
}