题意
给定一个数 \(n\)，要求将 \(n\) 表示成一些 \(4^{k}\) 的数之和或差的形式，要求用的数最少，求方案数。
思路
首先看到这道题的数据范围 \(n\le10^{1000}\)，又是求方案数，所以想到用数位 DP。因为每一个数都是 \(4\) 的次幂，显然我们需要讲原数转化为 \(4\) 进制，具体方法不多讲述。
最重要的还是 DP 方程的设计了。题目说可以在两数之间做加减运算，所以必须考虑一个很重要的东西——借位。因为减法运算的过程中会出现向高位借位的情况。举个例子：\((013)_{4} = (020)_{4} - (001)_{4}\)，可以发现，如果要借位的话，当前数位上的数从 \(3\) 变成了 \(1\)，也就是从 \(i\) 变成了 \(4-i\)。被借的那一位上从 \(1\) 变成了 \(2\)，也就是从 \(i\) 变成了 \(i+1\)。于是 DP 方程便可以推出来了。
设 \(f_{i}\) 表示不向高位借位时算到第 \(i\) 位时的方案数，\(g_{i}\) 表示要向高位借位时算到第 \(i\) 位时的方案数，则有：
-
\(f_{i} = (f_{i - 1} + b_{i}) + (g_{i - 1} + b_{i} + 1)\)
-
\(g_{i} = (f_{i - 1} + 4 - b_{i}) + (g_{i - 1} + 3 - b_{i} )\)
注意：这里的 f 和 g 均是结构体数组，加号的意义在结构体内经过了重定义，具体意义详见代码。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
#define inf 0x3f3f3f3f
typedef pair <int,int> pii;
const int MAXN = 5e3 + 10;
const int mod = 1e9;
int a[MAXN],cnt,b[MAXN],n;
char c[MAXN];
struct Node
{
int x,y;Node(){};
//x为数的个数，y为方案数
Node(int a,int b){x = a,y = b;}
inline Node operator + (int a){return Node(x + a,y);}
//结构体加普通数：数的个数相加，方案数不变
inline Node operator + (Node b){return x == b.x ? Node(x,(y + b.y) % mod) : (x < b.x ? Node(x,y) : b);}
//结构体加结构体：如果数的个数相等，则方案数相加；否则选数的个数较少的情况时的方案数。
}f[MAXN],g[MAXN];
signed main()
{
cin >> c + 1;
int len = strlen(c + 1);
for(int i = len;i >= 1;i--) a[i] = c[len - i + 1] - '0';
while(len)
{
a[0] = 0;
for(int i = len;i >= 1;i--)
{
a[i - 1] += ((a[i] % 4) * 10);
a[i] = (a[i] - a[i] % 4) / 4;
}
b[++cnt] = a[0] / 10;
if(a[len] == 0) len--;
}
cnt++;
f[0] = Node(0,1),g[0] = Node(MAXN,0);
for(int i = 1;i <= cnt;i++)
{
f[i] = (f[i - 1] + b[i]) + (g[i - 1] + b[i] + 1);
g[i] = (f[i - 1] + (4 - b[i])) + (g[i - 1] + (3 - b[i]));
}
cout << f[cnt].y;
return 0;
}