首页 > 其他分享 >题解:P11250 [GESP202409 八级] 手套配对

题解:P11250 [GESP202409 八级] 手套配对

时间:2024-11-11 11:46:34浏览次数:3  
标签:预处理 时要 GESP202409 int 题解 times 手套 P11250 mod

题目传送门

思路讲解

一道非常经典的排列组合的题。

首先,我们要先从 n n n 对手套中取走 k k k 对,容易想到方案数为 C n k C_{n}^{k} Cnk​。

接下来,因为我们要恰好取走 k k k 对手套,所以剩下取走的 m − 2 × k m-2\times k m−2×k 只手套中不能出现有两个属于同一对的情况,所以我们只能从剩下的 n − k n-k n−k 对手套中选出 m m m 对,各取走一只左手套或者右手套,方案数为 2 m − 2 × k × C n − k m − 2 × k 2^{m-2\times k} \times C_{n-k}^{m-2\times k} 2m−2×k×Cn−km−2×k​。

最终,答案为 C n k × 2 m − 2 × k × C n − k m − 2 × k C_{n}^{k} \times 2^{m-2\times k} \times C_{n-k}^{m-2\times k} Cnk​×2m−2×k×Cn−km−2×k​。

我们只需通过杨辉三角预处理组合数,再预处理 2 2 2 的整数幂(当然也可以用快速幂),最后直接输出答案即可。

需要注意的是,预处理和统计答案时要及时取模,并且输出时要开 long long,否则可能会超过变量的上限。还有当 m − 2 × k < 0 m-2\times k<0 m−2×k<0 或 m − 2 × k > n − k m-2\times k>n-k m−2×k>n−k 时要直接输出 0 0 0。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,m,k;
int C[1003][1003],mi[2003];
int main(){
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=i;j++)
            C[i][j]=(j==0 || j==i?1:C[i-1][j]+C[i-1][j-1]),C[i][j]%=mod;
    mi[0]=1;
    for(int i=1;i<=2000;i++)
        mi[i]=mi[i-1]*2%mod;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        if(m-2*k<0 || m-2*k>n-k)
            printf("0\n");
        else
            printf("%lld\n",(1LL*C[n][k]*mi[m-2*k]%mod)*C[n-k][m-2*k]%mod);
    }
    return 0;
}

标签:预处理,时要,GESP202409,int,题解,times,手套,P11250,mod
From: https://blog.csdn.net/andycode_/article/details/143677763

相关文章

  • MySQL问题解决记录(1):IP address 'xxx.xxx.xxx.xxx' could not be resolved: 这是在主机
    目录问题描述排查流程解决方案总结问题描述[Warning][MY-010055][Server]IPaddress'xxx.xxx.xxx.xxx'couldnotberesolved:这是在主机名解析时通常出现的暂时错误,它意味着本地服务器没有从权威服务器上收到响应。问题表现:A主机的服务在访问B主机的MySQL数据库时,产......
  • Jmeter并发线程场景下共享变量错乱问题解决
    问题复现问题描述使用IF控制器获取前一个请求的后置脚本中设置的全局变量->并发线程下通过vars.get获取变量时,第一个线程和第二个线程获取的变量值一样->导致不同基础数据的请求入参一样方法如下:vars.put("shoppingCartIdList",shoppingCartIdList.toString());/......
  • CF1974题解
    闲话1974年第一次在东南亚打自由搏击就取得了冠军······CF1974A简单计数题点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt;signedmain(){ scanf("%lld",&t); while(t--){ intx,y,ans=0,num=0; scanf("%lld%lld",&x,......
  • [CodeForces] CF1978 题解
    A.AliceandBooksLink-CFLink-Luogu【题目大意】\(n\)本书,编号为\(1\)到\(n\),价值为\(a_1\)到\(a_n\)。将这些书分成两堆,你获得每堆编号最大的书的价值。求可以获得的最大的价值。【解题思路】无论怎样,编号为\(n\)的书不管在那一堆都是编号最大的,所以一定会有它......
  • luogu-P3262题解
    简要题意有一棵不超过十层的满二叉树,需要对每个节点进行染色。每个叶子节点会对其颜色相同的祖先节点产生贡献且黑白贡献不同。求最大贡献。题解首先我会暴力!我如果直接暴力枚举每个节点的颜色,复杂度就是\(O(2^{2^n})\)。然后还要算贡献,所以还有一个\(O(2^{n-1}(n-1))\)。然......
  • CF 1365 题解
    CF1365题解APrimeSubtraction任何数的因数中都会有质数,除非他是\(1\).因此原题不合法当且仅当\(b-a=1\).BKill'EmAll首先,答案有明确的下界:最右面的怪兽一定要处理.不断模拟去杀掉当前最靠右的怪兽,得到的答案就是答案的下界.是否能取到下界呢?答案是肯定......
  • CF622E Ants in leaves 题解
    传送门给定一棵\(n\)个节点的树,根节点是\(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过\(1\)秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。根结点的各个子树独立,因......
  • #C. [GESP202409 四级] 黑白方块 GESP四级考级
    这个是具体的代码,孩子的代码问题在子矩阵的判断有问题。就是这几行,没有具体实现。原思路代码块include<bits/stdc++.h>usingnamespacestd;intn,a,b,m[105][105];intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a>>b;for(intj=1;j<=a;j++){for(int......
  • ABC372D ABC379F 题解 单调栈二分
    ABC372DABC379F题解单调栈二分一直觉得AT上面学到的东西比CF要多一些,无意捧一踩一,但可能是我太菜的原因,毕竟ABC的题目普遍要比Div.2简单一些。好多次碰到这个单调栈里面二分的trick了,所以写一篇来总结一下。ABC372D形象地给定一系列Buildings的高度\(h\),保证每个......
  • P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度 题解
    P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来:\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{......