- 题目
一个长度为 n 的数字串 s ，有多少种方法可以使得删除若干个数字后剩下的数字串构成的数字能被 5 整除。可以有前导零，但删完后的数字串不能为空。
s =aaaa...a(k个a) - 思路分析
~~~~ 题目的意思就是一个数在删除若干数字后仍能被 5 整除的方案数
~~~~ 我们拿第 2 个样例举 a=13990,n=2 , 所组成的数是 1399013990 我们知道能被 5 整除的数末尾一定是 0 ~5 ，我们发现这个例子在数字串的第 5 位和第 10 位是 0 ，根据定义，他们之前的数字都可以操作，而他们之后的数字都必须删掉，所以方案数即 2^9+2^4 满足样例输出。
~~~~ 我们不妨将 n 给扩大这个数就变为了
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 139901399013990...
~~~~ 我们可以得出它的方案数是：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2^4+2^9+2^{14}+2^{19}...
~~~~ 再将 2^4 提出来这个式子就会变为
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2^4(1+2^5+2^{10}...)=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2^4(1+2^5+(2^5)^2+(2^5)^3...)=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2^4\sum\limits_{i=0}^{k-1}(2^5)^i=
~~~~ 可以发现 4 是数字 0 在 a 中前面数字的个数 5 又是这个数字串的长度所以我们把这个式子扩展到任意的 a,k 应该为
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \sum\limits_{i=0}^{n-1}\Big( 2^{i}\sum\limits_{j=0}^{k-1}(2^{n})^j\Big)(a[i]~mod~5==0)
~~~~(其中 n 为数字串 a 的长度）
~~~~ 我们发现 \sum\limits_{j=0}^{k-1}(2^{n})^ j 是一个常量，所以只要预处理这个式子问题就迎刃而解，但暴力处理复杂度会达到 O(klogk) ，显然不太现实，所以要用到一个数学方法来化简:错位相减法
~~~~ 我们令 S=\sum\limits_{j=0}^{k-1}(2^{n})^j 将 \sum 展开得 S=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1+2^n+(2^n)^2+...+(2^n)^{k-1}
~~~~ 我们给左右两边同时乘以 2^n 得 2^nS=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2^n+(2^n)^2+(2^n)^3+...+(2^n)^{k}
~~~~ 两式相减得：
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (2^n-1)S=(2^{nk}-1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ S= \frac{2^{nk}-1}{2^n-1}
~~~~ 当然如果你会 等比数列的求和公式 也可以直接推出（雾,总时间复杂度为 O(logk)
~~ 献上代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e9+7;
inline int bp(int a,int b) {
if (b==0) return 1;
int res = bp(a,b/2);
if (b%2)
return(res*res)%M*a%M;
else
return (res*res)%M;
}
string a;
int k,inv,ans;
signed main(){
cin>>a>>k;
int n=a.size();
inv=bp(bp(2,n)-1,M-2);//求逆元
int s=((bp(2,n*k)-1)*inv)%M;
for(int i=0;i<n;i++){
if(a[i]=='0'|a[i]=='5') ans=(ans+(bp(2,i)*s)%M)%M;
}
cout<<ans;
return 0;
}