P11655 「FAOI-R5」Lovely 139题目背景Height≤139\text{Height}\leq139Height≤139。题目描述对于一个01\tt 0101串SSS下标从111开始我们定义它的一个区间[l,r][l,r][l,r]是极长颜色段当且仅当它同时满足以下条件如果l≠1l\neq 1l1Sl−1≠SlS_{l-1}\neq S_lSl−1​Sl​如果r≠∣S∣r\neq \lvert S\rvertr∣S∣Sr1≠SrS_{r1}\neq S_rSr1​Sr​∀i∈[l,r),SiSi1\forall i\in[l,r),S_iS_{i1}∀i∈[l,r),Si​Si1​。定义g(S)g(S)g(S)为SSS的不同极长颜色段数。比如g(00)1g(00)1g(00)1g(1110)2g(1110)2g(1110)2g(001011)4g(001011)4g(001011)4。定义f(n,m)f(n,m)f(n,m)的值为所有恰好包含n\boldsymbol nn个0\tt 00和m\boldsymbol mm个1\tt 11的01\tt 0101串SSS的g(S)g(S)g(S)之和。你需要回答TTT个问题每次给出n,mn,mn,m的值求f(n,m)f(n,m)f(n,m)的值对109710^971097取模后的结果。输入格式第一行输入一个正整数数TTT表示问题个数。接下来TTT行每行两个非负整数n,mn,mn,m表示问题的参数。输出格式输出TTT行每行为对应问题的答案。输入输出样例 #1输入 #13 2 2 4 6 7 8输出 #118 1218 54483输入输出样例 #2输入 #23 845 826 672 826 618 925输出 #2789284214 588160420 730993180输入输出样例 #3输入 #31 1 46输出 #3139说明/提示样例 1 解释对于第一组数据n2,m2n2,m2n2,m2一共有六个本质不同的SSS答案为g(0011)g(0101)g(0110)g(1001)g(1010)g(1100)24334218g(0011)g(0101)g(0110)g(1001)g(1010)g(1100)24334218g(0011)g(0101)g(0110)g(1001)g(1010)g(1100)24334218。数据规模与约定本题采用捆绑测试。Subtask 115 pts0≤nm≤200 \le nm \le 200≤nm≤201≤T≤101 \le T \le 101≤T≤10。Subtask 225 pts0≤nm≤4×1030 \le nm \le 4 \times 10^30≤nm≤4×103。Subtask 320 pts1≤T≤101 \le T \le 101≤T≤10。Subtask 440 pts无特殊限制。对于所有数据保证1≤T≤1061 \leq T \leq 10^61≤T≤1060≤nm≤2×1060 \leq nm\leq 2 \times 10^60≤nm≤2×1060≤n,m≤2×1060\le n,m\le 2\times10^60≤n,m≤2×106。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod1e97;intT,n,m,jc[2000006],inv[2000005];//jc表示阶乘inv表示逆元intqpow(inta,intb){intans1;while(b){if(b1)ansans*a%mod;b1;aa*a%mod;}returnans;}intc(intn,intm){returnjc[n]*inv[n-m]%mod*inv[m]%mod;}//求组合的函数signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinT;jc[0]1;for(inti1;i2000000;i)jc[i]jc[i-1]*i%mod;//求阶乘inv[2000000]qpow(jc[2000000],mod-2);//费马小定理for(inti1999999;i0;i--)inv[i]inv[i1]*(i1)%mod;while(T--){cinnm;if(!n!m){cout1\n;continue;}cout(c(nm,n)(nm-1)*c(nm-2,n-1)%mod*2%mod)%mod\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容