打卡信奥刷题（3115）用C++实现信奥题 P7355 「PMOI-1」抽奖

P7355 「PMOI-1」抽奖题目描述活动奖池中共有nnn种道具dead_X 有mmm张兑奖券。一张兑奖券可以兑换成一次抽奖机会或114514114514114514金币。dead_X 决定将一部分兑奖券拿来抽奖并将剩下的兑奖券兑换成金币。在一次抽奖机会中dead_X 会等概率得到所有奖池中一款道具的191981019198101919810秒体验卡。由于 dead_X 在活动中买了 VIP 卡他可以在所有抽奖结束后选择一款抽奖得到的体验卡将所有这种类型的体验卡上交并得到对应种类的永久道具。注意dead_X 可以不使用这个功能但是不可以使用多于一次。有选择困难症的 dead_X 想知道有多少种可能的活动结果。两种活动结果不同当且仅当 dead_X 获得的金币不同或者在任何一次抽奖中获得的体验卡不同即抽到体验卡形成的序列不同或者获得的永久道具不同。注意抽奖中获得的都是体验卡最后选择的永久道具和体验卡在哪一次抽出没有关系。Update 2023.11.16出题人看自己好几年前写的题面绷不住了补一份形式化题面。定义一个序列的权值是其不同元素个数111例如[1,9,2,6,8,1,7][1,9,2,6,8,1,7][1,9,2,6,8,1,7]的权值是777。对于所有长度∈[0,m]\in[0,m]∈[0,m]每个数∈[1,n]\in [1,n]∈[1,n]的整数序列求其权值和对109710^971097取模的值。输入格式本题有多组数据。第一行一个整数TTT代表数据组数。对于每组数据输入两个正整数n,mn,mn,m分别表示道具的种数和兑奖券的张数。输出格式输出共TTT行每行输出一个正整数代表方案数对109710^971097取模的值。输入输出样例 #1输入 #15 2 1 2 2 3 3 114 514 1919810 7872754输出 #15 15 115 338602801 30498159说明/提示【样例解释】以下为第二组测试数据所有可能的方案假设两种物品分别为AAA和BBB。兑换229028229028229028金币。兑换114514114514114514金币获得AAA体验卡。兑换114514114514114514金币获得BBB体验卡。兑换114514114514114514金币获得AAA永久道具。兑换114514114514114514金币获得BBB永久道具。第一次获得AAA体验卡第二次获得AAA体验卡。第一次获得AAA体验卡第二次获得BBB体验卡。第一次获得BBB体验卡第二次获得AAA体验卡。第一次获得BBB体验卡第二次获得BBB体验卡。第一次获得AAA体验卡第二次获得AAA体验卡指定AAA为永久道具。第一次获得AAA体验卡第二次获得BBB体验卡指定AAA为永久道具。第一次获得BBB体验卡第二次获得AAA体验卡指定AAA为永久道具。第一次获得AAA体验卡第二次获得BBB体验卡指定BBB为永久道具。第一次获得BBB体验卡第二次获得AAA体验卡指定BBB为永久道具。第一次获得BBB体验卡第二次获得BBB体验卡指定BBB为永久道具。【数据范围】Subtask110ptsn,m≤5,T≤25n,m\leq5,T\le25n,m≤5,T≤25Subtask210ptsn1n1n1Subtask310ptsm1m1m1Subtask420ptsn,m≤1000,T≤5n,m\leq1000,T\leq 5n,m≤1000,T≤5Subtask520pts∑m≤106\sum m\leq10^6∑m≤106Subtask630pts无特殊限制。对于100%100\%100%的数据满足1≤n,m≤1091\le n,m\leq 10^91≤n,m≤1091≤T≤1051\le T\leq 10^51≤T≤105。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;inlineintread(){intx0;charchgetchar();while(ch0||ch9)chgetchar();while(ch0ch9)xx*10(ch15),chgetchar();returnx;}constintp1000000007;intqp(intx,inty){intres1;for(intnowx;y;nownow*now%p,y1)(y1)(resres*now%p);returnres;}signedmain(){for(intTread();T--;){intnread(),mread();if(n1)printf(%lld\n,((m1)1)%p);elseif(n2)printf(%lld\n,((qp(n,m1)qp(n,m2)p-1-n)%p*qp(n-1,p-2)%pp-n*(m1)%p)%p);elseprintf(%lld\n,((qp(n,m1)qp(n,m2)p-1-n)%p*qp(n-1,p-2)%pp-n*(qp(n-1,m1)p-1)%p*qp(n-2,p-2)%p)%p);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容