CH Round #60 乘法表

2015.01.01 19:04 Thu| 7 visits oi_2015| 2015_刷题日常| Text

Solution

首先,新年快乐~~

开始的时候信誓旦旦地说这个题连快速幂都不用的我最终还是乖乖地写了一个逆元……

题意貌似看起来很乱……另外既然没有部分分,这个 1 和 2 的数据限制貌似可以怀疑是唯恐天下不乱……还有这个三进制……邢建开说话难道不能说完整?只说了爆long long为什么不说不爆unsigned long long……

好吧,可以说还是我太弱了……这道题可以轻易地找出规律吧。$(i,j)$ 的取值为 $(j\mod 9)\times i^{\lfloor {j\over 9}\rfloor}$ 。由于我被坑了,所以写的还是Python……不得不说我的Python水平有长进。也是终于能找到能提交Python3的OJ了。开心 >_<

Code

global inv, p
inv = [0] * 15
p = 10007

def power(a,b,p):
    re = 1
    while(b > 0):
        if(b & 1):
            re = re*a%p
        a = a*a%p
        b = b>>1
    return re

def work(a,b):
    t = b // 9
    if(a > 1):
        re = (power(a, t, p) -1) * inv[a-1] * 45 % p
    else:
        re = t * 45 % p
    re2 = (b%9 +1) * (b%9) / 2 * power(a, t, p) % p
    return (re + re2) % p

def r(x):
    temp = 1
    re = 0
    while( x > 0 ):
        re += x%10 * temp
        x //= 10
        temp *= 3
    return re


n = int(input(""))
if(n == 1):
    a,b = input("").split()
    a = int(a); b = int(b); c = a; d = b
else:
    a,b,c,d = input("").split()
    a = int(a); b = int(b); c = int(c); d = int(d)

a = r(a); b = r(b); c = r(c); d = r(d)

inv[1]=1;
for i in range(2, 11):
    inv[i]=(p-p//i) * inv[p%i] % p

ans = 0
for i in range (a, c+1):
    ans += work(i, d) - work(i, b-1) + p
    ans %= p

print(int(ans))