题解：P1771 方程的解
Binah_cyc
·
·
题解
无耻的推销我的高精模板
看见题解区并没有使用暴力 dp 卡过去的，作为一个卡常爱好者我当然要写一篇题解来造福后人。
看到这个题的第一反应就是 dp，我们有一个很显然的式子：
我们可以写出一份十分 naive 的代码：
```
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e4+5;
#define int long long
namespace high_precision
{
const int NUM_SIZE=35,len=7,maxn=pow(10,len);
struct bigint
{
vector<long long> a;
void clear()
{
a.clear();
a.push_back(0);
}
void change()
{
while(!a.back()) a.pop_back();
if(!a.size()) a.push_back(0);
}
bigint(long long y=0)
{
a.clear(),a.push_back(y);
a.resize(10);
for(int i=0; a[i]>=maxn; i++) a.push_back(a[i]/maxn),a[i]%=maxn;
change();
}
};
void print(bigint now)
{
if(now.a.size()==1&&now.a.back()==0) return (void)(cout<<0);
cout<<now.a.back();
for(int i=now.a.size()-2; i>=0; i--)
{
int tmp=now.a[i],sze=0;
while(tmp) tmp/=10,sze++;
for(int i=sze+1; i<=len; i++) cout<<0;
if(now.a[i]) cout<<now.a[i];
}
}
const bool operator!=(bigint x,bigint y)
{
if(x.a.size()!=y.a.size()) return 1;
for(int i=x.a.size()-1; i>=0; i--) if(x.a[i]!=y.a[i]) return 1;
return 0;
}
const bigint operator+(bigint x,bigint y)
{
bigint z;
z.clear();
int sze=max(x.a.size(),y.a.size())+1;
x.a.resize(sze),y.a.resize(sze),z.a.resize(sze);
for(int i=0; i<sze; i++)
{
z.a[i]+=x.a[i]+y.a[i];
if(z.a[i]>=maxn) z.a[i+1]++,z.a[i]%=maxn;
}
z.change();
return z;
}
const bigint operator+=(bigint &x,bigint y){x=x+y;return x;}
}
using namespace high_precision;
int n,x,val;
int power(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans;
}
bigint dp[105][1005];
bigint solve(int x,int val)
{
if(!val) return 0;
if(dp[x][val]!=0) return dp[x][val];
if(x==1) return dp[x][val]=1;
bigint ans=0;
for(int i=1;i<=val;i++) ans+=solve(x-1,val-i);
return dp[x][val]=ans;
}
signed main(signed argc,char** argv)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>x;
val=power(x,x,1000);
print(solve(n,val));
return 0;
}
```
[评测记录](https://www.luogu.com.cn/record/185532914)
我们有了 $40$ 分的好成绩。
看一下这份代码，它仍然有很多可以修改的地方，~~还能继续卡常~~。
在使用 __int128 压 $35$ 位~~并简单卡常~~之后，我们得到了常数更加亲民的代码，限于篇幅不贴。优化没什么用处，只优化了 $0.2 s$。[评测记录](https://www.luogu.com.cn/record/185532175)
在上政治课的时候，我突然想到了一个十分有用的优化：使用普通数组来代替 vector。作用十分明显，~~至少最慢的点不再是 1.20 s 了。~~[评测记录](https://www.luogu.com.cn/record/185532702)
随后，我又尝试使用 fwrite 来优化输出。这一步非常有用，直接让我的代码来到了 80 分！~~实际上多交几发卡卡评测机波动就过了。~~[评测记录](https://www.luogu.com.cn/record/185533648)
这一步的代码
```
#include<bits/stdc++.h>
using namespace std;
#define int unsigned
int n,x,val;
bool vis[105][1005];
struct bigint
{
__int128 a[15];
int sze=0;
bigint(__int128 y=0){sze=0;a[++sze]=y;}
} dp[105][1005];
__int128 maxn=1;
char pbuf[1<<20],*pp=pbuf;
void push(const char &c){*pp++=c;}
void print(__int128 x)
{
static int sta[35];
int top=0;
do{sta[top++]=x%10,x/=10;}while(x);
while(top) push(sta[--top]+'0');
}
void print(bigint now)
{
print(now.a[now.sze]);
for(int i=now.sze-1;i;i--)
{
__int128 tmp=now.a[i],sze=0;
while(tmp) tmp/=10,sze++;
for(int i=35;i>sze;i--) push('0');
if(now.a[i]) print(now.a[i]);
}
}
bigint operator+(bigint x,bigint y)
{
if(x.sze<y.sze) swap(x,y);
bigint z=x;
z.a[++z.sze]=0;
for(int i=1;i<=y.sze;i++) z.a[i]+=y.a[i],(z.a[i]>=maxn)?(z.a[i+1]++,z.a[i]-=maxn):0;
while(!z.a[z.sze]) z.sze--;
return z;
}
int power(long long a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans;
}
bigint solve(int x,int val)
{
if(vis[x][val]) return dp[x][val];
vis[x][val]=1;
int t=val-x+1;
for(int i=1;i<=t;i++) dp[x][val]=dp[x][val]+solve(x-1,val-i);
return dp[x][val];
}
signed main(signed argc,char** argv)
{
cin>>n>>x;
for(int i=1;i<=35;i++) maxn*=10;
val=power(x,x,1000);
for(int i=1;i<=val;i++) dp[1][i]=1,vis[1][i]=1;
print(solve(n,val));
fwrite(pbuf,1,1<<20,stdout);
}
```
然后，同机房的大佬 @[zcz0263](https://www.luogu.com.cn/user/760433)指出了我的问题：你的代码怎么用的是记忆化搜索实现的啊！
然后，我去写了一份循环式的代码，就过了，甚至没有用到 fwrite。
最终的代码：
```
#include<bits/stdc++.h>
using namespace std;
int n,x,val;
struct bigint
{
__int128 a[15];
int sze;
bigint(__int128 y=0){a[sze=1]=y;}
} dp[105][1005];
__int128 maxn=1;
void print(__int128 x)
{
int sta[55];
int top=0;
do{sta[top++]=x%10,x/=10;}while(x);
while(top) putchar(sta[--top]+'0');
}
void print(bigint now)
{
print(now.a[now.sze]);
for(int i=now.sze-1;i;i--)
{
__int128 tmp=now.a[i];
int sze=0;
while(tmp) tmp/=10,sze++;
for(int i=35;i>sze;i--) putchar('0');
if(now.a[i]) print(now.a[i]);
}
}
const bigint operator+=(bigint &x,bigint y)
{
if(x.sze<y.sze) swap(x,y);
x.a[++x.sze]=0;
for(int i=1;i<=(signed)y.sze;i++) x.a[i]+=y.a[i],(x.a[i]>=maxn)?(x.a[i+1]++,x.a[i]-=maxn):0;
while(!x.a[x.sze]) x.sze--;
return x;
}
int power(long long a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans;
}
signed main(signed argc,char** argv)
{
cin>>n>>x;
for(int i=1;i<=35;i++) maxn*=10;
val=power(x,x,1000);
for(int i=1;i<=val;i++) dp[1][i]=1;
for(int i=2;i<=n;i++) for(int j=i;j<=val;j++) for(int k=1;k<=j-i+1;k++) dp[i][j]+=dp[i-1][j-k];
print(dp[n][val]);
}
```