首页 > 代码库 > hdu4869

hdu4869

2024-07-15 13:40:51   217人阅读

题意：给你n张牌，一开始都是背面朝下的，现在有一些操作，每次操作都可以随意改变s[i]张牌的状态，问最后的牌有多少种状态。

标程题解：

最终的结果一定是连续出现的，只需要求出最终的区间。

因为如果对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数，那么最终结果也一定是奇数。同理，偶数也是一样的。

所以只要递推求出最后的区间，计算sum（C（xi，m）（i=0，1，2。。。）），m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是最终的答案。

 

根据它的思路，可以求出一个区间，就是最后还有多少张牌朝上的一个区间，这个区间要么是连续的偶数，要么是连续的奇数。

求出区间，还需要用到一个费马小定理+快速幂 解决C(m,k) %mod

费马小定理+快速幂 解决C(m,k) %mod：

 

C(m,k)=m!/(k!*(m-k)!)    对C(m,k)取模mod

 

取模运算规则：

 

  1. (a + b) % p = (a % p + b % p) % p （1）
  2. (a - b) % p = (a % p - b % p) % p （2）
  3. (a * b) % p = (a % p * b % p) % p （3）
  4. a ^ b % p = ((a % p)^b) % p （4）

 

在求 m!/(k!*(m-k)!)的时候由于有除法不能像以上那样一步取模一次，因此我们想到了用费马小定理把分母转化成整数再用第三条求模。

 

 

 

费马小定理：假如a是整数，p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。

 

                 那么a^(p-1)/a = 1/a%p 得到1/a%p= a^(p-2) ,  将一个分数的值化成了整数

 

  因此在求以上令a=k!*(m-k)!   ,   p=mod(即mod=1000000009)，

 

  1/(k!*(m-k)!)  %mod= (k!*(m-k)!)^(mod-2)

 

于是这个题目可以ac了......

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;typedef __int64 ss;const ss inf=100005;const ss mod=1000000009;ss s[inf],n,m;ss f[inf];ss deal(ss x,ss y){    if(y==1)    return x;    if(y%2==0)    {        ss sum=deal(x,y/2)%mod;        return (sum*sum)%mod;    }    else    {        ss sum=deal(x,y/2)%mod;        return sum*sum%mod*x%mod;    }}int main(){    f[0]=1;    f[1]=1;    for(ss i=2;i<=inf-4;i++)    f[i]=f[i-1]*i%mod;    while(scanf("%I64d%I64d",&n,&m)>0)    {        ss minx=0,maxn=0;        ss p,p1;        for(ss i=0;i<n;i++)        {            scanf("%I64d",&s[i]);        }        minx=0;        maxn=0;        for(ss i=0;i<n;i++)        {            if(minx>=s[i]) p=minx-s[i];            else if(s[i]<=maxn)            {                if(maxn%2==s[i]%2)                p=0;                else p=1;            }            else p=s[i]-maxn;            if(maxn+s[i]<=m) p1=maxn+s[i];            else if(minx+s[i]<=m)            {                if(m%2==(minx+s[i])%2)                p1=m;                else p1=m-1;            }            else p1=2*m-(minx+s[i]);            minx=p;            maxn=p1;        }        //printf("%I64d %I64d\n",minx,maxn);        ss sum=0;        for(ss i=minx;i<=maxn;i+=2)        {            sum+=((f[m]%mod)*(deal((f[i]*f[m-i])%mod,mod-2)%mod))%mod;            sum%=mod;        }        printf("%I64d\n",sum%mod);    }    return 0;}

　　

 


联系
我们