AtCoder Regular Contest 191 (Div. 2) A,B,C,D,E問題メモ

AtCoder Regular Contest 191 (Div. 2)

A,B問題の2完だけだと最速で解いてもPerf.ギリ2000程度で、遅解きの場合はPerf.1200ちょいまで下がる。つまり水～青帯の人もこの辺は解いているということで、実力の高まりを感じる。
C～Dを解ききらないとどうにもならんね。

Div.2なら、時間があれば全く解けないという感じではないので、考察と実装の効率化が肝か。

A - Replace Digits

問題文

長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ が与えられます。ここで、 $S,T$ はどちらも 1 から 9 までの数字からなります。
あなたは以下の操作を $k=1,2,\ldots,M$ の順に行います。
- $1\le i\le N$ を満たす整数 $i$ を選ぶ。そして、 $S$ の $i$ 文字目を $T$ の $k$ 文字目で置き換える。

$M$ 回の操作が終わった後の文字列 $S$ を整数としてみた値の最大値を求めてください。

制約

$1\le N,M\le 10^6$
$N,M$ は整数
$S$ は 1 から 9 までの数字からなる長さ $N$ の文字列
$T$ は 1 から 9 までの数字からなる長さ $M$ の文字列

解法

しっかり考えないと見落としパターンが発生する、やな問題。

まず、 $T$ にある大きい数から順に、 $S$ の先頭から、置き換えた方が答えが大きくなる場合、その位置を「予約」していく。

i  1 2 3 4 5 6
S  3 1 7 1 5 9
T  2 6 5 8 5 2

Tで大きい順に、
8 は、S[1]=3 より大きいので、i=1を予約する
6 は、S[2]=1 より大きいので、i=2を予約する
5 は、S[3]=7 より大きくない
      S[4]=1 より大きいので、i=4を予約する
5 は、S[5]=5 より大きくない
      S[6]=9 より大きくない    i が S の末尾に達したので終了

よって、この例では $T$ の大きい方から3個を使って、以下の $S'$ のように置き換えられる（途中段階）。

S'  8 6 7 5 5 9
    ~ ~   ~

ただし、 $T$ の要素は「必ず」置き換えなければならないので、末尾の $T_M=2$ もどこかを置き換えないといけない。
（末尾以外の要素は、もし不要であっても、たとえば $T_M$ を置き換える予定の位置を置き換えておけば、最後に上書きされるので気にしなくてよい）

上例の場合は、末尾を置き換えるのが最適となり、これが最終的な答えとなる。

S''  8 6 7 5 5 2
               ~

$T_M$ 自体がどこかを予約した数であればいいが、そうでない場合、どこを置き換えるのが最適か？

$S'$ の最小値を $m$ としたとき、

$m \lt T_M$ なら、 $T_M$ はアルゴリズム上、どこかを予約しているはずである。 $S'$ から変える必要は無い。
$m = T_M$ なら、 $T_M$ はどこかを予約しているか、または最初から $S$ にあった要素となる。そこを置き換えれば $S'$ から変える必要は無い。
$m \gt T_M$ なら、 $S'$ から減少するがどこかを上書きしないといけない。末尾を置き換えるのが最も被害が少ない。

これで答えとなる。下線部分を見落としやすい。

Python3

B - XOR = MOD

問題文

正整数 $N,K$ が与えられます。
以下の条件を満たす正整数 $X$ を $N$ と相性の良い数と呼びます。
- $X$ と $N$ の排他的論理和は、 $X$ を $N$ で割ったあまりと等しい。
$N$ と相性の良い数が $K$ 個以上存在するか判定し、存在する場合は $N$ と相性の良い数のうち $K$ 番目に小さい値を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$1\le N,K\le 10^9$
入力される値は全て整数

解法

考察の取っかかりやすさはAより簡単?

相性の良い数 $X$ の性質を考えていくと、

必ず $X \ge N$ である。
- $X \lt N$ の時、 $X \mod N = X$ である一方、1以上の $N$ に対して $X \oplus N$ は $X$ のままになり得ない。
2進数の桁数が同じである。
- 2進数の桁数が $d(X) \gt d(N)$ の場合、 $X$ の最上位bit はそのまま残り、 $X \oplus N \gt N$ である。
- しかし、剰余の性質上、 $X \mod N \lt N$ であり、矛盾する。

ここから、 $N \le X \lt 2N$ となるので、 $X \mod N = X - N$ と同じと考えて良いと分かる。

