首页 > 代码库 > Codeforces 464C Substitutes in Number 同余定理+模拟
Codeforces 464C Substitutes in Number 同余定理+模拟
题目链接:点击打开链接
题意:
给定一串数字
下面有n个操作
每行格式形如 d->t
d为一位数字,t为任意长度的数字。
t的长度和不超过100000
问:最后的结果%1e9+7
思路:
首先我们可以得到一个结论:
同余定理使用后不能再修改数字。
那么为了让同余定理能够使用,我们倒序处理每个数字,这样就能保证能够使用同余定理。
记录每个数字实际代表的数字和实际对应的位数。
然后倒序处理上来即可。
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <set> #include <algorithm> using namespace std; #define N 100005 #define M 100005 typedef long long ll; const ll mod = 1000000007; char s[N], t[N]; struct node{ int d; string s; }a[N]; ll v[10], wei[10], d[M]; ll W(ll x){ if(x==0)return 1LL; ll ans = 0; while(x){x/=10; ans++;} return ans; } int n; void solve(){ scanf("%d",&n); getchar(); for(int i = 1; i <= n; i++) { scanf("%d->", &a[i].d); gets(t); a[i].s = t; } for(int i = 0; i < 10; i++) { v[i] = i , wei[i] = 10LL; } for(int i = n; i >= 1; i--){ ll now = 0; ll len = (ll)a[i].s.length(); if(len == 0) { v[ a[i].d ] = 0; wei[ a[i].d ] = 1; continue;} ll X = 1; for(ll j = 0; j < len; j++) { now *= wei[a[i].s[j]-'0']; now += v[ a[i].s[j]-'0']; X = (X * wei[ a[i].s[j]-'0' ])%mod; now %= mod; } v[ a[i].d ] = now; wei[a[i].d] = X; } ll ans = 0; for(int i = 0; s[i]; i++) { ans *= wei[ s[i]-'0' ]; ans += v[ s[i]-'0' ]; ans %= mod; } cout<<ans<<endl; } int main(){ while(gets(s)) solve(); return 0; } /* 123123 1 2->00 123123 1 3-> 222 2 2->0 0->7 1000000008 0 */
Codeforces 464C Substitutes in Number 同余定理+模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。