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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define re register
 5 using namespace std;
 6 int max(int a,int b){return a>b?a:b;}
 7 const int W=10000000;
 8 int x,k;
 9 struct bigsum{
10     int a[25],len;
11     bigsum(){memset(a,0,sizeof(a));len=0;}
12     bigsum operator + (const bigsum &tmp) const{
13         bigsum c; int x=0;
14         c.len=max(len,tmp.len);
15         for(int i=1;i<=c.len;++i){
16             c.a[i]=a[i]+tmp.a[i]+x;
17             x=c.a[i]/W;c.a[i]%=W;
18         }
19         for(;x;x/=W) c.a[++c.len]=x%W;
20         return c;
21     }
22     void print(){//注意压位高精输出时每一位的前导0
23         printf("%d",a[len]);
24         for(int i=len-1;i>=1;--i){
25             for(int j=10;a[i]*j<W;j*=10) putchar(48);
26             printf("%d",a[i]);
27         }
28     }
29 }C[1001][1001];
30 int Pow(int x,int y){
31     int res=1;
32     for(;y;y>>=1,x=1ll*x*x%1000)
33         if(y&1) res=1ll*res*x%1000;
34     return res;
35 }
36 int main(){
37     scanf("%d%d",&k,&x); x%=1000;x=Pow(x,x);
38     for(int i=0;i<x;++i)
39         for(int j=0;j<=i;++j){
40             if(!j||j==i) C[i][j].a[C[i][j].len=1]=1;
41             else C[i][j]=C[i-1][j]+C[i-1][j-1];
42         }//杨辉三角递推
43     C[x-1][k-1].print();
44     return 0;
45 }