すると、相性の良い数とは、「 $N$ を2進数で表したときに“0”である部分のいくつかを“1”に置き換えた数」と同じと言える。

N  1001101001111111000001110
    ~~  ~ ~~       ~~~~~   ~
X候補
   1011101001111111110111110
   1001101011111111110101111  など

この中の $K$ 番目の要素を求めたい。

相性の良い数は、 $N$ の2進数表記の“0”の個数を $k$ とし、 $2^k$ 個だけ存在する。 $2^k \lt K$ なら存在しない。

存在する場合、 $K-1$ を2進数で表記し、それぞれを $N$ の“0”である部分に下から対応させていった数が答えとなる。

N   1001101001111111000001110    (10進数表記: 20250126)
           ||       ||||`--,|
           ||       |||`--,||
           ||       ||`--,|||
           ||       |`--,||||
           ||       `--,|||||
           |`---------,||||||
           `---------,|||||||
K-1                  10111110   （10進数表記:      190）
             ↓
X   1001101101111111111111110

Python3

C - A^n - 1

問題文

$1$ 以上 $10^9$ 以下の正整数 $N$ が与えられます。
以下の条件を共に満たす正整数の組 $(A,M)$ を一つ求めてください。ただし、制約下でそのような正整数の組が必ず存在することが証明できます。
- $A,M$ はどちらも $1$ 以上 $10^{18}$ 以下の正整数である。
- $A^n-1$ が $M$ の倍数となるような正整数 $n$ が存在し、その最小値は $N$ である。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^4$
$1\le N\le 10^9$
入力される値は全て整数

解法

Editorialの解法②に相当する方法で解こうとして、デバッグ中に時間切れ。
解法①は天啓がないと思いつけないね。

まず、 $N=1$ の時は “1 1” などいくらでも答えがあるので、以降 $N \ge 2$ とする。

問題文の条件は原始根、位数の発想と似ている。

原始根の定義と具体例（高校生向け） | 高校数学の美しい物語
類題: ABC335 G問題

「法 $P$ における $a$ の位数」とは、以下を満たす $i$ のことを指す。

$P$ を3以上の素数とし、 $a$ を $1 \le a \lt P$ を満たす数とする
$a$ の指数を $1,2,...$ と増やしていったとき、最初に $a^i \equiv 1 \mod{P}$ となる $i$ を $a$ の位数という。

$M$ を素数としてまず決め、次に法 $M$ における位数が $N$ である $A$ を見つければよい。

$M$ の求め方

法 $P$ における位数は、どのような $a$ でも必ず $P-1$ の約数となる性質がある。
よって、まずは $kN+1$ が素数となるような $k$ を探す。

基本的にしらみつぶししかない（と思う）が、当てはまる数はたくさんあるので、乱択や、小さい方から探していけばすぐに見つかる。
素数判定は、 $10^{18}$ 以下なら高速な「ミラーラビン判定法」を決定的アルゴリズムとして使える。

見つかったら、 $M=kN+1$ とする。

どのような素数 $P$ に対しても以下の事実が証明されているので、 $M$ は1つ見つかればよい。

全ての $P-1$ の約数 $d$ について、法 $P$ における位数が $d$ である数が存在する。

$A$ の求め方

こちらも $M$ と同様、解析的に解く方法はないので、乱択または小さい方から探していく。

「法 $M$ における $a$ の位数が $N$ 」とは、以下に言い換えられる。

$a^{N} \equiv 1 \mod{M}$
$N$ 以外の全ての $N$ の約数 $d$ について、 $a^{d} \not\equiv 1 \mod{M}$

ただし約数は全てを確かめる必要は無い。
$a^{d} \equiv 1$ なら、 $d$ の倍数については全て $i=2,3,...$ として $a^{id} \equiv 1$ なので、結局、 $N$ の素因数を（指数は無視して） $p_1,p_2,...,p_m$ として、

$a^{N} \equiv 1 \mod{M}$
全ての $N$ の素因数に対して、 $a^{N/p_i} \not\equiv 1 \mod{M}$

を確かめ、この判定を通過する $a$ を $A$ とすればよい。

十分な確率でACを取れるほど期待実行時間が低いか、テストケースに助けられているだけかどうかは未証明。

「位数が $N$ である $a$ 」を直接求めにいくより、 Editorialの解法②のように「法 $M$ の原始根である $x$ 」を探して、 $A=x^k$ とした方がよかった。
$M-1$ 個ある $a$ の候補中に、ちょうど位数が $N$ となるものはオイラーのトーシェント関数を使って $\phi(N)$ 個しかないので、 $N$ に対して $M$ が大きくなった場合、なかなかヒットしづらい。
位数が $M-1$ となる原始根を探す方が見つかる確率が高く、期待実行時間も短かったかもしれない。

Python3

        
          
          
              
              from collections import defaultdict
 
 
def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]
 
 
def prime_factorize(x, primes=None):
    """ xを素因数分解、辞書型で返す """
    # primes: sqrt(x)までの素数リスト
    #   省略時は奇数を試し割り（2だけ別処理）
    #   単発なら不要だが、複数のxで行う場合は事前計算した方がよい
 
    factors = defaultdict(int)
    if primes is None:
        if x & 1 == 0:
            b = (x & -x).bit_length() - 1
            factors[2] = b
            x >>= b
        primes = range(3, x, 2)
    for p in primes:
        if p * p > x:
            break
        if x % p == 0:
            factors[p] = 1
            x //= p
            while x % p == 0:
                factors[p] += 1
                x //= p
    if x != 1:
        factors[x] = 1
    return factors
 
 
def suspect(a, t, n):
    x = pow(a, t, n)
    n1 = n - 1
    while t != n1 and x != 1 and x != n1:
        x = pow(x, 2, n)
        t <<= 1
    return t & 1 or x == n1
 
 
def miller_rabin(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    check_list = (2, 7, 61) if n < (1 << 32) else (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
    for i in check_list:
        if i >= n:
            break
        if not suspect(i, d, n):
            return False
    return True
 
 
def solve(t, cases):
    primes = get_primes(10 ** 5)
    ans = []
    for n in cases:
        if n == 1:
            ans.append('1 1')
            continue
        p = -1
        for k in range(2, 100000, 2):
            cp = k * n + 1
            if miller_rabin(cp):
                p = cp
                break
        assert p != -1
 
        pfn = prime_factorize(n, primes)
        for a in range(2, p):
            if pow(a, n, p) != 1:
                continue
            ok = True
            for q in pfn.keys():
                if pow(a, n // q, p) == 1:
                    ok = False
                    break
            if ok:
                ans.append(f'{a} {p}')
                break
 
    return ans
 
 
t = int(input())
cases = [int(input()) for _ in range(t)]
ans = solve(t, cases)
print('\n'.join(ans))

            

        
      

D - Moving Pieces on Graph

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいます。
はじめ、コマ A が頂点 $S$ に、コマ B が頂点 $T$ にあります。ここで、 $S,T$ は入力として与えられます。
あなたは以下の操作を好きな順序で好きな回数行うことができます。
- コマ A かコマ B のどちらかを選び、そのコマを今の頂点から辺で結ばれた頂点に移動させる。
- ただし、操作後にコマ A とコマ B が同じ頂点に来るような操作はできない。

あなたの目的はコマ A が頂点 $T$ に、コマ B が頂点 $S$ にある状態にすることです。
あなたが目的を達成することができるか判定し、目的を達成することができる場合は必要な操作回数の最小値を求めてください。

制約

$2\le N\le 2\times 10^5$
$\displaystyle N-1\le M\le \min\left(\frac{N(N-1)}2,2\times 10^5 \right)$
$1\le u_i \lt v_i\le N$
与えられるグラフは単純かつ連結
$1\le S,T\le N$
$S\neq T$
入力される値は全て整数

解法

いろんなケースを注意深く網羅する必要がある。
注意力は要するが、整数論の知識は不要な分、C問題より取り組みやすい。

どこかで2つのコマをすれ違わせないといけない。
パスグラフ（一直線グラフ）の場合は明らかにすれ違えない。以下、グラフはそれ以外の形状とする。

$S,T$ 以外の頂点を以下のように考える。

○○,     ,○        ,○○    左: Tからは、Sを経由しないと行けない頂点
○○- S -○-○-○- T -○○    中: SからもTからも、もう一方を経由せずに行ける頂点
○○'        ○'     `○○    右: Sからは、Tを経由しないと行けない頂点

