circuit
IOI 2022 Day 2 Tasks
Japanese (JPN)

電⼦回路個のゲートからなる回路があり，各ゲートには 0 から N + M − 1 までの番号がついている．
ゲート からゲート N − 1 までは閾値付きゲートであり，ゲート N からゲート N + M − 1 はソースゲートである．
ゲート 0 以外のそれぞれのゲートは，ちょうど 1 つの閾値付きゲートの⼊⼒となっている．具体的には，1 ≦ i ≦ N + M − 1 を満たすそれぞれの i について，0 ≦ P [i] ≦ N − 1 を満たす P [i] があり，ゲート i がゲート P [i] の⼊⼒となっている．さらに， P [i] は P [i] < i を満たしている．また，
P [0] = −1 とする．それぞれの閾値付きゲートは，少なくとも 1 つのゲートを⼊⼒にもつ．どのソースゲートも⼊⼒をもたない．
各ゲートには 0 と 1 のいずれかで表される状態が定まっている．ソースゲートの初期状態は，M 個の整数からなる数列 A によって表される．0 ≦ j ≦ M − 1 を満たすそれぞれの j について，ソースゲー
ト N + j の初期状態は A[j] である．
それぞれの閾値付きゲートの状態は，そのゲートの⼊⼒の状態に応じて，次のように定まる．まず，それぞれの閾値付きゲートにはパラメータが定まっている．c 個の⼊⼒をもつ閾値付きゲートのパラメー
タは 1 以上 c 以下の整数である．パラメータが p の閾値付きゲートの状態は，状態が 1 のゲートからの⼊⼒を p 個以上もつとき 1 となり，そうでない場合 0 となる．
例えば，N = 3 個の閾値付きゲートがあり，M = 4 個のソースゲートがある場合を考える．ゲート 0はゲート 1 とゲート 6 を，ゲート 1 はゲート 2, 4, 5 を，ゲート 2 はゲート 3 を⼊⼒とする．
この例は，次の図に⽰されている．
N +M0circuit (1 of 4)

ゲート 3, 5 の状態が 1 であり，ゲート 4, 6 の状態が 0 であるとし，ゲート 2, 1, 0 に割り当てられたパラメータが，それぞれ 1, 2, 2 であるとする．この場合，ゲート 2 の状態は 1 に，ゲート 1 の状態は 1 に，ゲート 0 の状態は 0 になる．このように初期状態とパラメータを定めた場合の例は，次の図に⽰されている．状態が 1 のゲートは黒で塗られている．

ソースゲートの状態は Q 回更新される． 各更新は N ≦ L ≦ R ≦ N + M − 1 を満たす 2 つの整数 L,R を⽤いて表され，その更新では L 以上 R 以下の番号のソースゲートの状態が切り替わる．つまり，
L ≦ i ≦ R を満たすそれぞれの i について，ソースゲート i の状態は，元の状態が 0 ならば 1 に，元の状態が 1 ならば 0 に変わる．切り替わったゲートの状態は，その後の更新で再び切り替わるまで，変化することはない．
あなたの⽬標は，ゲート 0 の状態が 1 となるような閾値ゲートのパラメータの定め⽅が何通りあるかを，各更新の後に求めることである．2 つのパラメータの定め⽅は，ある閾値付きゲートのパラメータが異なる場合に，異なるものとする．求める値は⼤きくなりうるので，1 000 002 022 で割ったあまりを求めることとする．
先程の例においては，ゲート 0, 1, 2 への⼊⼒の個数がそれぞれ 2, 3, 1 のため，パラメータの定め⽅は 6通りある．そのうち，2 通りの定め⽅において，ゲート 0 の状態は 1 になる．

実装の詳細

あなたは，次の関数を実装する必要がある．
void init(int N, int M, int[] P, int[] A): 閾値付きゲートの個数: ソースゲートの個数: 閾値付きゲートの⼊⼒を表す⻑さ N + M の配列: ソースゲートの初期状態を表す⻑さ M の配列
この関数は， count_ways のどの呼び出しよりも先に，ちょうど 1 回呼び出される．
NMPAcircuit (2 of 4)

int count_ways(int L, int R), : 状態が変更されるソースゲートの範囲の境界値
この関数は，更新後のソースゲートの状態において，ゲート 0 の状態が 1 になるような閾値ゲー
トのパラメータの定め⽅の個数を 1 000 002 022 で割ったあまりを返さなければならない．
この関数はちょうど Q 回呼び出される．
L R

⼊出⼒例

次のような呼び出しを考える．
init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])

この例は問題⽂に⽰されている例である．
count_ways(3, 4)

この更新では，ゲート 3 とゲート 4 の状態が切り替わる．つまり，ゲート 3 の状態は 0 になり，ゲート4 の状態は 1 になる．ゲート 0 の状態が 1 になるような2 通りのパラメータの定め⽅が，次の図に⽰されている．
Way 1Way 2

その他のパラメータの定め⽅においては，ゲート 0 の状態は 0 になる．そのため，この関数は 2 を返さなければならない．
count_ways(4, 5)

この更新では，ゲート 4 とゲート 5 の状態が切り替わる．結果として，すべてのソースゲートの状態が0 となり，どのようなパラメータの定め⽅においても，ゲート 0 の状態は 0 となる．よって，この関数
circuit (3 of 4)

は 0 を返さなければならない．
count_ways(3, 6)

この更新により，すべてのソースゲートの状態が 1 になる．そのため，どのようなパラメータの定め⽅においても，ゲート 0 の状態は 1 となる．よって，この関数は 6 を返さなければならない．

制約

1 ≦ N , M ≦ 100 000
1 ≦ Q ≦ 100 000
P [0] = −10 ≦ P [i] < i P [i] ≦ N − 1 1 ≦ i ≦ N + M − 1
1i <x ≦N +M −1
P [x] = i0 ≦ A[j] ≦ 1 0 ≦ j ≦ M − 1N ≦L ≦R ≦N +M −1,()
それぞれの閾値付きゲートは少なくとも つ⼊⼒をもつ．(0 ≦ i ≦ N − 1 を満たすそれぞれの iに対して，かつを満たす x が存在する．）()

⼩課題

1. (2 点) N = 1, M ≦ 1000, Q ≦ 5
2. (7 点) N , M ≦ 1000, Q ≦ 5, 各閾値付きゲートはちょうど 2 つの⼊⼒をもつ．
3. (9 点) N , M ≦ 1000, Q ≦ 5
4. (4 点) M = N + 1, M = 2z (z は正の整数）と表せる, P [i] = ⌊ i−12 ⌋ (1 ≦ i ≦ N + M − 1),
L=R

5. (12 点) M = N + 1, M = 2z (zは正の整数）と表せる, P [i] = ⌊ i−12 ⌋ (1 ≦ i ≦ N + M − 1)
6. (27 点) 各閾値付きゲートはちょうど 2 つの⼊⼒をもつ．
7. (28 点) N , M ≦ 5000
8. (11 点) 追加の制約はない．

採点プログラムのサンプル

採点プログラムのサンプルは次の形式で⼊⼒を読み込む．
1 ⾏⽬: N M Q
2 ⾏⽬: P [0] P [1] … P [N + M − 1]
3 ⾏⽬: A[0] A[1] … A[M − 1]
4 + k (0 ≦ k ≦ Q − 1) ⾏⽬: k + 1 回⽬の更新における L R
採点プログラムのサンプルは以下の形式であなたの答えを出⼒する．
1 + k (0 ≦ k ≦ Q − 1) ⾏⽬: k + 1 回⽬の更新に対応する count_ways 関数の呼び出しの戻り値．
circuit (4 of 4)