首页 > 代码库 > Codeforces 464C Substitutes in Number(高效+快速幂)
Codeforces 464C Substitutes in Number(高效+快速幂)
题目链接:Codeforces 464C Substitutes in Number
题目大意:给定一个字符串,以及n中变换操作,将一个数字变成一个字符串,可能为空串,然后最后将字符串当成一
个数,取模1e9+7。
解题思路:将操作倒过来处理,这样维护每个数来的val,len两个,val表示对应数值取模1e9+7,len表示对应有多少
位,再计算的过程中要使用。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
char s[maxn], o[maxn];
int n;
ll v[20], l[20];
ll pow_mod (ll x, int n) {
ll ret = 1;
while (n) {
if(n&1)
ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
struct state {
int r;
vector<int> vec;
void set (char* str) {
int len = strlen(str);
r = str[0] - ‘0‘;
vec.clear();
for (int i = 3; i < len; i++) {
if (str[i] >= ‘0‘ && str[i] <= ‘9‘)
vec.push_back(str[i] - ‘0‘);
}
}
void solve () {
ll val = 0, len = 0;
for (int i = 0; i < vec.size(); i++) {
int u = vec[i];
len += l[u];
val = (val * pow_mod(10, l[u]) + v[u]) % mod;
len %= (mod-1);
}
v[r] = val;
l[r] = len;
}
}com[maxn];
void init () {
for (int i = 0; i < 10; i++) {
v[i] = i;
l[i] = 1;
}
for (int i = 0; i < n; i++) {
scanf("%s", o);
com[i].set(o);
}
for (int i = n - 1; i >= 0; i--) {
int u = com[i].r;
com[i].solve();
}
}
int main () {
scanf("%s%d", s, &n);
init();
int len = strlen(s);
ll ans = 0;
for (int i = 0; i < len; i++) {
int u = s[i] - ‘0‘;
ans = (ans * pow_mod(10, l[u]) + v[u]) % mod;
}
printf("%lld\n", ans);
return 0;
}
Codeforces 464C Substitutes in Number(高效+快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。