$d_S[i]:=S$ から $T$ を経由せずに行ける頂点 $i$ までの最短距離、行けない場合はINF
$d_T[i]:=T$ から $S$ を経由せずに行ける頂点 $i$ までの最短距離、行けない場合はINF

また、 $P=(S,p_1,...,T)$ を最短パスの1つとし、その距離を $d_{\min}$ とする。

すれ違うには、以下の2通りが考えられる。

(a)「中」の頂点のうち、 $P$ に使われない頂点がある場合、一方をそこまで持っていってすれ違わせる
(b)「左」または「右」の頂点のうち、次数が3以上の頂点ですれ違わせる

(a)の場合、以下のようにし、移動回数は $d_{\min}+d_S[v]+d_T[v]$ となるので、これが最も小さくなる $v$ を求める。

コマAを $S→v$ まで移動させる
コマBを $P$ に従って $T→S$ まで移動させる
コマAを $v→T$ まで移動させる

※ $d_S,d_T$ に一方を経由してはいけないという制約を課しているのは、 Aが $S→v$ に移動する際に $T$ は通ってはいけない、 $v→T$ に移動する際に $S$ を通ってはいけないためである。

(b)の場合、以下のような感じになる。

...○,               ... A,              ...○,
      ○--A--B-- →        ○--○--  →        ○--B--A--
