[Codeforces] Codeforces Round #675 (Div. 2) C. Bargain

2020年10月6日2020年12月12日

問題

数字列 \( n \) の部分列を取り除いて得られる整数の総和と求めます。

方針

部分列について

自然数 \( l \) を \( l = |n| \) とします。ここで、総和に対する \( i \) 文字目の整数 \( n_i \) の影響度を考えます。\( n_i \) を含まない文字列は、\( n_1 \) から \( n_{i – 1}\) の文字で構成される部分列 \( L_i \) と \( n_{i + 1} \) から \( n_l \) で構成される部分列 \( R_i \) のどちらかを \( n \) から取り除いたものとなります。 取り除くことができる部分列は連続なので、両方を取り除くことはできません。

\( n \) から \( L_i \) を取り除くとき

このとき、\( n_i \) の位は変化しません。これは、\( i + 1 \) 文字目以降の文字が取り除かれないためです。\( |L_i| = k \  ( 1 \leq k \leq i – 1 ) \) となる \( L_i \) の個数は、\( i – k \) 個あるので、累計で

\[ \dfrac{i(i -1)}{2}\]

個存在します。したがって、影響度は、

\[\dfrac{10^{i-1}n_ii(i -1)}{2}\]

となります。

\( n \) から \( R_i \) を取り除くとき

このとき、\( i + 1 \) 文字目以降の文字を取り除くことになるので、\( n_i \) の位が変化します。\( n_i \) の位が \( k \ (1 \leq k \leq l – i)\) となるときの \( R_i \) の個数は \( k \) となります。したがって、影響度は、

\[n_i \sum_{k = 1}^{l – i} k 10^{k – 1}\]

となります。\( \sum_{k = 1}^{l – i} k 10^{k – 1} \) は累積和を用いて高速に求めることができます。

\( n_i \) の影響度

上記より、\( n_i \) の影響度は、

\[ \dfrac{10^{i-1}n_ii(i -1)}{2} + n_i \sum_{k = 1}^{l – i} k 10^{k – 1}\]

となるので、全ての文字について全探索します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1000000007;

int main() {
    string N;
    cin >> N;
    int n = N.length();
    ll a[n + 1]{}, b[n + 1]{};
    a[0] = 1;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        a[i + 1] = (a[i] * 10) % mod;
        b[i + 1] = (b[i] + (i + 1) * a[i]) % mod;
    }
    for (ll i = 1; i <= n; i++) {
        ll c = N[i - 1] - '0';
        ll f = (((i - 1) * i) / 2) % mod;
        ans = (ans + c * f * a[n - i] + c * b[n - i]) % mod;
    }
    cout << ans << "\n";
    return 0;
}

感想

最初は非連続な部分列について考えてて誤読しました。