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输入 #12输出 #14 1输入输出样例 #2输入 #27输出 #2166374067 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所以他们出的比赛之间一定是属于同一个比赛集。E11E_11E1​1。样例解释二第一问取模前的答案为496\dfrac{49}{6}649​。第二问取模前的答案为22451944\dfrac{2245}{1944}19442245​。数据范围测试点编号nnn测试点编号nnn111≤3\leq 3≤3555≤1000\leq 1000≤1000222≤5\leq 5≤5666≤2000\leq 2000≤2000333≤9\leq 9≤97∼87\sim87∼8≤5000\leq 5000≤5000444≤12\leq 12≤129∼109\sim 109∼10≤104\leq10^4≤104对于100%100\%100%的数据有2≤n≤1042\leq n\leq10^42≤n≤104。C实现#includebits/stdc.h#defineintlonglong#definerintregisterintusingnamespacestd;intconstmod998244353;intconstN1e410;intfac[N],facn[N];#defineinv(x)(qpow(x,mod-2))inlineintqpow(inta,intb){intans1;while(b){if(b1)ans*a,ans%mod;a*a,a%mod,b1;}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;cinn;fac[0]1;for(inti1;in;i)fac[i]fac[i-1]*i,fac[i]%mod;facn[0]1;for(inti1;in;i)facn[i]facn[i-1]*(n-1),facn[i]%mod;//预处理 (n-1) 的次方coutn*n%mod*inv(n-1)%mod\n;intans0;for(inti2;in;i)ans(C(n,i)*fac[i-1]%mod*facn[n-i]%mod),ans%mod;coutans*inv(facn[n])%mod\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容