CodeForces - 1422C - Bargain 枚举贡献

题意：给出长度为n的字符串，删除其中任意长度的连续子串，将所有可能的情况的数字加起来取模

做法：假设序列是12354，假设2不被删去 那么可能的情况有以下两种：

删除位置[3,5]中的连续子串 这种情况下，2的贡献是不同的，分别是： 删除长度为3的子串$2\times 10^0\times 1$ 删除长度为2的子串：$2\times 10^1\times 2$ 删除长度为1的子串：$2\times 10^2\times 3$ $ans1={\sum }_{i=1}^n((s[i]{-}^{\prime }{0}^{\prime })\times {\sum }_{j=1}^{n-i}j10^{j-1})$删除位置[1,1]中的连续子串 这种情况下，2的贡献是相同的，只需要算有多少种情况即可 $ans2={\sum }_{i=1}^n((s[i]{-}^{\prime }{0}^{\prime })\times 10^{n-i}\times 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]$的串可以构成的答案是ans，把$s[i+1]$放进来

如果取它，那么之前的答案相当于左移一位=10ans，并且计算出有多少个新加进来的$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; }