打卡信奥刷题（3062）用C++实现信奥题 P6862 [RC-03] 随机树生成器

张开发
• 2026/4/7 12:33:26 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（3062）用C++实现信奥题 P6862 [RC-03] 随机树生成器
P6862 [RC-03] 随机树生成器题目描述小 R 有一个随机树生成器其工作原理如下输入nnn则对于每个1i≤n1i\le n1i≤n随机选择一个[1,i)[1,i)[1,i)中的节点作为其父亲。返回这棵树。给定n,kn,kn,k小 R 想知道可能生成的所有nnn个点的树中kkk号点的度数和。由于答案可能很大请输出答案模109910^991099的值。输入格式本题有多组数据。第一行一个整数是数据组数TTT。接下来TTT行每行两个正整数n,kn,kn,k。输出格式TTT行每行一个整数为这组数据的答案模109910^991099的值。输入输出样例 #1输入 #13 3 1 3 2 3 3输出 #13 3 2说明/提示【样例说明】数据111一共有两种情况111号点的度数分别为1,21,21,2。因此答案为333。数据222一共有两种情况222号点的度数分别为1,21,21,2。因此答案为333。数据333一共有两种情况333号点的度数均为111。因此答案为222。【数据范围】本题捆绑测试。对于100%100\%100%的数据1≤T≤1051\le T\le 10^51≤T≤1051≤k≤n≤1071\le k\le n\le 10^71≤k≤n≤107。详细数据范围如下。Subtask 120 分T≤50T\le 50T≤50n≤8n\le 8n≤8。Subtask 255 分T1T1T1n≤105n\le 10^5n≤105。Subtask 320 分T1T1T1。Subtask 45 分没有任何附加限制。C实现#includecstdio#includecstring#includealgorithmusingnamespacestd;constintmod1e99;intT,n,k,fac[10000005],inv[10000005];intmain(){fac[0]1;for(inti1;i1e7;i)fac[i]1ll*fac[i-1]*i%mod;inv[1]1;for(inti2;i1e7;i)inv[i]1ll*(mod-mod/i)*inv[mod%i]%mod;for(inti1;i1e7;i)inv[i](inv[i-1]inv[i])%mod;scanf(%d,T);while(T--){scanf(%d%d,n,k);intee(inv[n-1]-inv[k-1]mod)%mod;printf(%lld\n,(1ll*fac[n-1]*ee%mod(k!1)*fac[n-1])%mod);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章