转自作者弗莱
详细解析和分享经验
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。
请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。
输入格式
第一行一个正整数 N，含义如题面所述。
第二行一个正整数 Ma，表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
第四行一个正整数 Mb，表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。
输出格式
输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。
样例输入
11
3
10 4 0
3
1 2 0
样例输出
94
提示
当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。
对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B.
//1：如何是使得差值最小呢，我们可以利用dp的思想，要使得整体最小，那么组成他的各个部分也是最小，那么问题就变成了，如何使得各个部分的值最小；
// 2：每个部分有对应位上的差值组成，那么，要使得这个差值乘的进制数尽可能小就可以了；
// 3：如何使得进制尽可能小呢，进制的区间在2~N之间，那么只需要在这个区间之内，选取能包含a[i]和b[i]两个值的最小进制值就ok了，至此，思路就出来了
//如 1 3 2
//第三数位 第二数位 最低数位
#include<stdio.h>
int a[100005]={0};//转码可能数据很大
int b[100005]={0};
int mod=1000000007;
int max(int a,int b)
{
return (a>b?a:b);
}
int main()
{
int Ma,Mb,N,i;//其实N是有用的，只是测试数据没有非法数据，完整的话还要加判断输入是否非法才行的
scanf("%d%d",&N,&Ma);
for(i=Ma;i>=1;i--)
//倒序打印是因为开头输入最高位数，数组下标和位数匹配好理解，至于1也是，舍去了0下标
{
scanf("%d",&a[i]);
//又开始不写&
}
scanf("%d",&Mb);
for(i=Mb;i>=1;i--)
{
scanf("%d",&b[i]);
}
int jz[100005]={0};
for(i=Ma;i>=1;i--)
{
jz[i]=max(max(a[i]+1,b[i]+1),2);//选取最小进制
//选取其中最大的进制是因为A与B同进制，要保证进制合法
//因此两者数据间只有选最大的那个数据才能保证两者相同
//比如 6与8,我们只有选择8的进制我们才能同步两者的进制.
//是在保证进制合法的情况下选择最小的进制
//而题目意思中的十进制输入只是我们认为输入的数据，但是题设中的意思是我们实际上不知道它是什么进制
//而为了所求相减最小，我们就选最小的进制，也就是保证两者相同时选择最小的进制，也就是加1.
//加1是因为如果仅仅赋值输入的数据不可能的，注意有进位这个东西，不加1数据早就进位了
//如我们看到的9这个数字,那么它最小的进制只可能是10，如果是9进制,是会直接进位的，
//这样我们是看不见这个数字9的，看见的是进位后的结果
}
long long sum=0;//数据大用长字符
for(i=Ma;i>=2;i--)
{// A-B=对应数位相减+转换进制
// sum+=((sum+a[i]-b[i])*jz[i-1])%mod;
sum=((sum+a[i]-b[i])*jz[i-1])%mod;
//意思是将最高位的数据一直往低位转换，往上进就除自身的进制，往下进就乘低一位的进制
//这样就体现出每一次选取合法的最小进制的作用了。
//只要每一次的进制都是合法最小的，那乘的数也就是最小的，
//最后结果也一定是最小的。
//i到2截至是因为最低进位时已经将数据转为最小的进制，直接相加即可，单独讨论。
//sum也要放进去参与进位是因为首先是循环，上一次的sum的数据也在这次的循环中，而上一次sum的数据当然也要一同参与进位
//取模是防数据溢出，题设要求
//(+=)不等于(=),如1被赋值为3，和1加上3是不同的！
//其实也可以是直接A的结果转为最低位进制，然后B也转为最低进制
//最后相减即可。注意转换的时候都要取模,防止溢出
//理论上也是可以的.
//这里只不过是用了迭代，一层层相减转进制.
}
sum+=(a[1]-b[1]);//最低位时直接加起来结果.
sum%=mod;//防止溢出
printf("%lld\n",sum);
return 0;
}
