事前計算で1以上 $N$ 以下の数字を走査し、「先頭桁が $i$ で末尾桁が $j$ の数字の個数 $C_{i,j}$」をあらかじめ求めておく。
再度、1以上 $N$ 以下の数字を走査し、その数字が先頭桁が $j$ で末尾桁が $i$ なら答えに $C_{i,j}$ を加算すればよい。
(最初、まとめて計算しなければいけないと思って時間をかけすぎた。桁DPなら制約がもっとえげつないことに気付こう)
def solve(n): tbl = [0] * 100 for i in range(1, n + 1): st = str(i) tbl[int(st[0] + st[-1])] += 1 ans = 0 for i in range(1, n + 1): st = str(i) ans += tbl[int(st[-1] + st[0])] return ans n = int(input()) print(solve(n))
要は、$A_1,...,A_N$ の最小公倍数(LCM)を求めて、各 $B_i$ はそれを $A_i$ で割った値にした場合が最小である。
ただし、ある程度巨大なLCMをきちんと求められますか、という問題。
$A_1,A_2$ のLCMは、通常なら2数の最大公約数をもとめて、$A_1A_2$ をそれで割った値となる。 複数の値があっても、$lcm(A_1,A_2,A_3)=lcm(lcm(A_1,A_2),A_3)$ と順番に更新していけばよい。
しかし今回はそれでは、$A_i$ が互いに素だった場合、$10^{60000}$ くらいの値になりかねない。 また、割り算を伴うので、途中でMODをとってしまうと正しく求められない。
素因数分解の形で管理するとよい。
$A_1 = 2^a3^b5^c, A_2 = 2^d3^e5^f$ と素因数分解できるとすると、その最小公倍数は $2^{\max(a,d)}3^{\max(b,e)}5^{\max(c,f)}$ となる。
$A_i$ を全て素因数分解して各素因数の最大値を取っていくと、各要素がそこまで大きくならない範囲でLCMを保持できる。
最後に各素因数を順番にかけてやればいいが、ここではMODをとりながら行うことができる。
そして、各 $A_i$ につきLCMに逆数をかけた値を足し合わせれば答えとなる。
Pythonなら $pow(x,y,m)$ で比較的高速に簡単にmodの累乗を計算できるので、逐一フェルマーの小定理から $A_i^{-1} \equiv A_i^{MOD-2} \mod{MOD}$ を計算しても間に合う。
def prime_factorize(n): i = 2 res = {} while i * i <= n: if n % i != 0: i += 1 continue res[i] = 0 while n % i == 0: res[i] += 1 n //= i i += 1 if n != 1: res[n] = 1 return res n = int(input()) aaa = list(map(int, input().split())) MOD = 10 ** 9 + 7 lcm_ppf = prime_factorize(aaa[0]) for a in aaa[1:]: for p, c in prime_factorize(a).items(): if p in lcm_ppf: lcm_ppf[p] = max(lcm_ppf[p], c) else: lcm_ppf[p] = c lcm = 1 for p, c in lcm_ppf.items(): lcm = lcm * pow(p, c, MOD) % MOD # print(lcm) ans = 0 for a in aaa: ra = pow(a, MOD - 2, MOD) ans = (ans + lcm * ra) % MOD print(ans)
$10^{60000}$ ならそのまま計算できる。そう、Pythonならね。(AC 1895ms)(やればよかった)
ただし、加減乗除の内、除だけはかなり遅いので注意。
from fractions import gcd n = int(input()) aaa = list(map(int, input().split())) lcm = aaa[0] for a in aaa[1:]: lcm = lcm * a // gcd(lcm, a) print(sum(lcm // a for a in aaa) % (10 ** 9 + 7))
「少なくとも1つは黒である」という条件は扱いづらいので、「全て黒でない」に言い換えて、それを全体から引くのがセオリー。
今回のように条件が複数ある場合、全体から「どれか1つでも満たさない場合の数」を引く必要があるが、それは包除原理を用いれば計算できる。
辺数は最大49と小さいので、辺集合を1辺を1bitとしたビットフラグで表せる。 $u_i$ から $v_i$ まで、使った辺のbitを立てながらDFSなどで探索し、経路に使う辺集合を計算しておく。
入力例3 1 2 3 辺の横の数字は辺番号 ① --- ② --- ③ --- ④ `--- ⑤ 4 条件 経路 辺集合 bit表現 1 1~3 {1,2} 0011 2 2~4 {2,3} 0110 3 2~5 {2,4} 1010
または、適当な頂点 $r$ を根として、$r$ から全頂点への使う辺集合 $G_{r,v}$ をビットフラグで求めておけば、 $u,v$ 上の経路は $G_{r,u} \ XOR \ G_{r,v}$ で計算できるので計算量を減らせる。(今回は制約が小さいので恩恵は少ないが)
包除原理を用いるにあたり、全条件の内、一部だけを確実に満たさないパターン数(あとは満たしても満たさなくてもよい)を考える。 どの条件を満たさないかは、$2^M$ 通りある。これを全探索する。
$M$ 個中 $C_1,C_2,...,C_k$ の条件を満たさない場合、このいずれかの条件に対応する経路に含まれる辺は黒に塗られてはいけない。 各条件で使う辺集合のbitORを取って、'1'が立っているのがそれに該当する辺である。
他の辺はどうあってもよいので、$k$ 個の条件を全て満たさないパターン数は、$2^{N-1-bitORで1が立っている辺数}$ となる。
条件集合 条件集合 k 辺集合 not黒な 満たさない bit表現 bitOR 辺の数 場合の数 000 {} 0 0000 0 2^4 001 {1} 1 0011 2 2^2 010 {2} 1 0110 2 2^2 011 {1,2} 2 0111 3 2^1 100 {3} 1 1010 2 2^2 101 {1,3} 2 1011 3 2^1 110 {1,2} 2 1110 3 2^1 111 {1,2,3} 3 1111 4 2^0
ここから以下のように包除原理を適用すると「満たさない条件が1つでもある場合の数」を計算できる。
$(k=1の時の場合の数の和) - (k=2の時の場合の数の和) + (k=3の時の場合の数の和)$ $= (kが奇数の時の場合の数の和) - (kが偶数の時の場合の数の和)$
これを全事象の数から引けばよいが、全事象はつまり $k=0$ の時の場合の数なので、結局
$(kが偶数の時の場合の数の和) - (kが奇数の時の場合の数の和)$
を計算すれば、答えとなる。
辺集合の計算に $O(NM)$。
条件集合のイテレートに $O(2^M)$、各条件集合でbitORを求めるのに $O(M)$、立っているbitを数えるのに $O(N)$ より、$O((M+N)2^M)$。あわせて $O(NM+(N+M)2^M)$ となる。
最大値を代入して $7 \times 10^7$ くらい。これに定数倍がかかるのでそれなりに重くはあるが、4秒なら通る。
def dfs(s, t, links): visited = set() q = [(s, 0)] while q: v, used = q.pop() if v == t: return used visited.add(v) for lb, u in links[v]: if u in visited: continue q.append((u, used | lb)) n = int(input()) links = [set() for _ in range(n)] for i in range(n - 1): a, b = map(int, input().split()) a -= 1 b -= 1 lb = 1 << i links[a].add((lb, b)) links[b].add((lb, a)) conditions = [] m = int(input()) for i in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 conditions.append(dfs(u, v, links)) ans = 0 for i in range(1 << m): cnd_cnt = bin(i).count('1') bit = 0 k = i while k: b = k & -k j = b.bit_length() - 1 bit |= conditions[j] k ^= b free_link_cnt = n - 1 - bin(bit).count('1') val = 2 ** free_link_cnt if cnd_cnt % 2: ans -= val else: ans += val print(ans)
包除原理を用いなくても、DPでも計算できる。
あらかじめ各辺につき、「この辺が黒く塗られたら、条件 $C_1,C_2,...$ を満たすことが出来る」という情報 $F_i$ を、1条件を1bitとしたビットフラグで計算しておく。
として、以下のように遷移していく。
最終的に $DP[N-1][111...11]$ が答え。$O(NM+N2^M)$