tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/15 AtCoder(巨大な数をある数で割ったときの余りを求める、順列)

こんにちは。肉を食べると確実に腹をこわすとーです。

AtCoder

解くに至った問題(7問)

ABC:012D/021D/030D/046D/047D/052D/073D

ABC030D

例えば、1234567890という数字の列が10**5回続くような巨大な数字(つまり10**6桁)を10**9+7で割ったあまりを突然求めたくなったらどうすればよいだろうか

素直にmodをとると馬鹿みたいに時間がかかるので、工夫をする必要がある

簡単な例として、1234を4で割ったあまりを考えてみる

桁が大きい方の数字から見ていけば、
1を4で割ったあまりは1

1*10+2=12を4で割ったあまりは、(1を4で割ったあまり*10)を4で割ったあまりと、2を4で割ったあまりの和(つまり、1*10+2=12≡0)

12*10+3=123を4で割ったあまりは、(12を4で割ったあまり*10)を4で割ったあまりと、3を4で割ったあまりの和(つまり、0*10+3=3≡3)

123*10+4=1234を4で割ったあまりは、(123を4で割ったあまり*10)を4で割ったあまりと、4を4で割ったあまりの和(つまり、3*10+0=30≡2)

となって、2と求まる
つまり、上から一桁ずつ見ていけば、桁数分のループを行うことで余りが正しく求まるということが分かる

これをコードにする(kは与えられた巨大な数を「文字列」として受けとる。こうして上から一桁ずつ見ていける)

k = input()
mod = 10**9+7
ans = 0
for n in map(int,k):
  ans = (10*ans+n)%mod
print(ans)


ABC073D

順列の求め方

例えばL=[1,2,3]の順列を求めたいと思ったら、

import itertools
K = list(itertools.permutations(L))

とすれば、

K = [(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)]

となる(K[1][2] == 2など指定もできる)