こんにちは。肉を食べると確実に腹をこわすとーです。
解くに至った問題(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など指定もできる)