P1771方程的解
Frost_Delay
2019-08-23 19:27:06
前缀知识 [快速幂](https://www.luogu.org/problem/P1226),[高精度加法](https://www.luogu.org/problem/P1601)
看到这道题时,我蒙了一会儿,想打个暴力交上去却发现暴力也不好打;
于是,我开始了~~颓废~~手玩;
由于 $k<=g(x)$,
我开始了推算;
先不管 $x^x$%1000
就先推将X分成K个数有多少种方案;
![](https://cdn.luogu.com.cn/upload/pic/74489.png)
显然,这是一个杨辉三角,我们只需要做$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个元素的组合数。
-----百度百科
但我组合数学没学过,这个代码咕了。