CF327C Magic Five
搬运工
单调队列优化DP加等比数列求和
首先 \(5\) 的倍数要求末尾是 \(0\) 或 \(5\) 所以我们只用看给定字符串的 \(0\) 和 \(5\) 就好,我们钦定他是最终的数的末尾。
在他之前的选择删掉,在他之后的全部删掉,方案数就是 \(2^{pow-1}\),答案累加就可以了。
容易想到一个朴素的,每次找到后,循环 \(n\) 遍,\(ans=\sum^{len}_{pos}{\sum_{k=0}^{n-1} {2^{pos+k\cdot len-1}}}\),这样复杂度 \(O(nm)\),肯定不行。
不难看出上面的式子是一个等比数列,直接求和就行,最终式子是
k是系数,提前处理出来就好,\(k=\dfrac{2^{len\cdot n}-1}{2^{len}-1}\) 然后就做完了。
#include<bits/stdc++.h>
#define ll long long
const ll mod=1e9+7,N=1e5+5;
char s[N];
ll ans,len,ny,n,xs;
inline ll qpow(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
return ans;
}
int main(){
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0),std::cout.tie(0);
std::cin>>s+1>>n;
len=strlen(s+1);
ll k=qpow(2,len);
ny=qpow(k-1,mod-2);
xs=(qpow(k,n)-1)*ny%mod;
for(int i=1;i<=len;++i)
if(s[i]=='0'||s[i]=='5')
ans=(ans+xs*qpow(2,i-1)%mod)%mod;
std::cout<<ans<<'\n';
}
取模放括号里死活没看出来。