萌新刚学数论1ms求调站外数论题目

题目描述：

一个长度为

n

的数字串

s

，有多少种方法可以使得删除若干个数字后剩下的数字串构成的数字能被5整除。可以有前导零，但删完后的数字串不能为空。

输入格式：

第一行输入一个数字串

a

,第二行输入一个整数

k

s=aaaa...a(k个a)

输入样例

CPP

13990
2

输出样例

CPP

我的代码（能过样例）

CPP

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
bool debug = 1;
#define int ll
int quickpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    int k;
    cin >> s >> k;
    int ans = 0;
    int len = s.length();
    for (int i = 0; i < len; i++)
        if (s[i] == '0' || s[i] == '5')
            ans = (ans + (quickpow(2, i) * (quickpow(2, len * k) - 1))  / (quickpow(2, len) - 1)+MOD) % MOD;
    cout << ans;
    return 0;
}

萌新刚学数论1ms求调站外数论题目

讨论操作

回复

相关推荐

萌新刚学数论1ms求调站外数论题目