Solution -「CF520E」Pluses everywhere

\[{\Large \mathbb{No \ hay \ cosa \ mas \ feliz \ en \ el \ mundo \ que \ ver \ tu \ sonrisa \ mi \ Miffy}} \]

Step 1.

转化一步题目：考虑有 \(n\) 个小球，每个小球有 \(a_i\) 的价值，\(m\) 个板子，把板子插进小球间的空隙，且不能插在第 \(1\) 个球之前与第 \(n\) 个球之后。

且规定对于任意一个方案，若第 \(i\) 个球与下一块板子间相隔 \(j\) 个球，则该球对答案的贡献为 \(10^j a_i\)。现需要求出每一个方案每一个球的贡献和。

这题显然和原题是等价的（转化可能是因为它更组合一些 www），因为对于任意一个方案中的任意一个数字来说，只有它和下一个加号之间的数的个数会影响它对总答案的贡献。

于是我们考虑上面那个问题的答案。

对于第 \(i\) 个球，我们枚举 \(j\)，并尝试求出会有多少方案使得目前的状态成立。可以发现 \(0 \leq j \leq n - i\)。

可以明确第 \(i\) 个球后的 \(j\) 个球之间都不能再插板，且第 \(j\) 个球和第 \(j + 1\) 个球之间一定需要插板、总共有 \(n - 1\) 个位置可以插板。那么也就是说总方案应该是在剩下的 \(n - 1 - j - 1\) 个空位中插 \(m - 1\) 个板的方案数，即 \(\dbinom {n - j - 2} {m - 1}\)。

特殊的，如果 \(j = n - i\)，则柿子会有所改变。因为第 \(n\) 个球后不能插板，所以说可以转化为在 \(i\) 以前的能插的位置中插入 \(m\) 个板的方案，即 \(\dbinom {i - 1} {m}\)。

显然当前状态的第 \(i\) 个球的贡献应是 \(10^j a_i\)，故总答案为 \({\large \sum \limits _{i = 1}^{n}} {\large \sum \limits _{j = 0}^{n - i - 1}} \dbinom {n - j - 2} {m - 1} 10^j a_i + {\large \sum \limits _{i = 1}^{n}} \dbinom {i - 1} {m} 10^{n - i} a_i\)。

这是 \(O(n^2)\) 的求解过程，不能通过，于是考虑优化。

Step 2.

你会发现，如果我们，确定了 \(j\)，则我们也可以确定有多少 \(i\)，可以得到该 \(j\) 的贡献，具体来讲，对于一个 \(j\)，所有 \(1 \leq i \leq n - j\)，都能得到 \(j\) 的贡献，因为这些球的后面都有 \(j\) 个球可以用于隔开自己和下一个加号。

当然这里仍需要考虑当前球后面都不再放加号的特殊情况，仍是单拎出来计算。

于是就可以直接来枚举 \(j\)。记 \(S(x) = {\large \sum \limits _{i = 1}^{x}} a_i\)，则答案可写为 \({\large \sum \limits _{j = 0}^{n - 1}} 10^jS(n - j - 1)\dbinom {n - i - 2} {m - 1} + {\large \sum \limits _{i = 1}^{n}} \dbinom {i - 1} {m} 10^{n - i} a_i\)。

提前初始化组合数、\(10\) 的次方都是基本功了嘛。

Code.

#include 

typedef long long LL;
int Abs(int x) { return x < 0 ? -x : x; }
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }

int read() {
    int x = 0, k = 1;
    char s = getchar();
    while(s < '0' || s > '9') {
        if(s == '-')
            k = -1;
        s = getchar();
    } 
    while('0' <= s && s <= '9') {
        x = (x << 3) + (x << 1) + (s ^ 48);
        s = getchar();
    }
    return x * k;
}

void write(int x) {
    if(x < 0) {
        x = -x;
        putchar('-');
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void print(int x, char s) {
    write(x);
    putchar(s);
}

const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5;

char s[MAXN];
int fac[MAXN], inv[MAXN], q[MAXN], p[MAXN], sum[MAXN];

inline int Sub(int x) { return x < 0 ? x + mod : x; }
inline int Plus(int x) { return x >= mod ? x - mod : x; }
inline int C(int n, int m) { 
    if(n < m)
        return 0;
    return (LL)fac[n] * inv[m] % mod * inv[n - m] % mod; 
}

void init() {
    inv[1] = 1;
    for(int i = 2; i < MAXN; i++)
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
    fac[0] = 1, inv[0] = 1, p[0] = 1;
    for(int i = 1; i < MAXN; i++) {
        p[i] = (LL)p[i - 1] * 10 % mod;
        fac[i] = (LL)fac[i - 1] * i % mod;
        inv[i] = (LL)inv[i - 1] * inv[i] % mod;
    }
}

int main() {
    init();
    int n = read(), m = read();
    scanf ("%s", s + 1);
    for(int i = 1; i <= n; i++) {
        q[i] = s[i] - '0';     
        sum[i] = Plus(sum[i - 1] + q[i]);   
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = Plus(ans + (LL)sum[n - i - 1] * p[i] % mod * C(n - i - 2, m - 1) % mod);
    for(int i = 1; i <= n; i++)
        ans = Plus(ans + (LL)q[i] * p[n - i] % mod * C(i - 1, m) % mod);
    print(ans, '\n');
    return 0;
}

相关

标签