CodeForces - 1422C - Bargain 列舉貢獻

題意：給出長度為n的字串，洗掉其中任意長度的連續子串，將所有可能的情況的數字加起來取模

做法：假設序列是12354，假設2不被刪去
那么可能的情況有以下兩種：

• 洗掉位置[3,5]中的連續子串
  這種情況下，2的貢獻是不同的，分別是：
  洗掉長度為3的子串 2 × 1 0 0 × 1 2×10^0×1 2×100×1
  洗掉長度為2的子串： 2 × 1 0 1 × 2 2×10^1×2 2×101×2
  洗掉長度為1的子串： 2 × 1 0 2 × 3 2×10^2×3 2×102×3
  a n s 1 = ∑ i = 1 n ( ( s [ i ] ? ′ 0 ′ ) × ∑ j = 1 n ? i j 1 0 j ? 1 ) ans1=\sum_{i=1}^{n}((s[i]-'0')×\sum_{j=1}^{n-i}j10^{j-1}) ans1=∑i=1n?((s[i]?′0′)×∑j=1n?i?j10j?1)
• 洗掉位置[1,1]中的連續子串
  這種情況下，2的貢獻是相同的，只需要算有多少種情況即可
  a n s 2 = ∑ i = 1 n ( ( s [ i ] ? ′ 0 ′ ) × 1 0 n ? i × i ( i ? 1 ) / 2 ) ans2=\sum_{i=1}^{n}((s[i]-'0')×10^{n-i}×i(i-1)/2) ans2=∑i=1n?((s[i]?′0′)×10n?i×i(i?1)/2)

輸出ans1+ans2即可

代碼：

const int maxn=2e6+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
const ll mod=1e9+7;
char s[maxn];
ll f[maxn],ans=0,n;
ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if (b&1)res=(res*a)%mod;a=a*a%mod;b>>=1;}return res;}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    rep(i,1,n)f[i]=(f[i-1]+(i*qpow(10,i-1,mod)%mod))%mod;
    for (ll i=n;i>=1;i--)
    {
        ans=(ans+f[n-i]*(s[i]-'0')%mod)%mod;
        ans=(ans+(s[i]-'0')*qpow(10,n-i,mod)%mod*((i*(i-1)/2)%mod)%mod)%mod;
    }
    WW(ans);
    return 0;
}

拓展：一開始讀錯題了，以為是刪去任意長度的子序列（不一定連續），這種情況下，可以直接線性遞推，假設 [ 1 , i ] [1,i] [1,i]的串可以構成的答案是ans，把 s [ i + 1 ] s[i+1] s[i+1]放進來

• 如果取它，那么之前的答案相當于左移一位=10ans，并且計算出有多少個新加進來的 s [ i + 1 ] s[i+1] s[i+1]
• 如果不取它，仍然是ans

由于不能一個都不刪，所以得把它自身減去就是答案了

代碼：

const int maxn=2e6+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
const ll mod=1e9+7;
char s[maxn];
ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if (b&1)res=(res*a)%mod;a=a*a%mod;b>>=1;}return res;}
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    ll x=0,ans=0;
    for(int i=n;i>=1;i--)x=(x+qpow(10,n-i,mod)*(s[i]-'0')%mod)%mod;
    rep(i,1,n)ans=(ans*11%mod+qpow(2,i-1,mod)*(s[i]-'0')%mod)%mod;
    WW((ans-x+mod)%mod);
    return 0;
}