本文主要是介绍hdu - 4869 - Turn the pokers（组合数学 + 乘法逆元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：m 张牌，开始时全部正面朝下，翻转 n 次，每次翻转 xi 张牌，问最后的结果有多少种(0<n,m<=100000, 0<=Xi<=m)？
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4869
——>>假如最后有 a 张牌正面朝上，则它的结果有 C[m][a] 种（组合数），所以，只要求出最后可能有多少张牌正面朝上，再累加其组合数可行。。
1）求最后正面牌数的上下界；
2）以 2 为间隙进行枚举（可以取两个连续区间来试试，连续的区间最小变动为2，头尾变）。
#include <cstdio>typedef long long LL;const int MOD = 1000000009;
const int MAXN = 100000;int n, m;
int L, R;
LL f[MAXN + 10];void Init()
{L = R = 0;
}void Read()
{int x;for (int i = 0; i < n; ++i){scanf("%d", &x);int bufR = R;if (R + x <= m){R += x;}else{if (L + x > m){R = m - (L + x - m);}else{if ((m - L - x) & 1){R = m - 1;}else{R = m;}}}if (x <= L){L -= x;}else{if (x > bufR){L = x - bufR;}else{if ((x - L) & 1){L = 1;}else{L = 0;}}}}
}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 -= a / b * x;}
}LL Inv(int a, int n)
{LL ret = 0, d, y;Gcd(a, n, d, ret, y);return d == 1 ? (ret + n) % n : -1;
}void GetF()
{f[0] = f[1] = 1;for (int i = 2; i <= MAXN; ++i){f[i] = i * f[i - 1] % MOD;}
}LL C(LL n, LL m)
{return f[n] * Inv(f[m] * f[n - m] % MOD, MOD) % MOD;
}void Solve()
{LL ret = 0;for (int i = L; i <= R; i += 2){ret = (ret + C(m, i)) % MOD;}printf("%I64d\n", ret);
}int main()
{GetF();while (scanf("%d%d", &n, &m) == 2){Init();Read();Solve();}return 0;
}
这篇关于hdu - 4869 - Turn the pokers（组合数学 + 乘法逆元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
