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;
}