CodeForces – 1422C – Bargain 枚举贡献


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

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

CodeForces - 1422C - Bargain 枚举贡献

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » CodeForces – 1422C – Bargain 枚举贡献
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