企业官网建设流程全解析

数据型网站建设,做网站学什么代码,网络维护员工资多少,刘淼 网站开发2024年9月GESP真题及题解(C八级): 手套配对 题目描述 小杨有 nnn 对不同的手套#xff0c;每对手套由左右各一只组成。 小杨想知道从中取出 mmm 只手套#xff0c;mmm 只手套恰好包含 kkk 对手套的情况有多少种。 小杨认为两种取出的情况不同#xff0c;当且仅当两种情况…2024年9月GESP真题及题解(C八级): 手套配对题目描述小杨有n nn对不同的手套每对手套由左右各一只组成。小杨想知道从中取出m mm只手套m mm只手套恰好包含k kk对手套的情况有多少种。小杨认为两种取出的情况不同当且仅当两种情况取出的手套中存在不同的手套同一对手套的左右手也视为不同的手套。输入格式本题单个测试点内有多组测试数据。第一行包含一个正整数t tt代表测试用例组数。接下来是t tt组测试用例。对于每组测试用例一共一行。第一行包含三个正整数n , m , k n,m,kn,m,k代表手套数量取出的手套数和目标对数。输出格式对于每组测试数据输出一个整数代表可能的情况数量对10 9 7 10^971097取模的结果。输入输出样例 1输入 12 5 6 2 5 1 5输出 1120 0说明/提示子任务占比t ttn nnm mmk kk1 1130 % 30\%30%≤ 5 \leq 5≤5≤ 1000 \leq 1000≤1000≤ 3 \le 3≤3 1 112 2230 % 30\%30%≤ 5 \leq 5≤5≤ 5 \leq 5≤5≤ 10 \leq 10≤10≤ 5 \leq 5≤53 3340 % 40\%40%≤ 10 5 \leq 10^5≤105≤ 1000 \leq 1000≤1000≤ 2000 \leq 2000≤2000≤ 2000 \leq 2000≤2000对全部的测试数据保证1 ≤ t ≤ 10 5 , 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 2 × n , 1 ≤ k ≤ n 1 \leq t \leq 10^5,1 \leq n \leq 1000,1 \leq m \leq 2 \times n,1 \leq k \leq n1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。思路分析这是一个组合计数问题。我们有 n 对不同的手套每对手套有左、右手各一只。需要从这 2n 只手套中取出 m 只手套使得取出的手套恰好包含 k 对完整的手套即 k 对手套的左右手都在取出的集合中。关键点每对手套的左右手是不同的即左手和右手是不同的手套恰好包含 k 对完整的手套剩下的 (m-2k) 只手套必须是单只的不能形成新的完整对单只的手套不能来自已经配对的 k 对否则那一对就不完整了推导过程选择完整的 k 对从 n 对中选择 k 对方案数C(n, k)剩下的 (m-2k) 只单只手套这些单只手套必须来自剩下的 (n-k) 对中从 (n-k) 对中每对最多取 1 只否则会形成新的完整对从 (n-k) 对中选择 (m-2k) 对方案数C(n-k, m-2k)对于选择的每一对可以取左手或右手方案数2m − 2 k ^{m-2k}m−2k总方案数C(n, k) × C(n-k, m-2k) × 2m − 2 k ^{m-2k}m−2k边界条件当 m 2k 时不可能有 k 对完整的手套当 m-2k n-k 时不可能从 (n-k) 对中取出那么多单只手套因为每对最多取 1 只当 k n 时不可能有那么多对完整的手套算法设计预处理组合数 C[ n ] [ k ] [n][k][n][k]和 2 的幂次对于每个查询判断边界条件计算组合数公式时间复杂度预处理组合数O(N²)N1000每个查询O(1)总复杂度O(N² T)可以接受代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMOD1e97;constintN1010;// n的最大值constintM2010;// m的最大值// 组合数表ll C[N][N];// 2的幂次表ll pow2[M];// 预处理组合数和2的幂voidinit(){// 组合数预处理for(inti0;iN;i){C[i][0]C[i][i]1;for(intj1;ji;j){C[i][j](C[i-1][j]C[i-1][j-1])%MOD;}}// 2的幂预处理pow2[0]1;for(inti1;iM;i){pow2[i](pow2[i-1]*2)%MOD;}}intmain(){init();intt;cint;while(t--){intn,m,k;cinnmk;// 边界条件检查if(m2*k){cout0endl;continue;}intsinglem-2*k;// 单只手套数量// 单只手套不能超过剩余的对数if(singlen-k){cout0endl;continue;}// 计算方案数ll ansC[n][k];// 选择k对完整手套ansans*C[n-k][single]%MOD;// 选择哪些对取单只ansans*pow2[single]%MOD;// 每对可以选择左手或右手coutansendl;}return0;}功能分析变量说明C[N][N]组合数表C[i][j]表示从 i 个中选 j 个的组合数pow2[M]2 的幂次表pow2[i]表示 2^in手套对数m取出的手套总数k目标完整对数single m - 2*k单只手套的数量函数说明init()预处理组合数表和 2 的幂次表组合数使用递推公式C(n,k) C(n-1,k) C(n-1,k-1)2 的幂使用递推2^i 2^(i-1) * 2边界条件检查if (m 2 * k)如果取出的手套总数少于 2k不可能有 k 对完整的手套if (single n - k)如果单只手套数量大于剩余的对数无法满足每对最多取 1 只的条件公式计算C[n][k]从 n 对中选择 k 对完整手套C[n-k][single]从剩余的 (n-k) 对中选择 single 对来取单只手套pow2[single]对于每个选择的单只手套可以取左手或右手示例测试输入2 5 6 2 5 1 5计算过程n5, m6, k2single 6-4 2检查m6≥2k4single2≤n-k3计算C[ 5 ] [ 2 ] [5][2][5][2] 10, C[ 3 ] [ 2 ] [3][2][3][2] 3, pow2[2] 4结果10×3×4 120n5, m1, k5single 1-10 -9检查m12k10 → 输出 0复杂度分析预处理O(N²) 1000×1000 1e6 次运算每个查询O(1) 直接查表计算总查询最多10 5 10^5105次总复杂度可行各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}