作者：妖童J | 来源：互联网 | 2023-10-11 18:36
https:codeforces.comproblemsetproblem327C因为答案可以有前导零，所以0和5一视同仁。每个小节内，以排在第$i$个的5为结尾的序列即为在前面
https://codeforces.com/problemset/problem/327/C
因为答案可以有前导零，所以0和5一视同仁。每个小节内，以排在第 $i$ 个的5为结尾的序列即为在前面 $0\thicksim i-1$ 共i个里面选 $0$ 、 $1$ 、 $2$ 直到 $i-1$ 个去除，由二项式定理知道这里是 $2^i$ 。
因为小节可以循环，每次循环后面的对应位置要多 $n$ 个元素可以去除，那么就多乘一个 $2^n$ ，而一共有 $k$ 节，由等比数列求和 $\frac{a_1(1-q^n)}{1-q}$ 得知其实就是 $\frac{2^{nk}-1}{2^n-1}$ 。
那么2的任意次方可以由快速幂求出来。除法可以用费马小定理求出来乘法逆元（这里的模数是质数，而不仅仅是与2的幂次互质）。（逆元为所求数的p-2次方）。
#include
using namespace std;
#define ll long long
ll p=1000000007;
ll qpow(ll x,ll n){
ll res=1;
while(n){
if(n&1)
res=res*x%p;
x=x*x%p;
n>>=1;
}
return res;
}
char a[100005];
ll k;
int main(){
scanf("%s",a);
scanf("%lld",&k);
ll n=strlen(a);
ll cur=0;
for(int i=0;i){
if(a[i]=='5'||a[i]=='0'){
cur+=qpow(2,i);
cur%=p;
}
}
ll ans=cur*(qpow(2,n*k)-1)%p*(qpow(qpow(2,n)-1,p-2))%p;
printf("%lld\n",ans);
}
京公网安备 11010802041100号