打卡信奥刷题（3121）用C++实现信奥题 P7392 「TOCO Round 1」奇怪的排序

P7392 「TOCO Round 1」奇怪的排序题目背景欢喜不问天风流不问天温柔不问天良辰不问天良缘不问天。问你不问天。题目描述情人节那天Biadocy\color{orange}\texttt{Biadocy}Biadocy被虐得好惨尤其是上流的公爵和小孩说什么《和你在一起的每一天都叫情人节》。于是他找到了一个机会来报复。现在有nnn对情人编号为1∼n1\sim n1∼n按任意顺序排成一列Biadocy\color{orange}\texttt{Biadocy}Biadocy对他们执行了下面这段排序的伪代码。Biadocy\color{orange}\texttt{Biadocy}Biadocy想知道有多少种初始排列满足按照这段伪代码排序后情人们的编号有序。也许这能让他好受一点。输入格式第一行一个整数TTT表示数据组数。接下来TTT行每行两个整数n,kn,kn,k表示情人对数和第一次调用伪代码传入的参数。输出格式TTT行每行一个整数表示答案对109710^971097取模的结果。输入输出样例 #1输入 #13 3 1 10 2 1 0输出 #13 25200 1输入输出样例 #2输入 #25 502520 0 502520 1 502520 2 502520 3 502520 4输出 #21 218102685 429650441 770595802 584122358说明/提示对于前10%10\%10%的数据T0T0T0。对于前30%30\%30%的数据T≤10T\leq 10T≤10n≤7n\leq 7n≤7。对于另外10%10\%10%的数据k0k0k0。对于另外10%10\%10%的数据k100k100k100。对于100%100\%100%的数据0≤T≤1050\leq T\leq 10^50≤T≤1051≤n≤1061\leq n\leq 10^61≤n≤1060≤k≤1000\leq k\leq 1000≤k≤100。C实现#includeiostream#definelllonglongconstintmod(1e97);usingnamespacestd;ll t,n,k,jc[1000005]{0,1};llqpow(ll a,ll b){ll s1;while(b){if(b1)ss*a%mod;aa*a%mod;b1;}returns;}intmain(){#ifdefytxyfreopen(in.txt,r,stdin);#endifcint;for(inti2;i1e6;i)jc[i]jc[i-1]*i%mod;while(t--){cinnk;if(k20||(1k)n)coutjc[n]\n;elseif(k0)cout1\n;elsecout1ll*qpow(qpow(jc[n/(1k)],mod-2)/*逆元*/,1k)*qpow(qpow(n/(1k)1,mod-2),n%(1k))%mod/*此前为求概率所有第k层子集有序的总概率*/*jc[n]/*全排列数*/%mod\n;}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容