Magic Five
题目链接
分类：combinatorics math
1.题目描述
给出一个字符串a和一个整数k，表示这个字符串s是由k个a连接得到的，要求任意删除字符串s中的任意位上的字符，使得删除后的字符串表示的数能被5整除。
题目说明所求结果可能包含前导0的情况，即5和05算两种情况。
2.解题思路
对于一个串，我们很容易知道对于某一位i是0或5，有
2i
种选法（字符串从第0位开始，第i位确定）一个串的选法也很容易求出，按顺序求出每一位的选法，加起来（设一个串有
k
种选法，那么对于多个串，第二个串的某一位i（对于该串的第i位），有
2lens i种选法，即
2i×2lens
种选法。这样的话，选法之和可以提取为
k⋅2lens
种选法，这样的话，m个串的选法之和可以整理为等比数列之和，等比数列公式为
ai=(i−1)⋅k⋅2lens
按照等比数列求和公式我们得到m个串的和
Tm=1−2m⋅lens1−2lens%mod
，接下来就是逆元，根据费马小定理
ab≡1(%p)⇒ap−1≡1(%p)
其中逆元就是
ap−2
。
3.AC代码
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define e exp(1.0)
#define pi acos(-1.0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
#define INF 0x3f3f3f3f
#define maxn 100010
#define N 1111
typedef vector<int> VI;
typedef pair<
int,
int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int mod =
1e9 +
7;
char a[maxn];
ll quickpow(ll a, ll b) {
ll ans =
1;
while(b) {
if(b &
1) ans = ans * a % mod;
a = a * a % mod;
b >>=
1;
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
freopen(
"out.txt",
"w", stdout);
long _begin_time = clock();
#endif
ll k, cnt =
0;
scanf(
"%s%I64d", a, &k);
int len =
strlen(a);
rep(i,
0, len)
if(a[i] ==
'0' || a[i] ==
'5')
cnt = (cnt + quickpow(
2, i)) % mod;
ll x = quickpow(
2, len);
ll y = quickpow(x, k);
x = ((
1 - x) % mod + mod) % mod;
y = ((
1 - y) % mod + mod) % mod;
printf(
"%lld\n", cnt * (y * quickpow(x, mod -
2) % mod) % mod);
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf(
"time = %ld ms.", _end_time - _begin_time);
#endif
return 0;
}
