数位DP。
首先分析下题目，将 \(n\) 表示成一些 \(4^k\) 的数之和/差的形式 ，就可以理解为一个天平，\(n\) 放在左边，可以选一些数值为 \(4\) 的幂的砝码，放左/右都行，在让天平平衡，求方案数。
\(4^k\) 很容易联想到四进制，于是考虑把 \(n\) 转换为四进制后进行数位 DP，就比较好想了。
设 \(dp[i][j][k]\) 表示（\(4\) 进制下的 \(n\)）从低到高第 \(i\) 位，已经用了 \(j\) 个砝码，这一位进/不进位，\(k:0/1\) 的方案数。关于进位这一状态，转移时会讲解。
记 \(fr[i]\) 表示 \(n\) 在四进制下第 \(i\) 位的值。
那么状态设计好了，就可以开始愉快的转移了。
首先考虑和的形式（砝码和物品不在一边）:
- \(dp[i][j+fr[i]][0]=dp[i][j+fr[i]][0]+dp[i-1][j][0]\) 直接填当前数位上的值，从更低位转移过来。
- \(dp[i][j+fr[i]+1][0]=dp[i][j+fr[i]+1][0]+dp[i-1][j][1]\) 上一位有进位的情况，要加上低位进的一位再填。
关于进位：因为我们从低到高填砝码，在放的时候可能会有物品和砝码放一边，也就是减法的情况，这时我们就需要在另一边补一个更大的砝码来使天平平衡，相当于在更高位填一个砝码。
然后是差的形式（砝码和物品在一边）：
- \(dp[i][j+4-fr[i]][1]=dp[i][j+4-fr[i]][1]+dp[i-1][j][0]\)
- \(dp[i][j+4-fr[i]-1][1]=dp[i][j+4-fr[i]-1][1]+dp[i-1][j][1]\) 上一位有进位的情况，就可以少放一个砝码。
差形式因为砝码和物品放在了同一边，又因为这是四进制的数，所以我们考虑在这一边补上 \(4-fr[i]\) 个砝码，让这一位合成更大的一位，也就是进位，在天平另一边再放上这更大的一位使其平衡。所以差的形式 \(k\) 值为 \(1\)，表示需要进位。
这样就转移完了。
统计答案的话记 \(len\) 为 \(n\) 在四进制下的长度，从小到大枚举 \(j\) （因为要满足砝码数最少），找到第一个不为零的 \(dp[len][j][0]+dp[len][j-1][1]\)，输出即可。（因为如果用了 \(j-1\) 个砝码还要进位时，他就得再补一个砝码，最后总数也是 \(j\)，因此也要计入答案）。
注意：
- 本题 \(n<10^{1000}\)，需要用字符串读入。
- 直接开数组会炸空间，需要滚动数组优化。
其余细节在代码中呈现。
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s;
int n,a[100005],fr[100005],sum,num,cnt,dp[2][50005][2];
int now;
const int mod=1e9;
int main(){
cin>>s;
n=s.size();
for(int i=0;i<n;++i)a[i+1]=s[i]-'0';
while(1){//预处理四进制
bool f=0;
sum=0;
for(int i=1;i<=n;++i){
if(a[i])f=1;
sum=sum*10+a[i];//每次边乘边模，求出当前数除以四的余数，变转成四进制了。
a[i]=sum/4;//把这个数除以4。
sum%=4;
}
if(f)fr[++num]=sum;
else break;
}
dp[0][0][0]=1;//边界初始化。
for(int i=1;i<=num;++i){
now=i&1;//滚动数组
//因为每一位可以填四个，所以枚举个数时要为长度的4倍。
for(int j=0;j<=4*num;++j)dp[now][j][0]=dp[now][j][1]=0;
for(int j=0;j<=num*4;++j){
dp[now][j+fr[i]][0]=(dp[now][j+fr[i]][0]+dp[now^1][j][0])%mod;
dp[now][j+fr[i]+1][0]=(dp[now][j+fr[i]+1][0]+dp[now^1][j][1])%mod;
dp[now][j+4-fr[i]][1]=(dp[now][j+4-fr[i]][1]+dp[now^1][j][0])%mod;
dp[now][j+4-fr[i]-1][1]=(dp[now][j+4-fr[i]-1][1]+dp[now^1][j][1])%mod;
}
}
//找答案
for(int i=1;i<=4*num;++i)if(dp[now][i][0]+dp[now][i-1][1])return cout<<(dp[now][i][0]+dp[now][i-1][1])%mod,0;
return 0;
}