bzoj1902【Zju2116】 Christopher

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1902

sol  ：一眼可以看出此题应用了lucas定理(逃~

　　　将n,m都化为p进制，记为a[],b[]

　　　则对于我们所求的C(n,m)%p，有C(n,m)=∏ (i from 1 to n) (p^i)*(C(a[i],b[i]))%p

　　　若C(n,m)为p的倍数，则存在某一位b[i]>a[i]

　　　即此题要求有多少个<n的数，且其p进制下存在某一位比n的p进制的对应位大

　　　求出a[]后直接数位dp即可

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int Mx=;

struct Node

{

    int n,g[];

    void pre(int k) {n=; g[]=k;}

    Node operator*(const int &b)

    {

        Node c; int y=; c.n=n;

        if(!b) { c.pre(); return c; }

        for(int i=;i<=n;i++) { y+=g[i]*b; c.g[i]=y%; y/=; }

        while(y) { c.g[++c.n]=y%; y/=; }

        return c;

    }

    Node operator+(const Node &b)

    {

        Node c; int y=,p;

        if(n>b.n)

        {

            c.n=n; for(int i=;i<=n;i++) c.g[i]=g[i]; p=b.n;

            for(int i=;i<=b.n;i++) { y+=b.g[i]+c.g[i]; c.g[i]=y%; y/=; }

            while(y&&p<n) { y+=c.g[++p]; c.g[p]=y%; y/=; }

        }

        else

        {

            c.n=b.n; for(int i=;i<=b.n;i++) c.g[i]=b.g[i]; p=n;

            for(int i=;i<=n;i++) { y+=g[i]+c.g[i]; c.g[i]=y%; y/=; }

            while(y&&p<b.n) { y+=c.g[++p]; c.g[p]=y%; y/=; }

        }

        if(y) c.g[++c.n]=y;

        return c;

    }

    int operator/(const int &b)

    {

        int y=;

        for(int i=n;i>=;i--)

        {

            y=y*+g[i];

            if (y<b) g[i]=;

            else {g[i]=y/b; y%=b;}

        }

        while(n>&&!g[n]) n--;

        return y;

    }

    void read()

    {

        char s[Mx]; scanf("%s",s+); n=strlen(s+);

        for(int i=;i<=n;i++) g[n+-i]=s[i]-'';

    }

} x,mul,ans,f[Mx];

int p,a[Mx],cnt;

int main()

{

    x.read(); scanf("%d",&p);

    while(x.n!=||x.g[]) a[++cnt]=x/p;

    f[].pre(),mul.pre(),ans.pre();

    for(int i=;i<cnt;i++)

    {

        f[i]=mul*(p--a[i]);

        f[i]=f[i]+f[i-]*(a[i]+);

        mul=mul*p;

    }

    for(int i=cnt;i>;i--) ans=ans+f[i-]*a[i];

    for(int i=ans.n;i>=;i--) printf("%d",ans.g[i]);

    return ;

}