2010-2011 ACM-ICPC Northeastern European Regional Contest Binary Operation

給一個
{0~9}*{0~9} = {0~9} 的表

然後對於兩個正整數，這個二元運算是每位單獨操作
像 ab * cd  =  (a*b)(c*d)

要計算
a*(a+1)*.....(b)

基本上就要算

a*b*b*b.....(n次)

和

(0*0*...(n次)*1*1*....(n次).....)^k

用倍增法蓋表
然後逐位遞推就OK了

測資超兇QQ 總之最後過了.....

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef unsigned long long int int64;
int64 p10[20];
int mm[10][10];
int dmove[10][10][65];
int mmove[10][20][65];
void TLE(){while(1);}
int get_dmove(int a, int p, int64 n){
    int nn = a;
    for(int s = 0;n;s++, n/=2){
        if(n%2)
            nn = dmove[nn][p][s];
        if(s >= 64) TLE();
    }
    return nn;
}
int get_mmove(int a, int c, int64 n){
    int nn = a;
    for(int s = 0;n;s++, n/=2){
        if(n%2)
            nn = mmove[nn][c][s];
        if(s >= 64) TLE();
    }
    return nn;
}
int gain(int64 src, int p){
    return (src/p10[p])%10;
}
int main()
{
    freopen("binary.in", "r", stdin);
    freopen("binary.out", "w", stdout);
    p10[0] = 1; for(int lx = 1;lx <= 19;lx++) p10[lx] = p10[lx-1]*10LL;
    for(int lx = 0;lx < 10;lx++)
        for(int ly = 0;ly < 10;ly++)
            scanf("%d", &mm[lx][ly]);
    for(int lx = 0;lx < 10;lx++)
        for(int ly=  0;ly < 10;ly++)
            dmove[lx][ly][0] = mm[lx][ly];
    for(int ln = 1;ln <= 64;ln++)
        for(int lx = 0;lx < 10;lx++)
            for(int ly = 0;ly < 10;ly++)
                dmove[lx][ly][ln] = dmove[dmove[lx][ly][ln-1]][ly][ln-1];
    for(int lc = 0;lc <= 18;lc++){
        for(int ln = 0;ln <= 64;ln++){
            for(int la = 0;la<10;la++){
                if(ln == 0){
                    int st = la;
                    for(int lx  = 0;lx < 10;lx++)
                        st = get_dmove(st, lx, p10[lc]);
                    mmove[la][lc][0] = st;
                }else{
                    mmove[la][lc][ln] = mmove[mmove[la][lc][ln-1]][lc][ln-1];
                }
            }
        }
    }
    int64 a, b;
    scanf("%I64u %I64u", &a, &b);
    //if(b < 9*p10[17]+5*p10[16] and b > p10[17]) TLE();
    //if(a > b) TLE();
    int64 mao = 0;
    for(int prb = 0;prb <= 18 and p10[prb] <= b;prb++){
        int64 step = b-a;
        int st = gain(a, prb);
        //if(st >= 10) TLE();
        int64 delta1 = p10[prb]-a%p10[prb]-1LL;
        delta1 = min(step, delta1);
        st = get_dmove(st, st, delta1);
        step -= delta1;
        for(int lx = gain(a, prb)+1;lx <= 9;lx++){
            int64 tostep = min(step, p10[prb]);
            st = get_dmove(st, lx, tostep);
            step -= tostep;
        }
        if(step == 0){ mao += st*p10[prb]; continue;}
        int64 down = a/p10[prb]/10LL + 1LL;
        int64 up = b/p10[prb]/10LL;
        if(up < down ) TLE();
        st = get_mmove(st, prb, up-down);
        step -= p10[prb]*(up-down)*10;
        if(step < 0) TLE();
        for(int lx = 0;lx < gain(b, prb);lx++){
            step -= p10[prb];
            st = get_dmove(st, lx, p10[prb]);
            if(step < 0) TLE();
        }
        step -= b%p10[prb]+1;
        st = get_dmove(st, gain(b, prb), b%p10[prb]+1LL);
        if(step) TLE();
        mao += st*p10[prb];
    }
    printf("%I64u\n", mao);
    return 0;
}