「'a'を使うとしたら、どの位置の'a'を使うか」は、$S$ における 'a' の個数通りある。これを $P_a$ とする。これを各文字について求める。
どの文字を使うかのパターン数は、使わない場合の1通りを加えて $(P_a+1)\times(P_b+1)\times ... \times(P_z+1)$ となる。
どの文字を使うか決めれば、部分列の並び方は自動的に $S$ における順番になり一意に決まるので、並び順については考えなくてよい。
よってこのパターン数がそのまま答えとなる。ただし、1文字も選ばない1パターンは除いておく。
from collections import Counter n = int(input()) s = input() cnt = Counter(s) ans = 1 MOD = 10 ** 9 + 7 for c, v in cnt.items(): ans = ans * (v + 1) % MOD print((ans - 1) % MOD)
DPで解く。
今考えている石の色を $c_i$ とした時、1つ前に $c_i$ が出てきた場所を $j$ とする。
DPの更新は、$j~i$ について操作を行う場合と行わない場合を合算する。
問題の条件では、操作自体は直前の同色でなくてもっと前の同色の石との間でも行えるが、求めるのは最終的な色の並びなので、「もっと前の同色~$j$」「$j~i$」の2回操作を行ったと考えても変わらない。「もっと前の同色~$j$」の部分は $dp[j]$ までで考慮されているので、新規に考えるのは $j~i$ 間のみでよい。
実装では、あらかじめ同じ色が連続する部分は事前処理で1つにまとめてしまうと $j+1=i$ の場合分けが減って楽。
import sys from collections import defaultdict n = int(input()) stones = [-1] for line in sys.stdin: c = int(line) if stones[-1] == c: continue stones.append(c) dp = 1 prev = defaultdict(lambda: 0) MOD = 10 ** 9 + 7 for s in stones[1:]: dp = (dp + prev[s]) % MOD prev[s] = dp print(dp)
区間を、最初と最後の数字で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。
まず、出来るか出来ないかの問題として、パリティ(2進数で立っている'1'の数の偶奇)を考えると、「…→奇数→偶数→奇数→偶数→…」と交互になっていく。 順列は偶数項なので、$A$ と $B$ のパリティは異なっていないといけない。同じなら'NO'。
逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。
順列なので、途中で同じ数字が被らないように、1ビットずつ変化させていかなくてはいけない。以下の例を考える。
N=3 A=1 B=3 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 1 ? ? ? ? ? ? 3 001 011
$A,B=1,3$を見ると、2ビット目が異なっている。(複数ある場合、異なっているビットをどれか1つ選ぶ)
$0~2^N-1$ の中で2ビット目が'0'と'1'の数字の数は等しい。 よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。
P0 P1 P2 P3 P4 P5 P6 P7 1 ? ? ? | ? ? ? 3 001 ?0? ?0? ?0? | ?1? ?1? ?1? 011
前半の最後の数字($P_3$)を適当に1つ決める。これもまた $A$ から偶数項なので、パリティは異なっている必要がある。
これまでに分割に用いたビット(2ビット目)以外から適当に1つビット位置を選び、$P_3$ を $A$ についてそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、'1'の偶奇が異なっているという条件も満たす。ここでは1ビット目を選んだとする。
1 ? ? 0 | 2 ? ? 3 001 ?0? ?0? 000 | 010 ?1? ?1? 011 ^ 1bit目を変化 ^ ^ P3を決めるとP4も自動的に決まる
すると、左半分を「$A=1,B=0$、ただし2ビット目はいじらない」問題として処理できる。
最初の問題と同様に異なるビットを探すと、1と0では1ビット目が変化しているので(さっきそう変化させたので当然だが)、真ん中で1ビット目を変化させることにする。 前半の前半は「?01」、前半の後半は「?00」という数字を網羅することで、前前半と前後半でかぶりはなくなる。
P0 P1 P2 P3 P4 P5 P6 P7 1 ? | ? 0 | 2 ? ? 3 001 ?01 | ?00 000 | 010 ?1? ?1? 011
前前半の最後の項($P_1$)は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。
1 5 | 4 0 | 2 ? ? 3 001 101 | 100 000 | 010 ?1? ?1? 011
さらに分割を進めて「$A=1,B=5$、ただし1,2ビット目はいじらない」問題となるが、これは既に隣り合っているのでここで終了。右の「$A=4,B=0$」も同様に終了。
右半分も同様に、「$A=2,B=3$、ただし2ビット目はいじらない」として分割していくと、構築できる。
1 5 | 4 0 | 2 6 | 7 3 001 101 | 100 000 | 010 110 | 111 011
左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。 分割済ビット位置をリストで持ち、再帰関数の中で末尾にappendしてから子の探索に進み、終了後にpopするなどで実装できる。
def split(n, a, b, used, ai, ans, width): if width == 2: ans[ai] = a ans[ai + 1] = b return x = a ^ b y = x & -x # Rightmost Bit at which is different for a and b l = y.bit_length() - 1 used.append(l) i = 0 for i in range(n): if i not in used: break la, lb = a, a ^ (1 << i) ra, rb = lb ^ y, b width >>= 1 split(n, la, lb, used, ai, ans, width) split(n, ra, rb, used, ai + width, ans, width) used.pop() def solve(n, a, b): if bin(a).count('1') % 2 == bin(b).count('1') % 2: print('NO') return used = [] ans = [0] * (1 << n) split(n, a, b, used, 0, ans, 1 << n) print('YES') print(*ans) n, a, b = list(map(int, input().split())) solve(n, a, b)
a1 = p : 4 5 1 2 3 ┌ a1における'1'は3番目→a2の3番目は'1'→a3の'1'番目は'1' a2 = q : 3 2 1 5 4 ├ a1における'2'は4番目→a2の4番目は'5'→a3の'2'番目は'5' a3 : 1 5 4 3 2 ┼ a1における'3'は5番目→a2の5番目は'4'→a3の'3'番目は'4' a4 : 4 5 1 2 3 ├ ... a5 : 4 3 2 1 5
写像とか全単射とかその辺を利用する。
まず、$K$ が大きすぎるので、おそらくまとめて計算できるような周期があると予測する。 実際、サンプルでシミュレートしてみると3だったり72だったり、3の倍数で周期が発生している。
また、合成した結果を合成するので、その合成過程は $p$ と $q$ のみで表現できそうだが、試しに $f(p,q)$ を単に $pq$ と表現してみても
a1 = p a2 = q a3 = pq a4 = qpq a5 = pqqpq a6 = qpqpqqpq ...
となり、(だから何?)で終わってしまい、法則の手がかりが見つからなかった。
ここでは、数学の集合論における合成を利用すると法則が見つかりやすかったようだ。
まず、順列 $p$ を、「$i$ から $p_i$ への写像」と捉える。
i 1 2 3 4 5 ↓ ↓ ↓ ↓ ↓ p 4 5 1 2 3
$pq$ を $p$ と $q$ の合成とする。つまり、$i$ 番目が $p_{q_i}$ であるような順列とする。 処理の順番が直感と反していて、$pq$ は $q$ を施した後に $p$ を施すことに注意する。
i 1 2 3 4 5 q 3 2 1 5 4 pq[1] = p[q[1]] = p[3] = 1 p 4 5 1 2 3 pq[2] = p[q[2]] = p[2] = 5 ↓ pq[3] = p[q[3]] = p[1] = 4 ... pq 1 5 4 3 2
また、$p$ に対し、$p^{-1}$ を逆写像とする。つまり、
i 1 2 3 4 5 | p{-1} 1 2 3 4 5 ↓ ↓ ↓ ↓ ↓ | ↑ ↑ ↑ ↑ ↑ p 4 5 1 2 3 | i 4 5 1 2 3 ↓(並べ替え) i 1 2 3 4 5 p{-1} 3 4 5 1 2
となるような順列とする。以下のような性質がある。
$f(p,q)$ を合成の形で表すと、$qp^{-1}$ となる。
ここで、$p^{-1}=P,q^{-1}=Q$ と表現することにし、$a_n$ をこの4つだけで表現すると、
a1 = p a2 = q a3 = qP a4 = qPQ a5 = qPQpQ a6 = qPQpQqpQ = qPQppQ a7 = qPQppQqPqpQ = qPQpqpQ a8 = qPQpqpQqPPqpQ = qPQpqPqpQ a9 = qPQpqPqpQqPQPqpQ = qPQpqPPqpQ ...
と、なんとなく逆写像で打ち消し合って、長さのインフレが抑えられてる感じがする。
またよく見ると、1~2個の中心部を挟んで、前半と後半が綺麗に逆写像の関係であることがわかる。
a1 = (e) p (e) a2 = (e) q (e) a3 = (e) qP (e) a4 = q P Q a5 = qP Q pQ a6 = qP Qp pQ a7 = qPQp p PqpQ a8 = qPQp q PqpQ a9 = qPQp qP PqpQ a10= qPQpq P QPqpQ a11= qPQpqP Q pQPqpQ a12= qPQpqP Qp pQPqpQ a13= qPQpqPQp p PqpQPqpQ
これにより、以下の手順で $a_K$ が求められる。
ここで、$qPQp$ の合成の部分はそのまま計算すると $O(NK)$ かかるので、繰り返し二乗法を使って高速化すると $O(N \log{K})$ で求められる。 他の合成も $O(N)$ とか $O(N \log{N})$ 程度なので、十分高速に求められる。
from operator import itemgetter def get_identity(): return list(range(1, n + 1)) def composition(ppp, qqq): return [ppp[q - 1] for q in qqq] def inverse_composition(ppp, qqq): return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))] def solve(k, ppp, qqq): qp = inverse_composition(qqq, ppp) qpq = inverse_composition(qp, qqq) qpqp = composition(qpq, ppp) l, m = divmod(k - 1, 6) res = get_identity() tmp = qpqp while l: if l % 2 == 1: res = composition(res, tmp) tmp = composition(tmp, tmp) l >>= 1 if m == 0: base = ppp elif m == 1: base = qqq elif m == 2: base = inverse_composition(qqq, ppp) elif m == 3: res = composition(res, qqq) base = inverse_composition(get_identity(), ppp) elif m == 4: res = composition(res, qqq) res = inverse_composition(res, ppp) base = inverse_composition(get_identity(), qqq) elif m == 5: res = composition(res, qqq) res = inverse_composition(res, ppp) base = inverse_composition(get_identity(), qqq) base = composition(base, ppp) else: raise NotImplementedError ans = composition(res, base) ans = inverse_composition(ans, res) return ans n, k = map(int, input().split()) ppp = list(map(int, input().split())) qqq = list(map(int, input().split())) print(*solve(k, ppp, qqq))