BZOJ 1111: [POI2007]四进制的天平Wag 进制拆分，DP求方案数

Description

Mary准备举办一个聚会，她准备邀请很多的人参加她的聚会。并且她准备给每位来宾准备一些金子作为礼物。为了不伤及每个人的脸面，每个人获得的金子必须相同。Mary将要用一个天平来称量出金子。她有很多的砝码，所有砝码的质量都是4的幂。Mary将金子置于左边并且将砝码置于右盘或者两个盘。她希望每次称量都使用最少的砝码。并且，他希望，每次都用不同的称量方法称出相同质量的金子。对于给定的质量n，Mary希望知道最少需要用多少个砝码可以完成称量，并且想知道用这么多个砝码一共有多少种方式进行称量。
Input

输入文件仅包含一个整数，表示Mary希望给每个人的金子的质量。（1<=n<=10^1000）
Output

输出文件仅包含一个整数，表示一共可能的称量方式对10^9的模。
Sample Input
166

Sample Output
3

样例解释

一共有三种方式称量出166。166=64+64+16+16+4+1+1。166=256-64-16-16+4+1+1。166=256-64-16-4-4-1-1。

解题方法：我们首先考虑把 n 转换成一个四进制数。我们记转换完的数有 m 位，第 i 位（从低到高）的值为 num[i]。我们发现对于第 i 位要想满足条件只有两种放置方法，第一种是在天平的右盘放 num[i]个 4 i 的砝码，第二种是在天平的右盘放 1 个 4 i＋ 1 的砝码，在天平的左盘放 4－num[i]个 4 i的砝码。因此我们可以考虑用 DP 解决，定义状态
dp[i][j]表示第 i 到 m 位已经处理完，dp[i][0]表示第 i 位不多放一个在右盘，dp[i][1]表示在第 i 位多放一个在右盘，最少需要放置的砝码个数。则有：

d p [i] [0] ＝ m i n (d p [i ＋ 1] [0] ＋ n u m [i], d p [i ＋ 1] [1] ＋ 4 － n u m [i]);

d p [i] [1] ＝ m i n (d p [i ＋ 1] [1] ＋ n u m [i] ＋ 1, d p [i ＋ 1] [1] ＋ 3 － n u m [i]);

对于方案数，只要在动态规划的过程中顺便处理一下就可以了。然后代码参考了Po爷，蒟蒻高精度巨TM炸。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
const int mod = 1e9;
struct bign
{
    int a[2010];
    int len;

    bign()
    {
        memset(a, 0, sizeof(a));
        len = 0;
    }

    inline void input()
    {
        char b[2010];
        scanf("%s", b + 1);
        len = strlen(b + 1);
        for(int i = 1; i <= len; i ++)
        {
            a[i] = b[len - i + 1] - '0';
        }
    }

    inline bign get_bign(int rhs)
    {
        bign ret;
        while(rhs)
        {
            ret.a[++ ret.len] = rhs % 10;
            rhs /= 10;
        }
        return ret;
    }

    inline bool operator < (const bign& rhs) const
    {
        if(len < rhs.len) return 1;
        if(len > rhs.len) return 0;
        for(int i = len; i >= 1; i --)
        {
            if(a[i] < rhs.a[i]) return 1;
            if(a[i] > rhs.a[i]) return 0;
        }
        return 0;
    }

    inline bool operator > (const bign& rhs) const
    {
        return rhs < *this;
    }

    inline bool operator == (const bign& rhs) const
    {
        return !((rhs < *this) | (*this < rhs));
    }

    inline bool operator <= (const bign& rhs) const
    {
        return *this == rhs || *this < rhs;
    }

    inline bool operator >= (const bign& rhs) const
    {
        return *this == rhs || *this > rhs;
    }

    inline bool operator != (const bign& rhs) const
    {
        return !(*this == rhs);
    }

