コンビネーション数型取り

C(n,k)%pを求めます
pは素数
1、1=
2、1<=n、k<=10^18、p<=10^7、lucas定理を直接用いる.hdu3037        hdu3944
pは素数ではない
3、1=分解因子式再高速べき乗hdu 3398
4、1<=n、k<=10^18、P=p 1^c 1*p 2^c 2*p 3^c 3*…*pt^ct、piは素数、1≦pi^ci≦10^7.
まず各pi^ciに対してp因子を除いた結果とpiの個数を求め,さらに拡張ユークリッドで逆元を求め,最後にpiを乗じ,各結果に対して中国の残りの定理で統合した.詳細はACblog BZOJ 21142 2012 Petr Mitrichev Contest 10-Bを参照
ACcode:

/**
FZU2020
*/
#include
#include

typedef long long LL;
const int MS=10010;

LL res,b;
int n,m,p,t,r,T;
int c[MS],cnt;
int isprime[MS],pri[MS],top=0;

void prepare()
{
    for (int i=2;i0)
    {
        if (y&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans;
}

int main()
{
    prepare();
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        if ((n-m)

/**
hdu3398
*/
#include
#include

typedef long long LL;
const int NS=2000010;
const int MOD=20100501;

LL res;
int n,m,T;
int c[150000],cnt;
int isprime[NS],pri[150000],top=0;

void prime()
{
    for (int i=2;i=r)
        {
            t/=r;
            c[i]+=t*f;
        }
    }
    cnt=cnt>i?cnt:i;
}

LL quick_pow(int a,int y)
{
    LL ans=1,x=a;
    while (y>0)
    {
        if (y&1) ans=(ans*x)%MOD;
        x=(x*x)%MOD;
        y>>=1;
    }
    return ans;
}

int main()
{
    prime();
    scanf("%d",&T);
    while (T--)
    {
        cnt=0,res=1;
        memset(c,0,sizeof(c));
        scanf("%d %d",&n,&m);
        factor(m,-1);
        factor(n+m,1);
        factor(n+1,-1);
        int t=n-m+1;
        for (int i=0;i

/**
hdu3037
*/
#include
#include

typedef long long LL;

LL res,b;
int n,m,p,n0,m0,T;

LL quick_pow(LL x,int y,int mod)
{
    LL ans=1;
    while (y)
    {
        if (y&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        res=1,n=n+m;
        while (n>0||m>0)
        {
            n0=n%p,m0=m%p;
            n/=p,m/=p;
            if (n0

/**
hdu3944
*/
#include
#include

const int NS=9974;

int fac[NS][1229];
int isprime[NS],pri[NS],top=0;

void prepare()
{
    memset(isprime,0,sizeof(isprime));
    for (int i=2;i>=1)
    {
        if (y&1) ans*=x,ans%=mod;
        x*=x,x%=mod;;
    }
    return ans;
}

int combin(int n,int k,int p)
{
    int ans=1,x,y,q=isprime[p];
    while (k>0)
    {
        x=n%p,y=k%p;
        if (x

/**
BZOJ2142
*/
#include
#include

typedef long long LL;
const int NS=100010;

LL mod,sum,res;
int n,m;
int p[NS],q[NS],w[10],ac[NS];
int a[NS],c[NS],d[NS],cnt;
int isprime[NS],pri[NS],top=0;

void prime_table()
{
    for (int i=2; i1) ret*=x-1;
    return ret;
}


int quick_pow(int x,int y,int mo)
{
    int ans=1;
    while (y>0)
    {
        if (y&1) ans=((LL)ans*x)%mo;
        x=((LL)x*x)%mo;
        y>>=1;
    }
    return ans;
}

void divide(LL k)
{
    int t,r;
    for (int i=0; ipm) res=((LL)res*cal(k/pm,pos,flag))%y;
    return res;
}

int exgcd(int a1,int a2,int &x,int &y)
{
    if (!a2)
    {
        x=1,y=0;
        return a1;
    }
    int r=exgcd(a2,a1%a2,x,y);
    int t=x;
    x=y,y=t-a1/a2*y;
    return r;
}

int main()
{
    int rem,res;
    prime_table();
    while (~scanf("%lld%d%d",&mod,&n,&m))
    {
        sum=cnt=0,res=1;
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        for (int i=0; in)
        {
            printf("Impossible
");
            continue;
        }
        divide(mod);
        for (int i=0; i

/**
petr2012_B
*/
#include
#include
typedef long long LL;

const LL MOD2=1024;
const LL MOD5=9765625;
const LL MOD=10000000000LL;

LL n,m;
LL p[2],q[2],c[9];
int fac5[10000000],fac2[1111];

void prepare()
{
    fac5[0]=fac2[0]=1;
    for (int i=1;i>=1)
    {
        if (y&1) ans*=x,ans%=md;
        x*=x,x%=md;
    }
    return ans;
}

LL cal(LL k,int flag,int z)
{
    LL fd,x,ans;
    int md,y,r;
    md=flag?MOD5:MOD2;
    r=k%md,x=k/md;
    if (flag) y=5,fd=fac5[md-1],ans=fac5[r];
    else y=2,fd=fac2[md-1],ans=fac2[r];
    ans=(ans*qpow(fd,x,md))%md;
    c[flag]+=k/y*z;
    if (k>y) ans=(ans*cal(k/y,flag,z))%md;
    return ans;
}

LL Exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b)
    {
        x=1,y=0;
        return a;
    }
    LL r=Exgcd(b,a%b,x,y);
    LL t=x;
    x=y,y=t-a/b*y;
    return r;
}

int main()
{
    freopen("combi.in","r",stdin);
    freopen("combi.out","w",stdout);
    prepare();
    while (~scanf("%I64d%I64d",&n,&m))
    {
        c[0]=c[1]=0;
        p[0]=cal(n,0,1);
        q[0]=cal(n-m,0,-1);
        q[0]*=cal(m,0,-1);
        p[1]=cal(n,1,1);
        q[1]=cal(n-m,1,-1);
        q[1]*=cal(m,1,-1);
        q[0]%=MOD2,q[1]%=MOD5;

        LL x,y,res;
        Exgcd(q[0],MOD2,x,y);
        p[0]=(p[0]*x%MOD2+MOD2)*qpow(2,c[0],MOD2)%MOD2;
        Exgcd(q[1],MOD5,x,y);
        p[1]=(p[1]*x%MOD5+MOD5)*qpow(5,c[1],MOD5)%MOD5;
        Exgcd(MOD2,MOD5,x,y);
        res=p[0]*(y*MOD5%MOD)%MOD;
        Exgcd(MOD5,MOD2,x,y);

        res=(res+p[1]*(y*MOD2%MOD)+MOD)%MOD;

        x=1;
        double s=1;
        int flag=0;
        if (n-m=MOD)
            {
                flag=1;
                break;
            }
        }
        if (flag) printf("...%010I64d
",res);
        else printf("%I64d
",res);
    }
    return 0;
}