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行，每行一个整数，表示答案对109+710^9+7109+7取模的结果。
输入输出样例 #1
输入 #1
3 3 1 10 2 1 0输出 #1
3 25200 1输入输出样例 #2
输入 #2
5 502520 0 502520 1 502520 2 502520 3 502520 4输出 #2
1 218102685 429650441 770595802 584122358说明/提示
对于前10%10\%10%的数据，T=0T=0T=0。
对于前30%30\%30%的数据，T≤10T\leq 10T≤10，n≤7n\leq 7n≤7。
对于另外10%10\%10%的数据，k=0k=0k=0。
对于另外10%10\%10%的数据，k=100k=100k=100。
对于100%100\%100%的数据，0≤T≤1050\leq T\leq 10^50≤T≤105，1≤n≤1061\leq n\leq 10^61≤n≤106，0≤k≤1000\leq k\leq 1000≤k≤100。
C++实现
#include<iostream>#definelllonglongconstintmod(1e9+7);usingnamespacestd;ll t,n,k,jc[1000005]={0,1};llqpow(ll a,ll b){ll s=1;while(b){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}returns;}intmain(){#ifdefytxyfreopen("in.txt","r",stdin);#endifcin>>t;for(inti=2;i<=1e6;i++)jc[i]=jc[i-1]*i%mod;while(t--){cin>>n>>k;if(k>20||(1<<k)>=n)cout<<jc[n]<<'\n';elseif(k==0)cout<<1<<'\n';elsecout<<1ll*qpow(qpow(jc[n/(1<<k)],mod-2)/*逆元*/,1<<k)*qpow(qpow(n/(1<<k)+1,mod-2),n%(1<<k))%mod/*此前为求概率（所有第k层子集有序的总概率）*/*jc[n]/*全排列数*/%mod<<'\n';}}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
)
