F-有趣的数字（组合数+逆元）

题目链接：https://ac.nowcoder.com/acm/contest/699/F

题目意思：给出a,b,c,k,e,f,g。问多项式（ax+by+cz）^k 中 x^ey^fz^g的系数为多少（k=e+f+g）。

思路：根据排列组合的思维，容易想到 x^e是从k项中 选e次 即 C(e,k);

　　　而剩下的k-e=f+g项中选y^f即从f+g项选f次，即C(f,f+g);而剩下的g项不用再选了只能是z了。

　　　所以答案是 C(e,k)*C(f,f+g)*pow(a,e)*pow(b,f)*pow(c,g)%mod;

写法有很多种，下面写了两种写法：

写法一：用数组cc[ ][ ]存组合数 cc[i][j]的意思就是 C(i,i+j)  。因为cc[i][j]（从i+j项选了i个x,j个y）

而cc[i][j]=cc[i-1][j]+cc[i][j-1]  相当于从选了（i-1）项x,j项y,再选一项x， 加上  从选了 i项x,(j-1)项y, 再选一项y,(有点像dp)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#include<queue>
using namespace std;
typedef long long ll;
const ll mod=10007;
ll cc[1050][1050];
ll q_pow(ll a,ll b) 
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    ll a,b,c,e,f,g,k,ans=0;
    cin>>a>>b>>c>>k>>e>>f>>g;
    for(int i=0;i<=1000;i++)
        cc[i][0]=cc[0][i]=1;
    for(int i=1;i<=1000;i++)
        for(int j=1;i+j<=1000;j++)
            cc[i][j]=(cc[i-1][j]+cc[i][j-1])%mod;
    ans=(cc[e][f+g]*cc[f][g])%mod;
    ans=(ans*q_pow(a,e))%mod; 
    ans=(ans*q_pow(b,f))%mod; 
    ans=(ans*q_pow(c,g))%mod; 
    cout<<ans%mod<<endl;
    return 0;
}

写法二：用fac数组存阶乘。因为C(e,k)=k!/(e!*(k-e)!)  而C(f,f+g)=(f+g)!/(f！*g!)

　　所以C(e,k)*C(f,f+g)= k!/(e!*f!*g!) （因为k-e=f+g）

　　直接用逆元处理即可。因为给出的mod是一个质数，所以用费马小定理即可，且代码简单。

　　

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
#include<queue>
using namespace std;
typedef long long ll;
const ll mod=10007;
ll fac[1050];
ll q_pow(ll a,ll b) 
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    fac[0]=1;
    for(int i=1;i<=1000;i++)
        fac[i]=(fac[i-1]*i)%mod;
    ll a,b,c,k,e,f,g,ans;
    cin>>a>>b>>c>>k>>e>>f>>g;    
    ans=q_pow(a,e)%mod;
    ans=ans*q_pow(b,f)%mod;
    ans=ans*q_pow(c,g)%mod;
    ans=ans*fac[k]*q_pow(fac[e],mod-2)%mod;
    ans=ans*q_pow(fac[f],mod-2)%mod*q_pow(fac[g],mod-2)%mod;
    cout<<ans<<endl;
    return 0; 
}