P1771方程的解

前缀知识 [快速幂](https://www.luogu.org/problem/P1226)，[高精度加法](https://www.luogu.org/problem/P1601) 看到这道题时，我蒙了一会儿，想打个暴力交上去却发现暴力也不好打； 于是，我开始了~~颓废~~手玩； 由于 $k<=g(x)$, 我开始了推算； 先不管 $x^x$%1000 就先推将X分成K个数有多少种方案；  显然，这是一个杨辉三角，我们只需要做$k-1$次前缀和就能得到第$k$列的值； 注意，最后输出的是$f[x-k+1]$ 由于这个X很大，写个快速幂会快很多； 于是就有了第一个代码 ```cpp #include<iostream> #include<cstdio> #include<cctype> using namespace std; inline long long read() { long long x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } long long xx,k; inline long long poww(long long x,long long i) { long long ans=1; while(i) { if(i&1)ans=(ans*x)%1000; i>>=1; x=(x*x)%1000; } return ans%1000; } unsigned long long f[1001]; int main() { k=read();xx=read(); xx=poww(xx%1000,xx); for(int i=1;i<=xx;i++)f[i]=1; for(int i=1;i<k;i++) for(int j=1;j<=xx;j++)f[j]+=f[j-1]; cout<<f[xx+1-k]<<endl; return 0; } ``` 但是，它会爆！ 于是不得不写高精； 我们把$f[]$拓展一维，保存数值 AC代码 ```cpp #include<iostream> #include<cstdio> #include<cctype> using namespace std; inline long long read()//快读 { long long x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } long long xx,k; inline long long poww(long long x,long long i)//快速幂 { long long ans=1; while(i) { if(i&1)ans=(ans*x)%1000; i>>=1; x=(x*x)%1000; } return ans%1000; } long long f[1010][1010]; inline void jia(int x,int y) { for(int i=1;i<=max(f[x][0],f[y][0]);i++) f[x][i]+=f[y][i]; for(int i=1;i<=max(f[x][0],f[y][0]);i++) { if(f[x][i]>=100000000)//压位高精更快一点 { long long temp=f[x][i]/100000000; f[x][i]%=100000000; f[x][i+1]+=temp; } } if(f[x][f[x][0]+1])f[x][0]++; } int main() { k=read();xx=read(); xx=poww(xx%1000,xx); for(int i=1;i<=xx-k+1;i++)f[i][0]=f[i][1]=1;//初始化第一列 for(int i=1;i<k;i++) { for(int j=1;j<=xx-k+1;j++)//前缀和 jia(j,j-1); } int l=xx+1-k; printf("%lld",f[l][f[l][0]]);//压位高精的输出 for(int i=f[l][0]-1;i>=1;i--) { printf("%lld",f[l][i]/10000000); printf("%lld",f[l][i]/1000000%10); printf("%lld",f[l][i]/100000%10); printf("%lld",f[l][i]/10000%10); printf("%lld",f[l][i]/1000%10); printf("%lld",f[l][i]/100%10); printf("%lld",f[l][i]/10%10); printf("%lld",f[l][i]%10); } return 0; } ``` 你以为这就完了吗，~~我也以为完了~~ 经过我~~百度~~查找资料 杨辉三角第N行第M个数可以直接求！ 第n行的m个数可表示为$C(n-1,m-1)$，即为从n-1个不同元素中取m-1个元素的组合数。 -----百度百科 但我组合数学没学过，这个代码咕了。