...○'               ... B'              ...○'

次数3以上で、最も $S$ から近い「左」頂点、または最も $T$ から近い「右」頂点ですれ違わせればよい。
その距離を $d_j$ として、2コマが $d_j+1$ の距離を余分に往復することになるので、以下が移動回数となる。

$2d_{\min} + 4(d_j + 1)$

パスグラフで無い場合、(a)(b)のいずれかには必ず当てはまる。小さい方が答えとなる。

Python3

        
          
          
              
              from collections import deque
 
 
def bfs(s, t, links, return_path):
    """ s から「t を通り越さずに」行ける各頂点への最短距離 """
    q = deque([s])
    dists = [1 << 60] * n
    dists[s] = 0
    predecessors = [-1] * n
    while q:
        u = q.popleft()
        du = dists[u]
        dv = du + 1
        for v in links[u]:
            if dists[v] > dv:
                dists[v] = dv
                predecessors[v] = u
                if v != t:
                    q.append(v)
    if not return_path:
        return dists
 
    path = []
    v = t
    while v != -1:
        path.append(v)
        v = predecessors[v]
    path.reverse()
    return dists, path
 
 
def solve(n, m, s, t, edges):
    s -= 1
    t -= 1
    links = [[] for _ in range(n)]
    degrees = [0] * n
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)
        degrees[u] += 1
        degrees[v] += 1
 
    # パスグラフはすれ違えない。
    if all(d <= 2 for d in degrees) and any(d == 1 for d in degrees):
        return -1
 
    INF = 1 << 60
    dists_s, shortest_path = bfs(s, t, links, True)
    dists_t = bfs(t, s, links, False)
 
    first_best = dists_s[t]
 
    second_best = INF
    ssp = set(shortest_path)
    for i in range(n):
        if i in ssp:
            continue
        second_best = min(second_best, dists_s[i] + dists_t[i])
    ans1 = first_best + second_best
 
    # S-T 間はパスグラフで、最寄りの三叉路までともに行ってすれ違わないといけないケース
    # second_best がとても長い場合、こちらの方が近いこともある。
    nearest_junction = INF
    for i in range(n):
        if degrees[i] >= 3:
            nearest_junction = min(nearest_junction, dists_s[i], dists_t[i])
    ans2 = first_best * 2 + (nearest_junction + 1) * 4
 
    return min(ans1, ans2)
 
 
n, m, s, t = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, s, t, edges)
print(ans)

            

        
      

E - Unfair Game

問題文

正整数 $N,X,Y$ と長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ , $B=(B_1,B_2,\ldots,B_N)$ が与えられます。
$N$ 個の袋があり、それぞれ袋 $1$ から袋 $N$ までの番号が付けられています。袋 $i$ にははじめ金貨が $A_i$ 枚、銀貨が $B_i$ 枚入っています。
この $N$ 個の袋を使って高橋君と青木君がゲームをすることを考えます。最初に高橋君がいくつかの袋を取り（一つも取らなくても良い）、高橋君が取らなかった袋を全て青木君が取ります。その後、高橋君から始めて $2$ 人は交互に以下の操作を繰り返します。
- 自分の持っている袋のうち金貨か銀貨が $1$ 枚以上入っている袋を選び、選んだ袋に対し以下の $2$ つのうちいずれかを行う。
  - 金貨を $1$ 枚取り除き、銀貨を入れる。ただし、銀貨を入れる枚数は高橋君なら $X$ 枚、青木君なら $Y$ 枚である。この操作は金貨が選んだ袋に $1$ 枚以上ある場合にのみ行うことができる。
  - 銀貨を $1$ 枚取り除く。この操作は銀貨が選んだ袋に $1$ 枚以上ある場合にのみ行うことができる。
