[1]组合
题目描述
给出组合数 C(n,m) 表示从 n 个元素中选出 m 个元素的方案数。例如 C(5,2)=10,C(4,2)=6。可是当 n,m 比较大的时候，C(n,m) 很大。于是 xiaobo 希望你输出C(n,m)modp 的值。
输入
输入数据第一行是一个正整数 T，表示数据组数；

接下来是 T 组数据，每组数据有 3 个正整数 n,m,p。

对于所有数据，T≤100，1≤m≤n≤109，m≤104，m<p<109，p 是素数。

输出
对于每组数据，输出一个正整数，表示 C(n,m)modp 的结果。
样例输入
2
5 2 3
5 2 61
样例输出
1
10
思路:
Lucas定理模板题,
因为n,m的值太大所以要简化运算, C(m, n) = C(m mod p, n mod p) * C(m / p, n / p) (mod p)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;

ll fpow(ll a,ll b,ll n){
	if(b==1) return a;
	if(b%2 == 1){
		ll t = fpow(a,b/2,n);
		t = t * t % n;
		t = t * a % n;
		return t; 
	}
	else{
		ll t = fpow(a,b/2,n);
		t = t * t % n;
		return t;
	}
} 

ll comb(ll n,ll m,ll p){
	if(m>n)return 0;
	if(m==0)return 1;
	ll up = 1 ,down = 1;
	for(ll i = 1 ; i <= m ; i++){
		up = (up * (n-i+1)) % p;
		down = (down * i) % p ; 
	} 
	return up * fpow(down,p-2,p) % p;
} 

ll lucas(ll n, ll m ,ll p ){
	if(m==0) return 1;
	return comb(n%p,m%p,p) * lucas(n/p,m/p,p) % p;
}

int main(void)
{
	int t;
	cin>>t;
	while(t--){
		ll n,m,p;
		cin>>n>>m>>p;
		cout<<lucas(n,m,p)<<endl;
	} 
}

[2] 牡牛和牝
题目描述
约翰要带 N 只牛去参加***里的展示活动，这些牛可以是牡牛，也可以是牝牛。牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 K 只牝牛。
请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 5000011 取模。
输入
一行，输入两个整数 N 和 K。
对于全部数据，1≤N≤105,0≤K<N。
输出
一个整数，表示排队的方法数。
样例输入
4 2
样例输出
6
样例说明:
六种方法如下 :
牝牝牝牝，牡牝牝牝，牝牡牝牝，牝牝牡牝，牝牝牝牡，牡牝牝牡
思路:
, 枚举牡牛的数量m，将总牛数减去至少需要的牝牛数量后记为n，则每种数量的答案就为C(n,m)，答案就是把合法答案加起来,即ans=ΣC(n-(i-1)*k,i),

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
 
const int mod=5000011;
ll n,k,ans;
 
ll ksm(ll a,ll b)
{
    ll ans = 1;
    a = a % mod;
    while(b)
    {
      if(b&1) ans = (ans * a) % mod;
      b >>= 1;
      a = (a * a) % mod;
    }
    return ans % mod;
}
 
ll C(ll n,ll m)
{
    if(m > n) return 0;
	if(m == 0) return 1;
    ll a=1,b=1;
    for(ll i=n-m+1;i<=n;i++)
		a = a * i % mod;
    for(ll i=2;i<=m;i++)
		b = b * i % mod;
    return a * ksm(b,mod-2) % mod; 
}
 
 ll Lucas(ll n,ll m)
{
    if(!m) 
		return 1;
    else 
		return (C(n % mod , m % mod) % mod * Lucas(n / mod , m / mod) % mod) % mod;
}
 
int main(void)
{
    cin>>n>>k;
    for(ll i=0;i<=n;i++)
    {
      ll j=n-(i-1)*k;
      if(j<i)  break;
      ans=(ans+Lucas(j,i))%mod;
    }
    cout<<ans<<endl;
 
    return 0;
}

[3] 方程的解
题目描述
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程
a1+a2+⋯+ak−1+ak=g(x)，
其中 k≥2 且 k∈N∗，x 是正整数，
g(x)=xxmod1000（即 xx 除以 1000 的余数），x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当 k=3,x=2 时，方程的解分别为：
a1=1,a2=1,a3=2
a1=1,a2=2,a3=1
a1=2,a2=1,a3=1
输入
有且只有一行，为用空格隔开的两个正整数，依次为k,x。
对于 40% 数据，答案不超过 1016；
对于全部数据，1≤k≤100,1≤x<231,k≤g(x)。
输出
有且只有一行，为方程的正整数解组数。
样例输入
3 2
样例输出
3
思路:
这题求得是正整数解,只要把计算出来的g(x)拆成若干个1然后插板法就行了,
算g(x)可以用快速幂求解,然后数据很大要用高精度计算不然会wa,


 	#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int mod=1000;
    int a[10100];
    int k,x;
    
    int mulm(int a,int b){
        if(b==1) return a;
        int t=mulm(a,b>>1);
        t*=t;
        t%=mod;
        if(b%2==1){
            t*=a;
            t%=mod;
        }
        return t;
    }
    
    void comb(int n,int m){
        a[1]=1;
        a[0]=1;
        for(int i=m+1;i<=n;i++){
            for(int j=1;j<=a[0];j++){
                a[j]*=i;
            }
            int tmp=0;
            for(int j=1;j<=a[0];j++){
                tmp+=a[j];
                a[j]=tmp%10;
                tmp/=10;
            }
            while(tmp){
                a[++a[0]]=tmp%10;
                tmp/=10;
            }
        }
        for(int i=2;i<=n-m;i++){
            int tmp=0;
            for(int j=a[0];j>=1;j--){
                tmp*=10;
                tmp+=a[j];
                a[j]=0;
                if(tmp>i){
                    a[j]=tmp/i;
                    tmp%=i;
                }
            }
            while(a[a[0]]==0) a[0]--;
        }
    }
    
    int main(){
        cin>>k>>x;
        x%=mod;
        x=mulm(x,x);
        comb(x-1,k-1);
        for(int i=a[0];i>=1;i--) 
    		cout<<a[i];
        return 0;
    }