hdu5226 Tom and matrix 公式，Lucas

本文主要是介绍hdu5226 Tom and matrix 公式，Lucas，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给定x1,y1,x2,y2,求和C(i,j)，(x1<=i<=x2,y1<=j<=y2)，结果%p。

分析：因为\sum_{i=a}^{b}C_{i}^{k}=C_{b+1}^{k+1}-C_{a}^{k+1}∑​i=a​b​​C​i​k​​=C​b+1​k+1​​−C​a​k+1​​ 所以求同一列的数的和可以变成求两个组合数的差。由于p可能很小，当除数为p的倍数时就为0了，直接乘逆元会出问题，利用Lucas。

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 1000000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=100005;
ll p;
ll jiech[100005];
ll inv[100005];
ll powMod(ll a,ll b)
{if(b==0)return 1;ll ans=powMod(a,b/2);ans=ans*ans%p;if(b&1)ans=ans*a%p;return ans;
}
ll C(int a,int b)
{if(a<b)return 0;ll u=jiech[a]*inv[b]%p*inv[a-b]%p;return u;
}
ll Lucas(int a,int b)
{if(a<b)return 0;if(b==0)return 1;ll ret=C(a%p,b%p)*Lucas(a/p,b/p)%p;return ret;
}
int main()
{int x1,y1,x2,y2;while(cin>>x1>>y1>>x2>>y2>>p){jiech[0]=1;inv[0]=1;for(int i=1;i<=min((int)p-1,x2+1);i++){jiech[i]=jiech[i-1]*i%p;}int tt=min((int)p-1,x2+1);inv[tt]=powMod(jiech[tt],p-2);for(int i=tt-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%p;ll ans=0;for(int i=y1+1;i<=y2+1;i++){ans=(ans+Lucas(x2+1,i))%p;ans=(ans-Lucas(x1,i)+p)%p;}cout<<ans<<endl;}return 0;
}

这篇关于hdu5226 Tom and matrix 公式，Lucas的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---