- その後、選んだ袋を相手に渡す。
先に操作ができなくなったプレイヤーが負けとなります。

$2$ 人が自分が勝つために最適な行動を取ったとき、高橋君が勝てるような最初の袋の取り方が何通りあるかを $998244353$ で割ったあまりを求めてください。

制約

$1\le N\le 2\times 10^5$
$1\le X,Y\le 10^9$
$0\le A_i,B_i\le 10^9$
入力される値は全て整数

解法

袋が1つの場合

状態が多すぎると考察しづらいので、ひとまず「袋が1つしか無い」場合にどうなるか、以下のような再帰関数で調べてみる。

$f(a,b,t,x,y):=$ 金貨から銀貨への両替枚数がそれぞれ $x,y$ 枚で、金貨が $a$ 個、銀貨が $b$ 個入った袋が $t=0$ :高橋君、 $t=1$ :青木君に回ってきたときに、どちらが勝つか

すると、以下の事実が分かる。（ちゃんとした証明はともかく、結果の観察から簡単に推測は付く）

$x,y$ それぞれの「偶奇」により、 $a,b,t$ に対する結果が4通りに分かれる（偶奇が同じものは勝敗状況が同じ）
勝敗は、 $a,b,t,x,y$ によって簡単に（ $O(1)$ で）判別できる
- 具体的な判定方法はEditorial参照。証明は数学的帰納法によって可能

袋は、以下の4パターンに分かれる。

$P$ : どちらが最初に持っていても高橋君が勝つ
$Q$ : 最初に持っていた方が勝つ
$R$ : 最初に持っていた方が負ける
$S$ : どちらが最初に持っていても青木君が勝つ

最初に持ってる方   高橋  青木
               P    ○    ×     ○: 最初に持ってたら必勝
               Q    ○    ○     ×: 最初に持ってたら必敗
               R    ×    ×
               S    ×    ○

袋が複数の場合

持っていたら勝てる袋を「必勝の袋」、逆を「必敗の袋」とする。
（※ここでの「勝てる」は、袋単位の勝敗であり、その袋が空になった状態で相手に渡せる、という意味とする）

つまり、最初の状態では高橋君にとっての $P,Q$ 、青木君にとっての $Q,S$ が必勝の袋となる。

最初に手にする人が決まった時点で、一方の必勝の袋はもう一方の必敗の袋となる。
（そうなるように、必勝側が操作して渡す）

ゲーム中は、単純化すると、以下の応酬が繰り返される。

「必勝の袋」を相手に渡す。相手にとっては「必敗の袋」となる。
「必敗の袋」を相手に渡す。相手にとっての「必勝の袋」となる。

いつか空（＝必敗の袋）となって渡された時、その袋に関してはそれ以上操作できなくなる。
つまり応酬の部分をばっさりカットすると、最初に持つ袋を決めた後、それぞれの中身を以下のように変えてから開始しても結果は変わらない。

「必勝の袋」は、銀貨が1枚だけ入った袋
「必敗の袋」は、最初から空の袋

高橋君がゲームに勝つには、「青木君より多くの必勝の袋を最初に持っている」ことが必要十分条件となることがわかる。
それさえ満たされていれば、必敗の袋はどうであってもよい。

つまり、

初期状態の $P,Q,R,S$ の袋の個数をそれぞれ $p,q,r,s$ 個とする（入力から計算できる固定値）
うち、高橋君が最初に選んだ袋をそれぞれ $i,j,k,l$ 個とする

としたとき、

$i+j \gt (q-j)+(s-l)$ であればよい。
上を満たす $(i,j,l)$ の組毎に $2^r \dbinom{p}{i}\dbinom{q}{j}\dbinom{s}{l}$ 個の選び方がある。

不等式を整理すると $i+2j+l \gt q+s$ となる。
以下のように二項係数の数列を（ $j$ だけは2倍なので1個置きに）定義してこれらを畳み込む。

例)
p=5 → [1,  5, 10, 10,  5,  1]
q=4 → [1,  0,  4,  0,  6,  0,  4,  0,  1]
s=0 → [1]

