P3464 [POI2007] WAG-Quaternary Balance 题解

· · 题解

题意

给定一个数 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 和 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;
}