    inline bign operator * (bign& rhs) const
    {
        bign ret;
        for(int i = 1; i <= len; i ++)
        {
            for(int j = 1; j <= rhs.len; j ++)
            {
                ret.a[i + j - 1] += a[i] * rhs.a[j];
                ret.a[i + j] += ret.a[i + j - 1] / 10;
                ret.a[i + j - 1] %= 10;
            }
        }
        ret.len = len + rhs.len - 1;
        if(ret.a[ret.len + 1]) ret.len ++;
        return ret;
    }

    inline bign operator * (int& rhs)
    {
        bign yt = get_bign(rhs);
        return *this * yt;
    }

    inline bign operator + (bign& rhs) const
    {
        bign ret;
        ret.len = max(len, rhs.len);
        for(int i = 1; i <= ret.len; i ++)
        {
            ret.a[i] += a[i] + rhs.a[i];
            ret.a[i + 1] += ret.a[i] / 10;
            ret.a[i] %= 10;
        }
        if(ret.a[ret.len + 1]) ret.len ++;
        return ret;
    }

    inline bign operator + (int& rhs)
    {
        bign yt = get_bign(rhs);
        return *this + yt;
    }

    inline bign operator - (const bign& rhs) const
    {
        bign ret;
        for(int i = 1; i <= len; i ++)
        {
            ret.a[i] += a[i] - rhs.a[i];
            if(ret.a[i] < 0) ret.a[i] += 10, ret.a[i + 1] --;
            if(ret.a[i]) ret.len = i;
        }
        return ret;
    }

    inline bign operator - (int& rhs)
    {
        bign yt = get_bign(rhs);
        return *this - yt;
    }

    inline bign operator / (const int& rhs) const
    {
        bign ret;
        int x = 0;
        for(int i = len; i >= 1; i --)
        {
            x = x * 10 + a[i];
            ret.a[i] = x / rhs;
            x %= rhs;
        }
        ret.len = len;
        while(!ret.a[ret.len] && ret.len) ret.len --;
        return ret;
    }

    inline int operator % (const int& rhs) const
    {
        int x = 0;
        for(int i = len; i >= 1; i --)
        {
            x = x * 10 + a[i];
            x %= rhs;
        }
        return x;
    }

    inline bign operator ^ (int rhs)
    {
        bign ret;
        ret = get_bign(1);
        bign nbc = *this;
        while(rhs)
        {
            if(rhs & 1) ret = ret * nbc;
            nbc = nbc * nbc;
            rhs >>= 1;
        }
        return ret;
    }

    inline void operator = (int x)
    {
        *this = get_bign(x);
        return;
    }

    inline void print()
    {
        for(int i = len; i >= 1; i --) printf("%d", a[i]);
    }
};
int stk[maxn], top;
pair <int, int> f[maxn], g[maxn];
//f[i]表示从第i位往前的最小花销及方案数
//g[i]表示从第i位往前+1的最小花销及方案数
//f[i]就是dp[i][0], g[i]就是dp[i][1]
void add(pair <int, int> &x, pair <int, int> y, int z)
{
    if(y.first + z < x.first)
    {
        x.first = y.first + z, x.second = 0;
    }
    if(y.first + z == x.first)
    {
        (x.second += y.second) %= mod;
    }
}
int main()
{
    bign n;
    n.input();
    while(n.len)
    {
        stk[++top] = n % 4;
        n = n / 4;
    }
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    f[top + 1] = {0, 1};
    g[top + 1] = {1, 1};
    for(int i = top; i >= 1; i--)
    {
        if(stk[i] == 0){
            add(f[i], f[i+1], 0);
            add(g[i], f[i+1], 1);
        }
        else if(stk[i] == 1){
            add(f[i], f[i+1], 1);
            add(g[i], f[i+1], 2);
            add(g[i], g[i+1], 2);
        }
        else if(stk[i] == 2){
            add(f[i], f[i+1], 2);
            add(f[i], g[i+1], 2);
            add(g[i], g[i+1], 1);
        }
        else{
            add(f[i], g[i+1], 1);
            add(g[i], g[i+1], 0);
        }
    }
    cout << f[1].second << endl;
    return 0;
}