题解-P3464

· · 题解

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

模拟赛 T1 是这个，然后喜提保龄，有感而发，写一篇题解。

十分感谢 itshawn 和 刘辰雨 对本题解的二次润色打磨，并修复了很多讲的不清楚和错误的细节。

题面大意

给定一个数 n，要求将 n 表示成一些 4^k 的数之和/差的形式，要求用的数最少，求方案数模 10^9 的结果。

解题思路

首先我们不难想到使用高精度，将 n 进行四进制拆分，拆成低位起的数组。

例如 (166)_{10} = (2212)_{4}，我们的 c 数组就是 [2,1,2,2]，下文所讨论的状态转移均在此前提下进行。

然后我们考虑状态设计，我们定义第一维为已经规划到的位数，第二维为使用的数字总量，第三维为是否有数字进位到下一位。

注意：在我们的状态转移过程中，使用的数字凑出的总和始终不变，我们只是在进行等价变换。

那么我们就针对进位和不进位分别讨论。

如果这一位不进位，那么我们就直接将数放上去。

f_{i,j+c_i,0} \leftarrow f_{i-1,j,0}+f_{i-1,j,1}

如果这一位有进位，那么我们需要考虑两种情况：

  1. 将值加上 1 个更大（是现在 4 倍）的数，为了保持这两位的数字总和不变，仍是原来的 4^{i-1}(c_{i-1})+4^ic_i，将其减去 4^{i-1}(4-c_{i-1})，总花费为 5-c_{i-1} 个数。 f_{i,j+5-c_{i-1},1} \leftarrow f_{i-1,j,0}
  2. 将值加上 1 个更大（是现在 4 倍）的数，为了保持这两位的数字总和不变，仍是原来的 4^i (c_i+1)（因为上一位有进位），将其减去 3-(c_{i-1}+1) = 2-c_{i-1}，总花费为 3-c_{i-1} 个数。 f_{i,j+3-c_{i-1},1} \leftarrow f_{i-1,j,1}

    然后代码就不难写了，容易发现第一位可以滚掉节省空间（校内赛只给 32M），最后结果是第一个非零的 f_{n,i,0}+f_{n,i,1}。

代码如下：

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>

#define maxn 3007

typedef long long i64;

const i64 mod = 1000000000;

int min(int a, int b);
int max(int a, int b);

struct Int
{
    int li[maxn], len;
    Int();
    void fix();
    void read();
    void write();
    int &operator[](int x);
};
Int operator+(Int a, Int b);
Int operator*(Int a, i64 b);
i64 pow(i64 x, i64 p);
bool operator>(Int a, Int b);
bool operator==(Int a, Int b);
Int operator-(Int a, Int b);

Int n, c, pow4[maxn];
i64 res = 0, mxval, cnt[maxn], now, dp[2][maxn][2];

int main()
{
    n.read();

    pow4[0][0] = 1, pow4[0].len = 1;

    for (mxval = 1; mxval < maxn; mxval++)
    {
        pow4[mxval] = pow4[mxval - 1] * 4;
        if (pow4[mxval] > n)
            break;
    }

    for (int j = mxval - 1; j >= 0; j--)
    {
        while (n > pow4[j])
            cnt[j]++,
                n = n - pow4[j];
        if (pow4[j] == n)
        {
            cnt[j]++;
            break;
        }
    }

    dp[now][0][0] = 1;
    for (int i = 0; i < mxval; i++)
    {
        now ^= 1;
        memset(dp[now], 0, sizeof dp[now]);
        for (int j = 0; j + cnt[i] < maxn; j++)
        {
            dp[now][j + cnt[i]][0] = (dp[now][j + cnt[i]][0] + dp[now ^ 1][j][0]) % mod;
            dp[now][j + cnt[i]][0] = (dp[now][j + cnt[i]][0] + dp[now ^ 1][j][1]) % mod;
            dp[now][j + 5 - cnt[i]][1] = (dp[now][j + 5 - cnt[i]][1] + dp[now ^ 1][j][0]) % mod;
            dp[now][j + 3 - cnt[i]][1] = (dp[now][j + 3 - cnt[i]][1] + dp[now ^ 1][j][1]) % mod;
        }
    }

    for (int i = 0; i < maxn; i++)
        if (dp[now][i][0] + dp[now][i][1])
        {
            printf("%d", dp[now][i][0] + dp[now][i][1]);
            return 0;
        }

    return 0;
}