自动搬运

查看原文

来自洛谷，原作者为

	Rain_chr think twice,code once

搬运于2025-08-24 22:42:26，当前版本为作者最后更新于2023-01-02 18:07:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

UPDATE

2023.2.21 添加了第一位读者 @Palpitate23 的问题并解答

2023.3.13 添加了第二位读者 @abc1352758620 的问题并解答

2023.4.4 修了公式中不完善的地方。

question & answer

Q : 为什么计算 $ka$ 和 $kb$ 时也要对 $10^7$ 取模啊 ，题目的意思不是最后相减完再取模就可以了吗？

A : 是这样的，因为两个数 $A$ 和 $B$ 是 $10^5$ 级别的，如果先算出值再减法，没有任何一种变量存的下。而且越到后面这一位的权值越大，呈指数级别上涨，除非使用高精度，否则没有办法计算。而且取模运算有一个特性，加法和乘法可以任意取模，所以我就每计算一遍都取模。

问题来自：@Palpitate23

Q ：如果某一位的数字，出现 $a_i<b_i$ ，那么 $a_i-b_i$ 就变成负数了，是否需要借位？如果为负数，能否得出答案？

A ：思考的很全面，因为题面中提到了 $A−B$ 的结果的最小可能值转换为十进制后再模 $10^7$ 的结果，所以答案一定是一个取模意义下的数值。

借位其实就是直接取模后减法，即使答案是一个负数，但是在取模意义下的结果，所以我们直接进行取模意义下的减法即可。

另外，其实题目中保证了 $A-B$ 非负。

问题来自：@abc1352758620

在此由衷感谢！

题意简述

这题其实非常好理解，只是有一点点要注意。

平常的 $n$ 进制中，第 $i$ 位代表的值是 $a_i \times n^i$ ， 其中 $i$ 从0开始计数，从右往左数。

但在此题中，由于进制不同，无法以上方式子得到权值，第i位的权值是 $a_i \times \prod_{j=0}^i n_i$ ，其中 $n_i$ 是第i位的权值，这点值得谨记。

题目分析

对于每一位， $a_i$ 和 $b_i$ ,显然这一位的进制 $x$ 必须满足 $x>\max(a_i,b_i)$ ,不然的话没法儿表示。又因为要使得差尽可能小，所以每一位进制就是 $\max(a_i,b_i)+1$ ，这里是贪心思想。

最后直接上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
int b[100010];
int c[100010]; 
int d[100010];
const int mod=1e9+7;
signed main()
{
	int n; //输入部分 
	cin>>n;
	int ma;
	cin>>ma;
	for(int i=ma;i;i--)
		cin>>a[i];
	int mb;
	cin>>mb;
	for(int i=mb;i;i--)
		cin>>b[i];
		
	for(int i=max(ma,mb);i;i--) //处理进制 
		c[i]=max(a[i],b[i])+1;
	for(int i=max(ma,mb);i;i--) //最低进制是二进制 
		c[i]=c[i]>2?c[i]:2;
		
	d[1]=1; //处理每一位的价值 
	for(int i=2;i<=max(ma,mb);i++)
		d[i]=(d[i-1]*c[i-1])%mod;
		
	long long ka=0,kb=0; //统计价值 
	for(int i=ma;i;i--)
		ka+=a[i]*d[i],ka%=mod;
	for(int i=mb;i;i--)
		kb+=b[i]*d[i],kb%=mod;
	
	cout<<(ka-kb+mod)%mod; //特别注意：模意义下的减法 
	return 0;
}

思考提升

如果题目要求每一位的进制互不相同呢？

提示：考虑求每一位权值的式子。

结论：还是贪心，让低位的进制尽可能的小，以此保证后面的权值尽可能的小。