本文主要是介绍hdu4869（逆元+求组合数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//输入n，m，n表示翻牌的次数，m表示牌的数目，求经过n次操作后共有几种状态#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define MOD 1000000009
#define N 100000+5
#define ll __int64
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N];
ll c[N];
void gcd(ll a,ll b,ll &d,ll &x,ll &y)
{if(!b) {d = a;x = 1; y = 0;}else{gcd(b,a%b,d,y,x);y -= x*(a/b);}
}
ll inv(ll a,ll n)
{ll d,x,y;gcd(a,n,d,x,y);return d == 1 ? (x+n)%n : -1;
}
void init(int n)
{c[0] = 1;c[1] = n;for(int i = 2; i <= n; i++)c[i] = (((c[i-1]*(n-i+1))%MOD)*inv((ll)i,(ll)MOD))%MOD;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n,m;while(cin>>n>>m)//m张纸牌{init(m);int i;for(i = 0; i < n; i++)cin>>a[i];int l,r;l = r = a[0];for(i = 1; i < n; i++){int lll,rr;if(a[i] < l) lll = l-a[i];else if(a[i] <= r)lll = ((a[i]-l)&1);else lll = a[i]-r;if(a[i] < m-r) rr = r+a[i];else if(a[i] <= m-l)rr = m - ((a[i]-m+r)&1);else rr = m - (a[i]-(m-l));l = lll;r = rr;}// cout<<l<<" "<<r<<endl;ll ans = 0;//for(i = 1; i <= m; i++)// cout<<c[i]<<" ";//cout<<endl;for(i = l; i <= r; i += 2)ans = (ans+c[i])%MOD;cout<<ans<<endl;}return 0;
}这篇关于hdu4869（逆元+求组合数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
