转自作者弗莱

详细解析和分享经验

进制规定了数字在数位上逢几进一。

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 32//第三数位第二数位最低数位#includeint 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;}