首页 > 代码库 > HDU 4869 Turn the pokers 组合数学
HDU 4869 Turn the pokers 组合数学
链接:http://acm.hdu.edu.cn/showproblem.php?pid=4869
题意:有M张牌背面朝上,进行N次翻牌,每次翻Xi张(可以不连续),问进行N次翻牌后,最后所有牌面朝上朝下有多少种不同的情况。
思路:做比赛的时候有一些模糊的想法,赛后想来当时想的是正确的,不过当时逗比的去做了1005还没出(不是马后炮,捂脸哭)。其实面朝上的牌的数量是在一个固定的范围内的。由于翻开一张牌再翻回去要两次操作,所以朝上的牌的数量是同奇偶性的。两边的界限l和r是根据每次翻开牌的数量决定的。对于l有三种情况,r也有三种情况,很好理解,详见代码。然后就是用逆元求C(N,M)。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #include <set> #define PI acos(-1.0) #define maxn 10005 #define INF 0x7fffffff #define eps 1e-8 #define MOD 1000000009 typedef long long LL; typedef unsigned long long ULL; using namespace std; long long ex_gcd(long long a, long long b, long long &d, long long &x, long long &y) { if (!b) { x=1; y=0; d=a; } else { ex_gcd(b,a%b,d,y,x); y-=(a/b)*x; } } int inv(long long a,long long m) { long long d,x,y; ex_gcd(a,m,d,x,y); if (d==1) { x=(x%m+m)%m; return x; } else return -1; } int main() { int tot,t,m; long long c[100005]; while(~scanf("%d%d",&tot,&m)) { int l=0,r=0,x; for(int i=0; i<tot; i++) { scanf("%d",&x); int ll,rr; if(x<=l) ll=l-x; else if(x<r) ll=((x&1)==(l&1))?0:1; else ll=x-r; if(x+r<=m) rr=x+r; else if(x+l<=m) rr=(((l+x)&1)==(m&1))?m:m-1; else rr=2*m-(l+x); l=ll; r=rr; } long long ans=0; c[0]=1; if(0==l) ans+=c[0]; for(int i=1; i<=r; i++) { c[i]=(((c[i-1]*(m-i+1))%MOD)*(inv(i,MOD)))%MOD; if(i>=l&&((i+l)&1)==0) ans=(ans+c[i])%MOD; } printf("%I64d\n",ans); } return 0; }
HDU 4869 Turn the pokers 组合数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。