Skip to content

题解-P3464

Posted on:2023年7月18日 at 09:54

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

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

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

题面大意

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

解题思路

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

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

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

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

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

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

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

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

  1. 将值加上 11 个更大(是现在 44 倍)的数,为了保持这两位的数字总和不变,仍是原来的 4i1(ci1)+4ici4^{i-1}(c_{i-1})+4^ic_i,将其减去 4i1(4ci1)4^{i-1}(4-c_{i-1}),总花费为 5ci15-c_{i-1} 个数。
    fi,j+5ci1,1fi1,j,0f_{i,j+5-c_{i-1},1} \leftarrow f_{i-1,j,0}
  2. 将值加上 11 个更大(是现在 44 倍)的数,为了保持这两位的数字总和不变,仍是原来的 4i(ci+1)4^i (c_i+1)(因为上一位有进位),将其减去 3(ci1+1)=2ci13-(c_{i-1}+1) = 2-c_{i-1},总花费为 3ci13-c_{i-1} 个数。
    fi,j+3ci1,1fi1,j,1f_{i,j+3-c_{i-1},1} \leftarrow f_{i-1,j,1}
    然后代码就不难写了,容易发现第一位可以滚掉节省空间(校内赛只给 32M),最后结果是第一个非零的 fn,i,0+fn,i,1f_{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;
}


在 Rickyxrc's blog 出现的文章,若无特殊注明,均采用 CC BY-NC-SA 4.0 协议共享,也就是转载时需要注明本文章的地址,并且引用本文章的文章也要使用相同的方式共享。