首页 技术 正文
技术 2022年11月23日
0 收藏 935 点赞 3,066 浏览 2301 个字

Problem DescriptionDuring summer vacation,Alice stay at home for a long time, with nothing to do. She went out and bought m pokers, tending to play poker. But she hated the traditional gameplay. She wants to change. She puts these pokers face down, she decided to flip poker n
times, and each time she can flip Xi pokers. She wanted to know how many the results does she get. Can you help her solve this problem? InputThe input consists of multiple test cases. 

Each test case begins with a line containing two non-negative integers n and m(0<n,m<=100000). 

The next line contains n integers Xi(0<=Xi<=m). OutputOutput the required answer modulo 1000000009 for each test case, one per line. Sample Input

3 4
3 2 3
3 3
3 2 3

 Sample Output

8
3HintFor the second example:
0 express face down,1 express face up
Initial state 000
The first result:000->111->001->110
The second result:000->111->100->011
The third result:000->111->010->101
So, there are three kinds of results(110,011,101)

 

题意:对于m张牌给出n个操作,每次操作选择a[i]张牌进行翻转。问终于得到几个不同的状态思路:在n张牌选k张。非常easy想到组合数,可是关键是怎么进行组合数计算呢?我们能够发现,在牌数固定的情况下。总共进行了sum次操作的话,事实上有非常多牌是经过了多次翻转,而每次翻转仅仅有0和1两种状态,那么,奇偶性就出来了。也就是说,不管怎么进行翻牌,终于态不管有几个1,这些1的总数的奇偶性是固定的。那么我们如今仅仅须要找到最大的1的个数和最小的1的个数。然后再这个区间内进行组合数的求解就可以可是又有一个问题出来了,数据非常大,进行除法是一个不明智的选择。可是组合数公式必然有除法C(n,m) = n!/(m!*(n-m)!)可是我们知道费马小定理a^(p-1)=1%p那么a^(p-1)/a = 1/a%p 得到 a^(p-2) = 1/a%p发现了吧?这样就把一个整数变成了一个分母!于是便得到sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod用高速幂去撸吧!

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mod 1000000009
#define LL __int64
#define maxn 100000+5LL f[maxn];void set()
{
int i;
f[0] = 1;
for(i = 1; i<maxn; i++)
f[i] = (f[i-1]*i)%mod;
}LL quickmod(LL a,LL b)
{
LL ans = 1;
while(b)
{
if(b&1)
{
ans = (ans*a)%mod;
b--;
}
b/=2;
a = ((a%mod)*(a%mod))%mod;
}
return ans;
}int main()
{
int n,m,i,j,k,l,r,x,ll,rr;
set();
while(~scanf("%d%d",&n,&m))
{
l = r = 0;
for(i = 0; i<n; i++)
{
scanf("%d",&x);
//计算最小的1的个数,尽可能多的让1->0
if(l>=x) ll = l-x;//当最小的1个数大于x。把x个1所有翻转
else if(r>=x) ll = ((l%2)==(x%2))?0:1;//当l<x<=r,因为不管怎么翻。其奇偶性必然相等,所以看l的奇偶性与x是否同样,同样那么知道最小必然变为0,否则变为1
else ll = x-r;//当x>r,那么在把1所有变为0的同一时候,还有x-r个0变为1
//计算最大的1的个数,尽可能多的让0->1
if(r+x<=m) rr = r+x;//当r+x<=m的情况下。所有变为1
else if(l+x<=m) rr = (((l+x)%2) == (m%2)?m:m-1);//在r+x>m可是l+x<=m的情况下,也是推断奇偶。同态那么必然在中间有一种能所有变为1,否则至少有一张必然为0
else rr = 2*m-(l+x);//在l+x>m的情况下。等于我首先把m个1变为了0,那么我还要翻(l+x-m)张。所以终于得到m-(l+x-m)个1 l = ll,r = rr;
}
LL sum = 0;
for(i = l; i<=r; i+=2)//使用费马小定理和高速幂的方法求和
sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod;
printf("%I64d\n",sum%mod);
} return 0;
}

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,723
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,328
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,154
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,973
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,619
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,637