题意：

一道数论的题(又是数学期望)。

这道题是一位大佬叫我做的，然后我才会做。。。FALLEN_GEMINI大佬。

这道题有两种方法，一种是直接暴力求公式，一种是递归求解。

首先介绍第一种方法：

很明显根据抽屉原理可以得到，当次数最大为 n+1n+1 次时，必然会有两张相同的牌。

然后我们考虑算出抽 kk 次正好出现相同的牌的数学期望，再将这些期望求和便是总期望。

抽 kk 次正好抽中相同的牌的概率为：

Pk=1×n−1n×n−2n×⋅⋅⋅×n−(k−2)n×k−1n P_k=1\times \frac{n-1}{n}\times \frac{n-2}{n}\times ···\times \frac{n-(k-2)}{n}\times \frac{k-1}{n}

化简后即为：

Pk=(n−1)!(k−1)nk−1(n−k+1)! P_k=\frac{(n-1)!(k-1)}{n^{k-1}(n-k+1)!}

为什么呢？

首先观察前面这一串，即：

Pk1=1×n−1n×n−2n×⋅⋅⋅×n−(k−2)n P_{k_1}=1\times \frac{n-1}{n}\times \frac{n-2}{n}\times ···\times \frac{n-(k-2)}{n}

这里代表的是满足前 k−1k-1 次每次都要抽的与之前不同的概率。

再来看后面这个：

Pk2=k−1n P_{k_2}=\frac{k-1}{n}

这个代表的是正好第 kk 次抽中了与之前相同的概率，由于之前有 k−1k-1 张不同的牌，所以为 k−1n\frac{k-1}{n}。

然后由 数学期望=概率×取值，而抽 kk 次的取值为 kk，可以得到：

Ek=Pk×k=(n−1)!k(k−1)nk−1(n−k+1)! E_k=P_k\times k=\frac{(n-1)!k(k-1)}{n^{k-1}(n-k+1)!}

然后最后用求和公式即可得到总期望为：

E=∑k=1n+1(n−1)!k(k−1)nk−1(n−k+1)! E= \sum _{k=1} ^{n+1} \frac{(n-1)!k(k-1)}{n^{k-1} (n-k+1)!}

然后就可以愉快的码代码了。

代码：

#include<bits/stdc++.h>
 
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
    return x * f;
}
 
typedef long long ll;
 
int s[20];
int top;
inline void print(ll &ans) {
    top = 0;
    while(ans) {
        s[++top] = ans%10;
        ans /= 10;
    }
    while(top)
        putchar(s[top--]+'0');
    putchar('\n');
}
 
const int MAXN = 10000010;
const ll MOD = 998244353;
ll fac[MAXN], ifac[MAXN], inv[MAXN];
int n;
 
inline ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1LL) res = res * a % MOD;
        b >>= 1, a = a * a % MOD;
    }
    return res;
}
 
int main() {
     
    int Q = read();
    ll i;
    fac[0] = 1;
    for(i = 1; i <= 10000000; i++) fac[i] = fac[i-1]*i%MOD;
    ifac[10000000] = qpow(fac[10000000], MOD-2);
    for(i = 10000000; i >= 1; i--) ifac[i-1] = ifac[i]*i%MOD;
    for(i = 1; i <= 10000000; i++) inv[i] = ifac[i]*fac[i-1]%MOD;
     
    while(Q--) {
        n = read();
        ll ans = 0, np = 1;
        for(i = 1; i <= n+1; i++) {
            ans = (ans+i*(i-1)%MOD*ifac[n-i+1]%MOD*np%MOD)%MOD;
            np = np * inv[n]%MOD;
        }
        ans = ans * fac[n-1]%MOD;
        print(ans);
    }
    return 0;
}

然后讲第二种思路(来自大佬FALLEN_GEMINI大佬)。

我们可以采用初中数学统计的方式，画一颗树，树的第几层代表第几次可以抽哪些牌，那么当一个节点到根节点的路径上出现了两个相同的数，那么这个点就是叶子节点，不能再往下画了。同时我们可以清晰地知道第 kk 层的概率为 1nk\frac{1}{n^k}，那么只用找出每层有多少个节点，找到规律后递归(递推)求解即可。(据大佬说递归会被卡)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int MAXN=1e7+10;
int n,ans,inv[MAXN];
int read(){int sss=0,fff=1;char ccc=getchar();while(ccc<'0'||ccc>'9'){if(ccc=='-') fff=-1;ccc=getchar();}while(ccc>='0'&&ccc<='9'){sss=sss*10+ccc-'0';ccc=getchar();}return sss*fff;}
int ksm(int base,int k)
{
	int sum=1;
	while(k)
	{
		if(k&1) sum=1ll*sum*base%mod;
		base=1ll*base*base%mod;
		k>>=1;
	}
	return sum;
}
void solve()
{
	n=read();ans=0;
	int op=n,kd=inv[n];
	for(int i=1;i<=n+1;i++)
	{
		int ansl=1ll*op*kd%mod;
		ans=(ans+ansl)%mod;
		op=1ll*op*(n-i+1)%mod;
		kd=1ll*kd*inv[n]%mod;
	}
	printf("%d\n",ans);
}
void init()
{
	inv[1]=1;
	for(int i=2;i<=10000000;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	init();
	int T=read();
	while(T--)
		solve();
	return 0;
}