X 进制减法

【问题描述】

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

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.

思路

贪心做法给出证明：
首先观察题目给出条件是A>=B,所以A的位数一定不会比B少，A的位数大于等于B的位数，我们把两个数存到数组中去
，每一位占一个数，我们把最低位当做是第1位，A和B的最大位是n,B没有这一位就相当于是0，最高位是第n位，
即a[1]是A的最高位，以此类推，B也是


首先我们要知道，一个每一位进制可能不同的数如何转化成10进制

示例：A->10进制(ki)表示第i位的进制

A=a[1] + a[2] * (k1) + a[3] * (k1 * k2) + a[4] * (k1 * k2 * k3) + ··· + a[n] * (k1 * k2 *···* kn-1)
所以A-B可以表示成如下图

$sum_{i=1}^{n}(a~i~ - b~i~)(k~1~ * k~2~ * ··· *k~i-1~)$

当i=1的时候是a~i~ - b~i~

题目要求是A-B最小，也就是上面两项乘积的所有和最小(下面我们把ai-bi比作xi)

1.如果所有的项的xi>=0则，很明显，所有的进制k1~kn都取最小即可(满足条件的情况下即ki>ai && ki>bi)


2.如果有某些项的xi<0

在这里我们先证明当xi<0 ，xi+1>0,两个项的和是多少即

 xi  *( k1 * k2 * ··· * ki-1) + xi+1 * (k1 * k2 * ··· * ki-1 * ki)

=(xi + xi+1 * ki)(k1 * k2 * ··· * ki-1)

首先xi<0 , xi+1>0(xi+1>=1更严谨), 且由于ki是i这一位上的进制，所以|xi|<ki,所以

(xi +xi+1 * ki)一定是大于0，并且(k1 * k2 * ···* ki-1)也是大于0，那么这个整体就大于0,
如果想要这个整体越小的话，那么每一个进制都越小越好，这里是证明了，两个相邻的小于0和大于0的两项，
如果是连续的多个小于0的，和大于0的呢

 xi-1 * ( k1 * k2 * ··· * ki-2)+xi * ( k1 * k2 * ··· * ki-1) + xi+1 * (k1 * k2 * ··· * ki-1 * ki)

=(xi+1 * ki * ki-1 + xi * ki-1 + xi-1)(k1*k2*···*ki-2)

首先是xi-1<0 , xi<0 , xi+1>0 由于|xi-1|<ki-1所以 xi*ki-1 + xi-1,最多变成
(xi - 1)*ki-1,(这里是理想状态下，因为ki-1>|xi-1|,我们证明这种理想状态下，满足条件的话，
也能证明我们的结论)
即(xi+1 * ki * ki-1 + (xi - 1) * ki-1),那么由于ki>=|xi - 1|
所以(xi+1 * ki * ki-1 + (xi - 1) * ki-1)还是要大于等于0，那么想要越小越好的话，还是每一个k越小越好，
这是理想状态下，那么现实状态下是必然是大于0的,所以结论也是每一个k越小越好。

总上所述，无论是几个小于0的项相连，只要后面有一项是大于0的项那么就要前面所有位进制都是取越小越好
，由于A>=B的，所以最高位是大于等于0，把等于0的项忽略掉，那么剩余项中最高的项的系数必然是大于0，
那么就取每一位越小越好

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N=1010,M=100010,MOD=1e9+7;
typedef long long LL;
int n;
int ma,mb;
int a[M],b[M];
LL res;

int main(){
    cin>>n;
    cin>>ma;
    for(int i=1;i<=ma;i++) cin>>a[i];
    cin>>mb;
    for(int i=1;i<=mb;i++) cin>>b[i];
    reverse(a+1,a+1+ma);
    reverse(b+1,b+1+mb);
    LL K=1;
    for(int i=1;i<=ma;i++){
        int k = max(max(a[i],b[i])+1,2);
        res=(res+(a[i]-b[i])*K)%MOD;
        K=(K*k)%MOD;
    }
    cout<<res<<endl;
    return 0;
}