畳み込んだ結果の $q+s+1$ 以上となる添字部分を合計し、 $2^r$ をかければ答えとなる。

Python3

        
          
          
              
              from pprint import pprint
 
import numpy as np
 
 
def naive1():
    # 1つの山だけのゲーム
    x = 2
    y = 2
 
    # memo[a,b,t] := t=0先手/1後手 に、金貨a枚、銀貨b枚で回ってきたときに、0:先手必勝/1:必敗
    memo = {}
 
    def check(a, b, t):
        if a == 0 and b == 0:
            return t ^ 1
        if (a, b, t) in memo:
            return memo[a, b, t]
        win = t ^ 1
        if b > 0 and check(a, b - 1, t ^ 1) == t:
            win = t
        z = x if t == 0 else y
        if a > 0 and check(a - 1, b + z, t ^ 1) == t:
            win = t
        memo[a, b, t] = win
        return win
 
    sa = 10
    sb = 10
    print(check(sa, sb, 0))
    print(check(sa, sb, 1))
 
    mb = max(b for a, b, t in memo)
    res0 = [[8] * (mb + 1) for _ in range(sa + 1)]
    res1 = [[8] * (mb + 1) for _ in range(sb + 1)]
    res0[0][0] = 1
    res1[0][0] = 0
    for (a, b, t), r in memo.items():
        if t == 0:
            res0[a][b] = r
        else:
            res1[a][b] = r
 
    pprint(res0, width=200)
    pprint(res1, width=200)
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs
 
 
def _convolve(f, g):
    # 小さいうちは愚直の方が高速。convolve_mod()と併用するなら大丈夫だが、単独で使用する場合はオーバーフローに注意
    if len(f) * len(g) < 10000:
        return np.convolve(f, g)
 
    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1
 
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg
 
    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)
 
    return h[:true_len]
 
 
def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)
 
    a = _convolve(f1, g1) % p
    c = _convolve(f2, g2) % p
    b = (_convolve(f1 + f2, g1 + g2) - (a + c)) % p
 
    h = (a << 30) + (b << 15) + c
    return h % p
 
 
def solve(n, x, y, coins):
    if x % 2 == 0:
        if y % 2 == 0:
            judge0 = lambda a, b: (a ^ b ^ 1) & 1
            judge1 = lambda a, b: (a ^ b) & 1
        else:
            judge0 = lambda a, b: 0 if a > 0 else (b + 1) % 2
            judge1 = lambda a, b: 0 if a > 1 else b % 2
    else:
        if y % 2 == 0:
            judge0 = lambda a, b: 1 if a > 1 else (b + 1) % 2
            judge1 = lambda a, b: 1 if a > 0 else b % 2
        else:
            judge0 = lambda a, b: (b + 1) % 2
            judge1 = lambda a, b: b % 2
 
    win = [[0, 0], [0, 0]]
    for a, b in coins:
        win[judge0(a, b)][judge1(a, b)] += 1
 
    p, q = win[0]
    r, s = win[1]
    c1 = [0] * (p + 1)
    c2 = [0] * (q * 2 + 1)
    c3 = [0] * (s + 1)
    MOD = 998244353
    facts, finvs = precompute_factorials(max(p, q, s), MOD)
 
    for i in range(p + 1):
        c1[i] = facts[p] * finvs[i] * finvs[p - i] % MOD
    for j in range(q + 1):
        c2[j * 2] = facts[q] * finvs[j] * finvs[q - j] % MOD
    for l in range(s + 1):
        c3[l] = facts[s] * finvs[l] * finvs[s - l] % MOD
 
    c12 = convolve_mod(c1, c2, MOD)
    c123 = convolve_mod(c12, c3, MOD)
    ans = sum(c123[q + s + 1:]) % MOD
    ans *= pow(2, r, MOD)
    ans %= MOD
    return ans
 
 
n, x, y = map(int, input().split())
coins = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, x, y, coins)
print(ans)

            

        
      

−目次

AtCoder Regular Contest 191 (Div. 2) A,B,C,D,E問題メモ

A - Replace Digits

問題文

制約

解法

B - XOR = MOD

問題文

制約

解法

C - A^n - 1

問題文

制約

解法

MM の求め方

AA の求め方

D - Moving Pieces on Graph

問題文

制約

解法

E - Unfair Game

問題文

制約

解法

袋が1つの場合

袋が複数の場合

$M$ の求め方

$A$ の求め方