P7474 「C.E.L.U-02」学术精神
题目描述
提供一句话题意阅读。
某地有nnn个小朋友，每个小朋友都有一个独特的idea，其中第iii个小朋友的 idea 的编号为iii。老师让这个每一个小朋友在一组编号分别为1∼n1\sim n1∼n的卡片中随机抽一个，抽完后把卡片放回去，这个小朋友会和编号为卡片上数字的小朋友交换idea（交换指两人把所有自己知道的 idea 告诉对方）。因为自己和自己交换 idea 在他们眼中也许是一件很傻的事情，所以如果卡片上的编号与自己的相同，他将再抽一次（此时他已经把卡片放回去了），直到编号不是自己的为止。
不久，每个小朋友都抽完了一遍，每个小朋友将把收集到的所有idea 出成一场比赛，因为有 idea 的交换，有很多比赛之间都是有联系的。
如果两场比赛中存在 idea相同的题目，我们认为这两场比赛是有联系的。「联系」具有传递性：如果比赛A\mathbf AA、B\mathbf BB有联系，比赛B\mathbf BB、C\mathbf CC有联系，则比赛A\mathbf AA、C\mathbf CC也有联系。为了避免理解错误，在这举一个例子：
若仅有四场比赛：比赛一出现了 idea111、222；比赛二出现 idea222、555；比赛三出现 idea333、555、888，比赛四出现 idea444、777。则比赛一、二之间有直接联系。比赛一、三之间虽然没有公共 idea，但它们之间是有联系的。比赛四与其他所有比赛没有联系。
而所有有联系的比赛都将属于同一个比赛集，没有联系的比赛处在不同的比赛集。
上例中比赛一、二、三属于一个比赛集，比赛四属于另一个。
求所有人抽球卡片的次数和的期望E0E_0E0和比赛集的个数sss的期望E1E_1E1。
一句话题意：
对于每个点iii随机与[1,n][1,n][1,n]中的一点连无向边，若连向自己，则保留该边并再次连边，一直重复至连到别的点上为止，求边数与连通块个数期望。
输入格式
输入一行一个正整数nnn。
输出格式
第一行输出一个数E0E_0E0，第二行输出一个数E1E_1E1，可以证明它们都是有理数。
为了避免精度误差，您只需要输出它们对质数998244353998244353998244353取模的结果即可，如果您不会分数取模，您可以查找关于费马小定理与乘法逆元的相关资料。
如果输出格式错误或两问答案均错误，该测试点得000分；
如果仅答对第一问，该测试点得333分；
如果仅答对第二问，该测试点得777分；
如果两问均正确，该测试点得101010分。
请务必输出两个整数。
输入输出样例 #1
输入 #1
2输出 #1
4 1输入输出样例 #2
输入 #2
7输出 #2
166374067 539688692说明/提示
样例解释
样例解释一
每个小朋友摸卡片次数为111的概率为12\dfrac{1}{2}21，摸卡片次数为222的概率为14\dfrac{1}{4}41，摸卡片次数为iii的期望次数为12i\dfrac{1}{2^i}2i1，期望摸卡片次数为222，总摸卡片次数为444。
111号小朋友一定会和222号小朋友交换 idea，所以他们出的比赛之间一定是属于同一个比赛集。E1=1E_1=1E1=1。
样例解释二
第一问取模前的答案为496\dfrac{49}{6}649。
第二问取模前的答案为22451944\dfrac{2245}{1944}19442245。
数据范围
| 测试点编号 | nnn | 测试点编号 | nnn |
|---|---|---|---|
| 111 | ≤3\leq 3≤3 | 555 | ≤1000\leq 1000≤1000 |
| 222 | ≤5\leq 5≤5 | 666 | ≤2000\leq 2000≤2000 |
| 333 | ≤9\leq 9≤9 | 7∼87\sim87∼8 | ≤5000\leq 5000≤5000 |
| 444 | ≤12\leq 12≤12 | 9∼109\sim 109∼10 | ≤104\leq10^4≤104 |
对于100%100\%100%的数据，有2≤n≤1042\leq n\leq10^42≤n≤104。
C++实现
#include<bits/stdc++.h>#defineintlonglong#definerintregisterintusingnamespacestd;intconstmod=998244353;intconstN=1e4+10;intfac[N],facn[N];#defineinv(x)(qpow(x,mod-2))inlineintqpow(inta,intb){intans=1;while(b){if(b&1)ans*=a,ans%=mod;a*=a,a%=mod,b>>=1;}returnans;}inlineintC(intn,intm){returnfac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;}signedmain(){ios::sync_with_stdio(false);cout.tie(0),cout.tie(0);intn;cin>>n;fac[0]=1;for(inti=1;i<=n;++i)fac[i]=fac[i-1]*i,fac[i]%=mod;facn[0]=1;for(inti=1;i<=n;++i)facn[i]=facn[i-1]*(n-1),facn[i]%=mod;//预处理 (n-1) 的次方cout<<n*n%mod*inv(n-1)%mod<<'\n';intans=0;for(inti=2;i<=n;++i)ans+=(C(n,i)*fac[i-1]%mod*facn[n-i]%mod),ans%=mod;cout<<ans*inv(facn[n])%mod<<'\n';return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
