交错代表队一、题目题目名称交错代表队题目背景某场 ICPC 训练营需要从两个方向的成员中选出一支代表队并按照出场顺序排成一列。题目内容训练营中有 A 名算法组成员和 B 名工程组成员每个人都互不相同。现在要选出恰好 K 个人并将这 K 个人按照出场顺序排成一列。要求1. 队伍中恰好有 R 名算法组成员2. 任意两名算法组成员不能相邻。请你计算满足条件的不同出场序列数量。两个序列不同当且仅当存在某个位置上的成员不同。答案可能很大请输出对 1000000007 取模后的结果。输入第一行一个整数 T表示测试用例数量。接下来 T 行每行四个整数 A、B、K、R。输出对于每组测试数据输出一行一个整数表示满足条件的出场序列数量模 1000000007 的结果。样例输入42 3 3 13 2 4 25 1 4 30 4 2 0样例输出3636012数据范围1 T 2000000 A,B 10000000 K AB0 R K提示注意成员都是互不相同的因此不仅要选择成员还要考虑他们在序列中的顺序。时间限制普通/Java2000 MS / 10000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路考察排列数、组合数以及“先安排一类再插空”的计数模型。设工程组实际选出的人数为 S K - R。如果出现以下任一情况答案为 01. R A2. S B3. S 04. R S 1。第四个条件来自“不允许两名算法组成员相邻”。如果先把 S 名工程组成员排好会形成 S1 个空隙_ B _ B _ ... B _每个空隙最多放一名算法组成员所以必须有 R S1。接下来分三步第一步选择并排列 S 名工程组成员。因为顺序有区别方案数为P(B,S)第二步从 S1 个空隙中选择 R 个空隙。方案数为C(S1,R)第三步选择并排列 R 名算法组成员。方案数为P(A,R)因此Ans P(B,S) * C(S1,R) * P(A,R)所有计算对 MOD 1000000007 取模。由于 A、B 最大为 10^6可以预处理阶乘 fact 和逆阶乘 ifactC(n,k) fact[n] * ifact[k] * ifact[n-k]P(n,k) fact[n] * ifact[n-k]时间复杂度预处理 O(N)每组询问 O(1)。空间复杂度O(N)。三、解题代码#include bits/stdc.h using namespace std; using int64 long long; const int MOD 1000000007; int64 qpow(int64 a, int64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{int A,B,K,R;}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; if(!(cinT)) return 0; vectorQuery qs(T); int N0; for(auto q:qs){ cinq.Aq.Bq.Kq.R; int Sq.K-q.R; Nmax(N,q.A); Nmax(N,q.B); if(S0) Nmax(N,S1); } vectorint64 fact(N1), ifact(N1); fact[0]1; for(int i1;iN;i) fact[i]fact[i-1]*i%MOD; ifact[N]qpow(fact[N],MOD-2); for(int iN;i1;i--) ifact[i-1]ifact[i]*i%MOD; auto C [](int n,int k)-int64{ if(k0 || kn || n0) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; auto P [](int n,int k)-int64{ if(k0 || kn || n0) return 0; return fact[n]*ifact[n-k]%MOD; }; for(auto q:qs){ int Sq.K-q.R; if(S0 || q.Rq.A || Sq.B || q.RS1){ cout0\n; continue; } int64 ansP(q.B,S); ansans*C(S1,q.R)%MOD; ansans*P(q.A,q.R)%MOD; coutans\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。环形灯带一、题目题目名称环形灯带题目内容有 N 盏灯按照顺时针方向排成一个圆环编号为 1,2,...,N。编号 1 与编号 N 的灯也相邻。你需要恰好点亮其中 K 盏灯。我们把一段“亮灯块”定义为圆环上一个极大的连续亮灯区间。例如当 N8 时亮 灭 亮 亮 灭 灭 亮 亮由于第 1 盏灯与第 8 盏灯相邻所以第 7、8、1 盏灯属于同一个亮灯块。请计算恰好点亮 K 盏灯并且整个圆环上恰好出现 R 个亮灯块的方案数。每盏灯的位置有编号因此旋转后得到的状态通常视为不同方案。特殊约定1. K0 时亮灯块数量为 02. KN 时亮灯块数量为 1。答案对 1000000007 取模。输入第一行一个整数 T。接下来 T 行每行三个整数 N、K、R。输出每组数据输出一行答案。样例输入65 2 15 2 26 3 16 3 26 3 34 4 1样例输出5561221数据范围1 T 2000001 N 10000000 K N0 R N时间限制普通/Java2000 MS / 10000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路核心不是直接套一个组合数而是把环上的状态转化为“若干个正长度亮段 若干个正长度灭段”。先处理特殊情况1. K0只有全灭一种状态并且 R 必须为 02. KN只有全亮一种状态并且 R 必须为 1。下面考虑 0KN。如果恰好有 R 个亮灯块那么由于圆环中亮块与灭块交替出现也一定有 R 个灭灯块。把 K 盏亮灯拆成 R 个非空连续段长度组成方案数为 C(K-1,R-1)。把 N-K 盏灭灯拆成 R 个非空连续段长度组成方案数为 C(N-K-1,R-1)。现在得到的是一个按“亮段、灭段、亮段、灭段……”排列的环形结构但还没有固定到编号 1。选择圆环上的一个位置作为某个亮段的起点有 N 种选择。然而同一个最终灯带状态有 R 个亮段起点因此被计算了 R 次。所以Ans N / R * C(K-1,R-1) * C(N-K-1,R-1)这里的除法是在模 1000000007 意义下乘 R 的逆元。因为 N MOD 且 1 R N所以 R 一定存在逆元。必要条件1 R K1 R N-K否则答案为 0。时间复杂度预处理 O(N)每组 O(1)。空间复杂度O(N)。三、解题代码#include bits/stdc.h using namespace std; using int64 long long; const int MOD1000000007; int64 qpow(int64 a,int64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{int n,k,r;}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; vectorQuery qs(T); int N0; for(auto q:qs){ cinq.nq.kq.r; Nmax(N,q.n); } vectorint64 fact(N1), ifact(N1), inv(N1); fact[0]1; for(int i1;iN;i) fact[i]fact[i-1]*i%MOD; ifact[N]qpow(fact[N],MOD-2); for(int iN;i1;i--) ifact[i-1]ifact[i]*i%MOD; if(N1) inv[1]1; for(int i2;iN;i) inv[i]MOD-(MOD/i)*inv[MOD%i]%MOD; auto C [](int n,int k)-int64{ if(n0 || k0 || kn) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; for(auto q:qs){ int nq.n,kq.k,rq.r; if(k0){ cout(r0 ? 1 : 0)\n; continue; } if(kn){ cout(r1 ? 1 : 0)\n; continue; } if(r1 || rk || rn-k){ cout0\n; continue; } int64 ans(int64)n*inv[r]%MOD; ansans*C(k-1,r-1)%MOD; ansans*C(n-k-1,r-1)%MOD; coutans\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。两处检查点一、题目题目名称两处检查点题目内容在一个 N×M 的网格上起点为 (0,0)终点为 (N,M)。你每一步只能进行以下两种移动之一1. 从 (x,y) 移动到 (x1,y)2. 从 (x,y) 移动到 (x,y1)。网格中有两个不同的检查点P(X1,Y1)Q(X2,Y2)请计算从 (0,0) 到 (N,M) 的所有合法路径中恰好经过 P、Q 两个检查点中的一个的路径数量。“恰好经过一个”表示经过 P 但不经过 Q或者经过 Q 但不经过 P。答案对 1000000007 取模。输入第一行一个整数 T。接下来 T 行每行六个整数N M X1 Y1 X2 Y2保证两个检查点不同并且都位于矩形 0xN0yM 内。输出每组数据输出一行答案。样例输入43 3 1 1 2 23 3 1 2 2 14 3 0 0 2 15 4 2 1 4 3样例输出8181758数据范围1 T 1000000 N,MNM 20000000 X1,X2 N0 Y1,Y2 MP ! Q时间限制普通/Java2000 MS / 10000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路考察二项式系数、路径分段乘法以及基础容斥并且必须正确判断两个检查点是否可能在同一条单调路径上同时出现。从 (x1,y1) 单调走到 (x2,y2)只有在x1x2 且 y1y2时才可能到达。若可以到达设 dxx2-x1dyy2-y1。路径数为C(dxdy,dx)记A 经过 P 的路径集合B 经过 Q 的路径集合题目要求恰好经过一个检查点所以|A△B| |A| |B| - 2|A∩B|经过单个检查点 P 的路径数ways((0,0),P) * ways(P,(N,M))Q 同理。关键在 A∩B。如果X1X2 且 Y1Y2那么同一条单调路径若同时经过两个点只能先经过 P再经过 Qways((0,0),P) * ways(P,Q) * ways(Q,(N,M))如果X2X1 且 Y2Y1则只能先经过 Q再经过 P。否则两个点在二维偏序上不可比较例如一个更靠右但另一个更靠上。由于路径不能向左或向下因此不可能同时经过两个点此时 |A∩B|0。最终Ans |A| |B| - 2|A∩B|注意模意义下处理负数。时间复杂度预处理阶乘 O(NM)每组询问 O(1)。空间复杂度O(NM)。三、解题代码#include bits/stdc.h using namespace std; using int64long long; const int MOD1000000007; int64 qpow(int64 a,int64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{int n,m,x1,y1,x2,y2;}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; vectorQuery qs(T); int S0; for(auto q:qs){ cinq.nq.mq.x1q.y1q.x2q.y2; Smax(S,q.nq.m); } vectorint64 fact(S1), ifact(S1); fact[0]1; for(int i1;iS;i) fact[i]fact[i-1]*i%MOD; ifact[S]qpow(fact[S],MOD-2); for(int iS;i1;i--) ifact[i-1]ifact[i]*i%MOD; auto C [](int n,int k)-int64{ if(n0 || k0 || kn) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; auto ways [](int xa,int ya,int xb,int yb)-int64{ if(xaxb || yayb) return 0; int dxxb-xa, dyyb-ya; return C(dxdy,dx); }; for(auto q:qs){ int64 Aways(0,0,q.x1,q.y1)*ways(q.x1,q.y1,q.n,q.m)%MOD; int64 Bways(0,0,q.x2,q.y2)*ways(q.x2,q.y2,q.n,q.m)%MOD; int64 I0; if(q.x1q.x2 q.y1q.y2){ Iways(0,0,q.x1,q.y1); II*ways(q.x1,q.y1,q.x2,q.y2)%MOD; II*ways(q.x2,q.y2,q.n,q.m)%MOD; }else if(q.x2q.x1 q.y2q.y1){ Iways(0,0,q.x2,q.y2); II*ways(q.x2,q.y2,q.x1,q.y1)%MOD; II*ways(q.x1,q.y1,q.n,q.m)%MOD; } int64 ans(AB-2*I)%MOD; if(ans0) ansMOD; coutans\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。有限字母表一、题目题目名称有限字母表题目内容给定一个包含 M 种不同字符的字母表。现在要构造一个长度恰好为 N 的字符串。字符串中的每个位置都可以从这 M 种字符中任选一种并且字符允许重复出现。请计算恰好使用 K 种不同字符的字符串数量。例如字符串 abac 恰好使用了 3 种字符a、b、c。答案对 1000000007 取模。输入第一行一个整数 T。接下来 T 行每行三个整数 N、M、K。输出每组数据输出一行答案。样例输入53 3 24 4 45 3 12 5 30 10 0样例输出1824301数据范围1 T 1000000 N 10^180 M 2000000 K M所有测试用例的 K 之和不超过 200000。特别说明长度为 0 的空字符串恰好使用 0 种字符因此 N0,K0 时答案为 1。时间限制普通/Java3000 MS / 15000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路需要先选择真正出现的字符集合再对“每种字符至少出现一次”进行容斥。第一步从 M 种字符中选择最终会出现的 K 种字符C(M,K)接下来只考虑这 K 种字符要求长度 N 的字符串中每一种都至少出现一次。如果暂时不限制是否出现每个位置有 K 种选择共K^N定义坏事件 Ai第 i 种已选字符完全没有出现。使用容斥至少每种字符出现一次的字符串数量为sum_{i0..K} (-1)^i * C(K,i) * (K-i)^N其中 i 表示指定 i 种字符缺失。所以Ans C(M,K) *sum_{i0..K} (-1)^i C(K,i)(K-i)^N边界1. KM答案为 02. N0 且 K0答案为 03. N0,K0答案为 14. KN 时事实上也不可能但容斥公式会自然得到 0。实现中可直接提前返回。由于 N 可达 10^18幂必须使用快速幂。组合数中的 M、K 最大只有 2×10^5因此正常预处理阶乘即可。时间复杂度每组 O(K log N)所有 K 之和 2×10^5。空间复杂度O(M)。三、解题代码#include bits/stdc.h using namespace std; using int64long long; using u64unsigned long long; const int MOD1000000007; int64 qpow(int64 a,u64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{ unsigned long long n; int m,k; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; vectorQuery qs(T); int M0; for(auto q:qs){ cinq.nq.mq.k; Mmax(M,q.m); } vectorint64 fact(M1), ifact(M1); fact[0]1; for(int i1;iM;i) fact[i]fact[i-1]*i%MOD; ifact[M]qpow(fact[M],MOD-2); for(int iM;i1;i--) ifact[i-1]ifact[i]*i%MOD; auto C [](int n,int k)-int64{ if(n0 || k0 || kn) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; for(auto q:qs){ if(q.n0){ cout(q.k0 ? 1 : 0)\n; continue; } if(q.k0 || (unsigned long long)q.kq.n){ cout0\n; continue; } int64 sur0; for(int i0;iq.k;i){ int64 termC(q.k,i)*qpow(q.k-i,q.n)%MOD; if(i1) sur(sur-termMOD)%MOD; else sur(surterm)%MOD; } coutC(q.m,q.k)*sur%MOD\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。礼物错配一、题目题目名称礼物错配题目内容有 N 个人编号为 1,2,...,N同时有 N 份礼物礼物也编号为 1,2,...,N。现在把所有礼物一一分配给所有人每个人恰好得到一份礼物每份礼物恰好被一个人得到。如果第 i 个人得到第 i 份礼物我们称第 i 个人发生了一次“正确匹配”。请计算满足以下两个条件的分配方案数1. 恰好有 K 个人发生正确匹配2. 第 1 个人不能得到第 2 份礼物。答案对 1000000007 取模。输入第一行一个整数 T。接下来 T 行每行两个整数 N、K。输出每组数据输出一行答案。样例输入62 03 03 14 15 25 5样例输出0126171数据范围1 T 2000002 N 10000000 K N时间限制普通/Java2000 MS / 10000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路若只会“恰好 K 个固定点 C(N,K)D(N-K)”还不够需要继续处理额外禁止边。记 D(t) 为 t 个元素的错排数D(0)1D(1)0D(t)(t-1)(D(t-1)D(t-2))首先忽略“1 不能得到礼物 2”。恰好 K 个正确匹配先选出 K 个固定点再让剩余 N-K 个人全部错排Total C(N,K) * D(N-K)接下来减去坏方案Bad 恰好 K 个正确匹配并且第 1 个人得到礼物 2。设 MN-K。如果强制 1-2那么1. 人 1 不可能是固定点2. 人 2 也不可能是固定点因为礼物 2 已经被人 1 拿走3. K 个固定点只能从编号 3..N 中选择。选择固定点C(N-2,K)固定这些人后还剩 M 个人参与非固定部分。其中已经固定了一条边 1-2。删除人 1 和礼物 2 后剩下 M-1 个人与 M-1 份礼物进行匹配。其中有 M-2 个位置仍然禁止“人 i 得到礼物 i”而人 2 的自身礼物 2 已经被删除因此对人 2 没有对应的固定点限制。这个计数为F(M)sum_{j0..M-2} (-1)^j C(M-2,j)(M-1-j)!并且可以化简为F(M)D(M-1)D(M-2)因此Bad C(N-2,K) * (D(M-1)D(M-2))当 KN-2 时C(N-2,K)0坏方案自然不存在。最终Ans Total - Bad所有下标小于 0 的 D 视为 0。时间复杂度预处理阶乘与错排 O(N)每组 O(1)。空间复杂度O(N)。三、解题代码#include bits/stdc.h using namespace std; using int64long long; const int MOD1000000007; int64 qpow(int64 a,int64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{int n,k;}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; vectorQuery qs(T); int N0; for(auto q:qs){ cinq.nq.k; Nmax(N,q.n); } vectorint64 fact(N1), ifact(N1), der(N1); fact[0]1; for(int i1;iN;i) fact[i]fact[i-1]*i%MOD; ifact[N]qpow(fact[N],MOD-2); for(int iN;i1;i--) ifact[i-1]ifact[i]*i%MOD; der[0]1; if(N1) der[1]0; for(int i2;iN;i){ der[i](int64)(i-1)*(der[i-1]der[i-2])%MOD; } auto C [](int n,int k)-int64{ if(n0 || k0 || kn) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; auto D [](int n)-int64{ if(n0) return 0; return der[n]; }; for(auto q:qs){ int mq.n-q.k; int64 totalC(q.n,q.k)*D(m)%MOD; int64 bad0; if(q.kq.n-2){ badC(q.n-2,q.k)*(D(m-1)D(m-2))%MOD; } int64 ans(total-badMOD)%MOD; coutans\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。限量补给一、题目题目名称限量补给题目内容有 N 支互不相同的队伍以及 S 个完全相同的补给包。你需要把所有 S 个补给包全部分配给这 N 支队伍。对于每支队伍1. 可以不获得补给包2. 最多只能获得 C 个补给包。现在额外要求恰好有 R 支队伍获得至少 1 个补给包。请计算满足要求的分配方案数。由于队伍有编号因此即使各队获得数量相同只要对应队伍不同也视为不同方案。答案对 1000000007 取模。输入第一行一个整数 T。接下来 T 行每行四个整数N S C R输出每组数据输出一行答案。样例输入53 4 3 24 3 2 25 5 1 55 6 1 54 0 3 0样例输出912101数据范围1 T 1000001 N 10000000 S 10000001 C 10000000 R N所有测试用例的 R 之和不超过 200000。时间限制普通/Java3000 MS / 15000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路需要连续使用“选择非空队伍 正整数解转非负整数解 上界容斥”。第一步先选择哪 R 支队伍获得补给。方案数C(N,R)接下来只考虑这 R 支队伍。设它们得到的补给数为x1x2...xRS并且1 xi C令yixi-1则y1y2...yRS-R并且0 yi C-1如果没有上界 yiC-1那么非负整数解数量由隔板法得到C((S-R)R-1,R-1)C(S-1,R-1)现在使用容斥处理上界。选择 j 个变量违反上界即 yiC。对这些变量令 yiyi-C相当于总和减少 jC。对应非负整数解数量C(S-jC-1,R-1)选择违反上界的 j 个变量有C(R,j)所以合法正整数解数量为sum_j (-1)^j C(R,j) C(S-jC-1,R-1)其中只需要枚举满足S-R-jC 0的 j。最终Ans C(N,R) *sum_j (-1)^j C(R,j) C(S-jC-1,R-1)边界1. R0 时只有 S0 才有 1 种方案2. SR 时不可能3. SR*C 时不可能4. RN 时不可能。时间复杂度每组 O(min(R,(S-R)/C))。由于所有 R 之和 2×10^5总复杂度可控。空间复杂度O(max(N,S))。三、解题代码#include bits/stdc.h using namespace std; using int64long long; const int MOD1000000007; int64 qpow(int64 a,int64 e){ int64 r1; while(e){ if(e1) rr*a%MOD; aa*a%MOD; e1; } return r; } struct Query{int n,s,c,r;}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; vectorQuery qs(T); int M0; for(auto q:qs){ cinq.nq.sq.cq.r; Mmax(M,max(q.n,q.s)); } vectorint64 fact(M1), ifact(M1); fact[0]1; for(int i1;iM;i) fact[i]fact[i-1]*i%MOD; ifact[M]qpow(fact[M],MOD-2); for(int iM;i1;i--) ifact[i-1]ifact[i]*i%MOD; auto C [](int n,int k)-int64{ if(n0 || k0 || kn) return 0; return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; }; for(auto q:qs){ if(q.r0){ cout(q.s0 ? 1 : 0)\n; continue; } if(q.rq.n || q.sq.r || (long long)q.s(long long)q.r*q.c){ cout0\n; continue; } int maxjmin(q.r,(q.s-q.r)/q.c); int64 ways0; for(int j0;jmaxj;j){ int topq.s-j*q.c-1; int64 termC(q.r,j)*C(top,q.r-1)%MOD; if(j1) ways(ways-termMOD)%MOD; else ways(waysterm)%MOD; } coutC(q.n,q.r)*ways%MOD\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。跨模委员会一、题目题目名称跨模委员会题目内容某学校共有 N 名候选人。其中有三个互不重叠的特殊部门A 部门有 A 人B 部门有 B 人C 部门有 C 人。其余 N-A-B-C 人不属于这三个部门中的任何一个。现在要从全部 N 名候选人中选出恰好 K 人组成委员会并要求1. A 部门至少有 1 人入选2. B 部门至少有 1 人入选3. C 部门至少有 1 人入选。候选人都是互不相同的。给定一个质数 P请输出方案数对 P 取模后的结果。注意N、A、B、C、K 都可能非常大最大可达到 10^18。输入第一行两个整数 P、Q其中 P 为质数Q 为询问数量。接下来 Q 行每行五个整数N A B C K保证0 ABC N0 K N输出对于每个询问输出一行答案表示满足要求的委员会数量模 P。样例输入7 410 2 3 2 420 5 4 3 6100 20 20 20 501000000000000 100 200 300 10样例输出4204数据范围2 P 200000且 P 为质数1 Q 1000000 N,A,B,C,K 10^18ABC NK N提示当组合数的上标、下标远大于模数 P 时普通阶乘预处理无法直接使用。时间限制普通/Java3000 MS / 15000 MS空间限制262144 KByte数据输出限制1024 KByte二、解题思路题解跨模委员会先做三集合容斥再用 Lucas 定理计算巨大组合数。题目没有直接要求“求 C(N,K) mod P”因此需要先完成组合建模。定义三个坏事件EAA 部门无人入选EBB 部门无人入选ECC 部门无人入选。总委员会数量C(N,K)题目要求三个坏事件都不发生。使用三集合容斥Ans C(N,K)- C(N-A,K)- C(N-B,K)- C(N-C,K) C(N-A-B,K) C(N-A-C,K) C(N-B-C,K)- C(N-A-B-C,K)问题变成多次求C(X,K) mod P但 X、K 可达 10^18而 P 是不超过 2×10^5 的质数。使用 Lucas 定理。把 n、k 写成 P 进制n n0 n1*P n2*P^2 ...k k0 k1*P k2*P^2 ...则C(n,k) mod PΠ C(ni,ki) mod P如果某一位 kini则这一项为 0整个组合数为 0。因为每个 ni、ki 都小于 P只需要预处理fact[0..P-1]ifact[0..P-1]然后小组合数C(ni,ki)fact[ni]*ifact[ki]*ifact[ni-ki] mod P每次 Lucas 的复杂度为 O(log_P N)。每个询问只需要 8 次 Lucas。需要特别注意1. P 可能很小例如 P2此时 P 进制位数会比较多2. 不能把“除法”直接当成普通整数除法3. C(n,k) 在 kn 时应返回 04. 容斥过程中要随时规范到 [0,P-1]。时间复杂度预处理 O(P)每个询问 O(8 log_P N)。空间复杂度O(P)。三、解题代码#include bits/stdc.h using namespace std; using int64long long; using u64unsigned long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int P,Q; cinPQ; auto qpow [](long long a,long long e){ long long r1%P; while(e){ if(e1) rr*a%P; aa*a%P; e1; } return r; }; vectorlong long fact(P), ifact(P); fact[0]1; for(int i1;iP;i) fact[i]fact[i-1]*i%P; ifact[P-1]qpow(fact[P-1],P-2); for(int iP-1;i1;i--) ifact[i-1]ifact[i]*i%P; auto smallC [](int n,int k)-long long{ if(k0 || kn) return 0; return fact[n]*ifact[k]%P*ifact[n-k]%P; }; auto Lucas [](u64 n,u64 k){ long long ans1; while(n || k){ int nin%P; int kik%P; if(kini) return 0LL; ansans*smallC(ni,ki)%P; n/P; k/P; } return ans; }; while(Q--){ u64 n,a,b,c,k; cinnabck; u64 s[3]{a,b,c}; long long ans0; for(int mask0;mask8;mask){ u64 removed0; int bits0; for(int i0;i3;i){ if(maski1){ removeds[i]; bits; } } long long valLucas(n-removed,k); if(bits1) ans-val; else ansval; ans%P; } if(ans0) ansP; coutans\n; } return 0; }四、代码解释1. 使用快速幂函数计算模意义下的逆元方便组合数计算。2. 预处理阶乘 fact 和逆阶乘 ifact将组合数 C(n,k) 和排列数 P(n,k) 的计算优化为 O(1)。3. 主函数读取输入根据题目中的限制条件判断无解情况。4. 按照解题思路中的数学公式计算答案并在每一步进行取模。5. 代码整体复杂度通常为预处理 O(N)每组数据 O(1)适合大规模测试。