YukicoderContest289 C問題P2 「Hungry Kanten」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 18
解法・お気持ち
$ Nが小さいため,すべての場合を試します.
ただし,積が大きくなるため多倍長整数を利用する必要があります.
巨大な素数を3つ用意してそれらでそれぞれ演算結果にMODの処理を行い,それらのタプルをカウントすることもできます.(ローリングハッシュのテクニック)
以下は自分が初めて知ったPythonのテクニックについてまとめます.
itertoolsモジュールのproductは直積を作るメソッドです.
product([x, y, z], [a, b, c])とすると(x, a), (x, b) ..., (z, c)のタプルを返すイテレータが渡ります.そのため,そのままforに投げればよいです.
また,product(list, repeat=x)とすると,listをx個つないだ直積を作れます.
そのため,product([0, 1], repeat=10)とすると,10bitのなんちゃってビット全探索ができます.
また,functoolsのreduceは高階関数です.
reduce(演算f, 渡されるリスト)であり,これらの計算結果が返されます.
(単位元が渡されないんですが,どうやっているのでしょうか...? (単位元なしに直接2要素選んで計算している?))
さらにもっと仕様を調べようと思います.
operatorモジュールには便利な演算モジュールが入っています.たとえば,mulです.
計算量
$ O(2^N \times N)
新たな学び
pythonの新たなモジュール
反省点
コード
code: cpp
from itertools import product
from operator import mul
from functools import reduce
N, K = map(int, input().split())
s = set()
for p in product(0, 1, repeat=N): if list(p).count(1) < K:
continue
s.add(sum(Ai for i in range(N) if pi)) s.add(reduce(mul, (Ai for i in range(N) if pi))) print(len(s))
z = lambda x, y: x * y