# HDU4869:Turn the pokers(费马小定理+高速幂)

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 43 2 33 33 2 3`

Sample Output

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

`#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模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用