P1771 方程的解_NOI导刊2010提高（01）

P1771 方程的解_NOI导刊2010提高（01）

按题意用快速幂把$g(x)$求出来

发现这不就是个组合数入门题吗！

$k$个人分$g(x)$个苹果，每人最少分$1$个，有几种方法？

根据插板法，显然答案为$C(g(x)-1,k-1)$

蓝后写个高精度。（我曾经十分天真地认为$ans<=10^{50}$）

这里用压位+结构体重载高精。可以应对$ans<=10^{24*7}$的数据。

注意：存在x，P，$(x^x) \% P!=(x\% P)^{(x\% P)} \% P$

#include<iostream>

#include<cstdio>

#include<cstring>

#define re register

using namespace std;

int max(int a,int b){return a>b?a:b;}

const int W=;//压7位

int x,k;

struct bigsum{

    int a[],len;

    bigsum(){memset(a,,sizeof(a));len=;}

    bigsum operator + (const bigsum &tmp) const{

        bigsum c; int x=;

        c.len=max(len,tmp.len);

        for(int i=;i<=c.len;++i){

            c.a[i]=a[i]+tmp.a[i]+x;

            x=c.a[i]/W;c.a[i]%=W;

        }

        for(;x;x/=W) c.a[++c.len]=x%W;

        return c;

    }

    void print(){//注意压位高精输出时每一位的前导0

        printf("%d",a[len]);

        for(int i=len-;i>=;--i){

            for(int j=;a[i]*j<W;j*=) putchar();

            printf("%d",a[i]);

        }

    }

}C[][];

int Pow(int x,int y){

    int res=;

    for(;y;y>>=,x=1ll*x*x%)

        if(y&) res=1ll*res*x%;

    return res;

}

int main(){

    scanf("%d%d",&k,&x); x=Pow(x%,x);

    if(!x){puts("");return ;}

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

        for(int j=;j<=i;++j){

            if(!j||j==i) C[i][j].a[C[i][j].len=]=;

            else C[i][j]=C[i-][j]+C[i-][j-];

        }//杨辉三角递推

    C[x-][k-].print();

    return ;

}