题意
有无限个质量为 $4$ 的幂的砝码，给定正整数 $n$，在使用的砝码数量尽可能少的情况下，求称量重量为 $n$ 的金子的方案数。($1 \leq n \leq 10^{1000}$)
题解
想想可以怎么凑出最后的 $n$，首先你可以全放在右盘；或者，也可以放更大的在右盘，再放些小的在左盘。
可以倒着考虑每位，因为显然想要凑出$(33)_4$，你不会选择放$15 \times 4^0$，而只会直接在当前位放需要的砝码数量（$3 \times 4^0$），或是放一个大一点的，再减去若干个小的（$1 \times 4^1 - 1 \times 4^0$）每位的影响最多只会在 $1$ 的幅度内影响到上一位（也就是在上一位借 $1$）。
那么就可以开始写转移啦。这里用顺推，设翻转后的 $n$ 在四进制下的每一位为 $a_{1..cnt}$，设$f_{i,j,0/1}$ 表示现在考虑四进制下的倒数第 $i$ 位，已经用了 $j$ 个砝码，倒数第 $i$ 位有没有被借 $1$。
所以初始化 $f_{1,0,0}=1$，答案就是第一个结果非 $0$ 的以下表达式 $f_{cnt+1,i,0}+f_{cnt+1,i-1,1}$
$f_{i,j,0} \Rightarrow f_{i+1,j+a[i],0}$ $f_{i,j,1} \Rightarrow f_{i+1,j+4-a[i],0}$ $f_{i,j,0} \Rightarrow f_{i+1,j+a[i]+1,1}$ $f_{i,j,1} \Rightarrow f_{i+1,j+4-(a[i]+1),1}$
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char orin[1101];int l=1,r;
int d[2222],n;
int f[2][6666][2];
int now=0;
const int mod=1e9;
int main(){
scanf("%s",orin+1);
r=strlen(orin+1);
for(int i=1;i<=r;++i)orin[i]-='0';
bool left=true;
while(left){
left=false;
int cur=0;
for(int i=1;i<=r;++i){
cur=cur*10+orin[i];
if(cur)left=true;
orin[i]=cur/4;cur%=4;
}
d[++n]=cur;
}
while(d[n]==0)--n;
f[now][0][0]=1;
for(int i=1;i<=n;++i,now=!now){
memset(f[!now],0,sizeof f[!now]);
for(int j=0;j<=6000;++j){
(f[!now][j+d[i]][0]+=f[now][j][0])%=mod;
(f[!now][j+(4-d[i])][1]+=f[now][j][0])%=mod;
(f[!now][j+d[i]+1][0]+=f[now][j][1])%=mod;
(f[!now][j+(4-d[i]-1)][1]+=f[now][j][1])%=mod;
}
}
for(int i=0;i<=6000;++i){
if(f[now][i][0]||f[now][i-1][1]){
printf("%d\n",(f[now][i][0]+f[now][i-1][1])%mod);
return 0;
}
}
}