# HDU 5226

```#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100005;
long long a[maxn], b[maxn], X1, X2, Y1, Y2, P, ans;
int n;

long long inv(long long x, long long m)
{
if (x == 1) return x;
return inv(m % x, m)*(m - m / x) % m;
}

long long C(int x, int y)
{
if (x > y) return 0;
return (a[y] * b[x]) % P * b[y - x] % P;
}

long long c(int x, int y)
{
if (x > y) return 0;
if (y >= P) return C(x % P, y % P)*c(x / P, y / P) % P;
else return C(x, y);
}

int main()
{
while (cin >> X1 >> Y1 >> X2 >> Y2 >> P)
{
a[0] = b[0] = 1;
for (int i = 1; i <= min(X2 + 1, P - 1); i++)
{
a[i] = (a[i - 1] * i) % P;
b[i] = inv(a[i], P);
}
ans = 0;
for (int i = Y1; i <= Y2; i++)
{
(ans += c(i + 1, X2 + 1) - c(i + 1, X1)) %= P;
}
(ans += P) %= P;
cout << ans << endl;
}
return 0;
}
```

## 组合数(Lucas定理) + 快速幂 --- HDU 5226 Tom and matrix

Tom and matrix Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=5226 Mean: 题意很简单,略. analyse: 直接可以用Lucas定理+快速幂水过的,但是我却作死的用了另一种方法. 方法一:Lucas定理+快速幂水过 方法二:首先问题可以转化为求(0,0),(n,m)这个子矩阵的所有数之和.画个图容易得到一个做法,对于n<=m,答案就是2^0+2^1+...+2^m=2^(m+1)-1,对于n>m

## HDU 5917 Instability ramsey定理

http://acm.hdu.edu.cn/showproblem.php?pid=5917 即世界上任意6个人中,总有3个人相互认识,或互相皆不认识. 所以子集 >= 6的一定是合法的. 然后总的子集数目是2^n,减去不合法的,暴力枚举即可. 选了1个肯定不合法,2个也是,3个的话C(n, 3)枚举判断,C(n, 4), C(n, 5) #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using name