CF327C Magic Five 题解

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

取模放括号里死活没看出来。