加法方案

· · 个人记录

加法方案

Description

对于一个数字 n 的拆数字操作如下：

求所有拆数字的方案的答案之和，对 998244353 取模。

对于 50\% 的数据，n \le 10^{10^3}；

对于 100\% 的数据，n \le 10^{10^6}；

Solution 1

首先我们将输入的数字翻转，定义 a_1 为原数的个位数，a_2 为原数的十位数，以此类推，数字总共长 len 位。

接下来考虑每个数对答案的贡献。

对于第 i 个数位 a_i，如果它作为拆出来的数的第 j 位的话，我们需要计算它存在于几个不同的数中。即，有多少个拆出来的数的第 j 位是 a_i。

由于 a_i 是第 j 位，所以在 i 前面的 1 \sim i - 1 位中应该选择 j - 1 个数位才能满足拆出来的数的第 j 位是 a_i。因此前面的方案数为 C_{i - 1} ^{ j - 1}。

对于 i 后面的 i + 1 \sim len 位，由于不管它们选还是不选都不会影响拆出来的数的第 j 位是 a_i，所以后面的方案数为 2^{len - i}。因此总共有 C_{i - 1}^{j - 1} \times 2^{len - i} 个拆出来的数的第 j 位是 a_i。

第 j 位上填 a_i 本身的贡献为 a_i \times 10^{j - 1}，因此它对答案的总贡献为 a_i \times 10^{j - 1} \times C_{i - 1}^{j - 1} \times 2^{len - i}。

暴力计算这个式子时间复杂度为 \mathcal O(len^2)，可以获得 50 分。

Solution 2

为了方便描述，我们将答案式写下来：

\sum_{i = 1}^{len} \sum_{j = 1}^i (a_i \times 10^{j - 1} \times C_{i - 1}^{j - 1} \times 2^{len - i})

把与 j 无关的 a_i 和 2^{len - i} 提出来，有：

\sum_{i = 1}^{len} \left( a_i \times 2^{len - i} \times \sum_{j = 1}^i (10^{j - 1} \times C_{i - 1}^{j - 1})\right)

问题来到了如何快速计算 \sum_{j = 1}^i (10^{j - 1} \times C_{i - 1}^{j - 1}) 上。

由于用到的都是 j - 1，所以我们把式子变为 \sum_{j = 0}^{i - 1} (10^{j} \times C_{i - 1}^{j})。

如果你用程序打几个这样的数字的表，你会得到这样的结果：

1
11
121
1331
14641（指一万四千六百四十一）

神奇的是这些数字竟然就是杨辉三角！

我们将上面式子中的 \sum 展开，即 10^{0} \times C_{i - 1}^{0} + 10^1 \times C_{i - 1}^1 \times 10^2 \times C_{i - 1}^2 + \cdots，可以发现这样计算确实可以得到一个杨辉三角的某一行。

那么问题就转换成了，如何把杨辉三角某一行上的数字按照上面的方式写下来。

我们定义 F(n) 表示第 n 行上的数字，那么我们计算 F(n + 1) 时需要把 F(n) 上的相邻两位加起来（即杨辉三角的性质）。具体如图：

那么我们如如何快速地根据 F(n) 计算 F(n + 1) 呢？

考虑进行一个错位，并与原数相加。具体如图：

那么就得到下一行的值了。

考虑完成这个操作。把 F(n) 往左错一位实际上是 F(n) \times 10，与原数相加为 F(n) \times 10 + F(n)。因此可以得到递推式：

F(n) = 11F(n - 1)\\F(0) = 1

可以看出的是，F(n) = 11^n。于是问题就解决了。

整理一下，答案为：

\sum_{i = 1}^{len} (a_i \times 2^{len - i} \times 11^{i - 1})

于是预处理 2 和 11 的幂，就可以 \mathcal O(len) 解决了。吊打std

一些问题：

  1. 一个数字是可以被拆出来两次的，也就是说计算最终答案时需要将答案乘 2。例如在 123 这个例子中，如果最开始选出 1 个数，有可能被分成 2, 13 两个数，但如果最开始选出 2 个数，仍然可能会分成这两个数。因此答案需要乘 2；
  2. 如果最开始将所有的数字都选出了，那么这个值的答案不需要乘 2。因为题目要求求是不能选出 0 个数的。

Code


#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define re register
#define il inline

const int N = 100010, P = 998244353;

char s[N];
int a[N], res;
int n;

il int fpm(re int a, re int b)
{
    re int res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % P;
        b >>= 1, a = (LL)a * a % P;
    }
    return res;
}

int p10[N], p11[N], p2[N];

il void init()
{
    p10[0] = p11[0] = p2[0] = 1;
    for (re int i = 1; i < N; ++ i )
        p11[i] = p11[i - 1] * 11ll % P,
        p2[i] = p2[i - 1] * 2ll % P,
        p10[i] = p10[i - 1] * 10ll % P; 
}

int k;

int main()
{
    init();

    scanf("%s", s);
    n = strlen(s);

    for (re int i = 1; i <= n; ++ i )
        a[i] = s[n - i] - '0';

    for (re int i = 1; i <= n; ++ i )
        res = (res + (LL)a[i] * p2[n - i] % P * p11[i - 1] % P) % P;

    res = res * 2ll % P;

    for (re int i = 1; i <= n; ++ i )
        res = ((res - (LL)a[i] * p10[i - 1] % P) % P + P) % P;

    cout << res;

    return 0;
}