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

AtCoder Regular Contest 200 (Div. 2)

祝☆200回

A - Dot Product

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$ が与えられます。
以下の条件を全て満たす整数列 $X=(X_1,X_2,\ldots,X_N)$ が存在するか判定し、存在するなら一つ求めてください。
- $-10^8\le X_i\le 10^8$ $(1\le i\le N)$
- $\displaystyle \sum_{i=1}^N A_iX_i \gt 0$
- $\displaystyle \sum_{i=1}^N B_iX_i \lt 0$

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

制約

$1\le T\le 2\times 10^5$
$1\le N\le 2\times 10^5$
$1\le A_i,B_i\le 10^5$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

$\displaystyle C=\sum_{i=1}^N A_iX_i, \ \ D=\sum_{i=1}^N B_iX_i$ とする。

$N=1$ のとき

$A_i,B_i$ は正より、$C,D$ も両方正か両方負にしかできないので不可能。

$N=2$ のとき

$(A_i,B_i)$ を $gcd(A_i,B_i)$ で割って、互いに素にしたものを $(A'_i,B'_i)$ とする。

$(A'_1,B'_1)=(A'_2,B'_2)$ の時は不可能である。
$(C,D)$ が取り得る領域は $y=\frac{B_1}{A_1}x$ 上の直線上にしか存在せず、この直線は第1と第3象限しか通らない。

それ以外の時、以下のようにできる。

A    20   25
B    31   41

まず、Aを揃える。

 X   25   20
AX  500  500
BX  775  840

この例では BX1 < BX2 なので、X=(25,-20) とすれば、C=0, D<0 にできる。

また、Bを揃える。

 X   41   31
AX  840  775
BX 1271 1271

この例では AX1 > AX2 なので、X=(41,-31) とすれば、C>0, D=0 にできる。

そしてこれは線形的に合成できるので、
X=(25+41, -20-31) とすれば、C>0,D<0 にできる。

 X   66   -51
AX 1320 -1275  →  C =  45 > 0
BX 2046 -2091  →  D = -45 < 0

大小関係が逆の場合は符号が逆になる。

$-2 \times 10^5 \le -(A_{\max}+B_{\max}) \le X_i \le (A_{\max}+B_{\max}) \le 2 \times 10^5$ より、値の範囲も大丈夫。

$N \ge 3$ のとき

全ての $(A'_i,B'_i)$ が一致していたら不可能。

それ以外の場合、$(A'_i,B'_i)$ が異なる2つを持ってきて、$N=2$ の時に帰着し、他は $0$ にすればよい。

Python3

from math import gcd


def solve(n, aaa, bbb):
    if n == 1:
        return None

    i1, a1, b1, g1 = -1, -1, -1, -1
    i2, a2, b2, g2 = -1, -1, -1, -1
    for i in range(n):
        a = aaa[i]
        b = bbb[i]
        g = gcd(a, b)
        a //= g
        b //= g
        if a1 == b1 == -1:
            i1 = i
            a1 = a
            b1 = b
            g1 = g
            continue
        if a1 == a and b1 == b:
            continue
        i2 = i
        a2 = a
        b2 = b
        g2 = g
        break
    else:
        return None

    assert b1 * a2 != a1 * b2
    a1 *= g1
    b1 *= g1
    a2 *= g2
    b2 *= g2
    if b1 * a2 < a1 * b2:
        x1 = a2 + b2
        x2 = -a1 - b1
    else:
        x1 = -a2 - b2
        x2 = a1 + b1

    ans = [0] * n
    ans[i1] = x1
    ans[i2] = x2

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, aaa, bbb)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(*ans)

B - LCM

問題文

正整数 $A_1,A_2,A_3$ が与えられます。
以下の条件を全て満たす正整数の組 $(X_1,X_2)$ が存在するか判定し、存在する場合は一組求めてください。
- $X_1$ は十進法で $A_1$ 桁の整数である。
- $X_2$ は十進法で $A_2$ 桁の整数である。
- $X_1$ と $X_2$ の最小公倍数は十進法で $A_3$ 桁の整数である。

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

制約

$1\le T\le 17^3$
$1\le A_1,A_2,A_3\le 17$
入力される値は全て整数

解法

互いに素な $X_1,X_2$ なら、最小公倍数は $X_1 \times X_2$ になるので桁数がわかりやすい。
そういう方向に持ってけないか考える。

$a$ 桁× $b$ 桁は、$a+b-1$ または $a+b$ 桁となる。

a=4, b=5
最小: 1000 * 10000 =  10000000  →8桁
最大: 9999 * 99999 = 999890001  →9桁

最小公倍数は2数の積より大きくはならないので、$A_1 + A_2 \lt A_3$ なら不可能。
また、最小公倍数は元の数より小さくならないので、$A_1 \gt A_3$ や $A_2 \gt A_3$ の場合も不可能。

それ以外の場合、互いに素であることが保証される素数を使って、構築できる。
直接的に $A_1+A_2=A_3$ または $A_1+A_2=A_3-1$ という関係性に無い場合は、末尾に0を追加して調整する。

xはa桁、yはb桁、x,yは互いに素、z=xy

LCM( x0000 , y0000 ) = z0000
     ~~~~~   ~~~~~     ~~~~~
     a+4桁   b+4桁     a+b+4 または (a+b-1)+4 桁

$A_1+A_2-1 \le A_3 \le A_1+A_2$ になるまで、$A_1,A_2,A_3$ から1ずつ引いていく。
この時引いた回数を $d$、引いた結果を $A'_1,A'_2,A'_3$ として、$X_1,X_2$ は以下のように作れる。

$A'_3=A'_1+A'_2-1$ の時
- $X'_1=A'_1$ 桁の最小の素数
- $X'_2=A'_2$ 桁の2番目に小さい素数
$A'_3=A'_1+A'_2$ の時
- $X'_1=A'_1$ 桁の最大の素数
- $X'_2=A'_2$ 桁の2番目に大きい素数
$X_1=X'_1$ の末尾に0を $d$ 個追加したもの
$X_2=X'_2$ の末尾に0を $d$ 個追加したもの

この方法で $X'_1 \times X'_2$ が $A'_3$ 桁となり、$X_1 \times X_2$ が $A_3$ 桁となる。
素数はわりと密に存在するので、各桁の最小や最大（$1000$ や $9999$ など）から多少ずれたとしても、積の桁数が変わるほどずれることはない。

「$k$ 桁の最小・最大の素数」を得るには、Pythonなら sympy.nextprime, prevprime が使える。

Number Theory - SymPy 1.14.0 documentation

Python3

SMALL_PRIME = [
    0,
    2,
    11,
    101,
    1009,
    10007,
    100003,
    1000003,
    10000019,
    100000007,
    1000000007,
    10000000019,
    100000000003,
    1000000000039,
    10000000000037,
    100000000000031,
    1000000000000037,
    10000000000000061,
]
LARGE_PRIME = [
    0,
    7,
    97,
    997,
    9973,
    99991,
    999983,
    9999991,
    99999989,
    999999937,
    9999999967,
    99999999977,
    999999999989,
    9999999999971,
    99999999999973,
    999999999999989,
    9999999999999937,
    99999999999999997,
]
SMALL_PRIME2 = [
    0, 3, 13, 103, 1013, 10009, 100019, 1000033, 10000079, 100000037, 1000000009, 10000000033, 100000000019,
    1000000000061, 10000000000051, 100000000000067, 1000000000000091, 10000000000000069,
]
LARGE_PRIME2 = [
    0, 5, 89, 991, 9967, 99989, 999979, 9999973, 99999971, 999999929, 9999999943, 99999999947, 999999999961,
    9999999999863, 99999999999971, 999999999999947, 9999999999999917, 99999999999999977,
]


def solve(a, b, c):
    if a + b < c:
        return -1, -1
    zfill = 1
    while c < a + b - 1:
        a -= 1
        b -= 1
        c -= 1
        zfill *= 10
    if a <= 0 or b <= 0 or c <= 0:
        return -1, -1

    if a + b - 1 == c:
        x1 = SMALL_PRIME[a] * zfill
        x2 = SMALL_PRIME2[b] * zfill
    else:
        x1 = LARGE_PRIME[a] * zfill
        x2 = LARGE_PRIME2[b] * zfill

    return x1, x2


t = int(input())
for _ in range(t):
    a, b, c = map(int, input().split())
    x, y = solve(a, b, c)
    if x == -1:
        print('No')
    else:
        print('Yes')
        print(x, y)

C - Movie Theater

問題文

正整数 $N$ と長さ $N$ の正整数列 $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$ が与えられます。
- ここで、 $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ は全て互いに異なることが保証されます。
ある映画館には $N$ 個の席が左右一列に並んでいます。左から $i$ 番目の席を席 $i$ と呼びます。
この映画館に人 $1$ から人 $N$ までの $N$ 人の人が訪れます。あなたは各人に席を $1$ つずつ割り当てます。
人 $i$ に割り当てた席を $P_i$ とすると、人 $i$ は時刻 $L_i$ に席 $1,2,\ldots,P_i-1$ を横切って席 $P_i$ に座り、時刻 $R_i$ に席 $1,2,\ldots,P_i-1$ を横切って席から離れます。
人 $i$ の不満度を時刻 $L_i$ から時刻 $R_i$ までの間（ちょうど $L_i,R_i$ は含まない）に他の人に席 $P_i$ を横切られた回数とします。
人 $1$ から人 $N$ までの $N$ 人の不満度の総和が最小となる $(1,2,\ldots,N)$ の順列 $P$ のうち辞書順最小のものを求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 500$
$1\le N\le 500$
$1\le L_i \lt R_i\le 2\times N$
$L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ は全て互いに異なる
全てのテストケースにおける $N$ の総和は $500$ 以下
入力される値は全て整数

解法

答えが逆（シート $i$ に誰を座らせるか）という問題だったらトポロジカルソートで簡単に求まるのに、、、
「人 $i$ をどのシートに座らせるか」を辞書順最小にするのに意外と手こずった。

$[L_i,R_i]$ を数直線にプロットし、その関係性を3種類に場合分けする。

■交わらない

  |----1----|     |---2---|

この場合、お互いに不満度を与えることはない。
座らせるシートの左右位置関係はどちらでも良い。

■交差する
  |----1----|
     |----2----|

人1を左に座らせると、人2の入館時に1が不満を1覚える。
人2を左に座らせると、人1の退館時に2が不満を1覚える。
どちらにしろ不満が1増えるのは変わらないので、座らせる位置関係はどちらでもよい。

■包含する
  |-------1-------|
     |----2---|

人1を左に座らせると、人2の入館時と退館時に不満を2覚える。
人2を左に座らせると、不満は増えない。
よってこの場合は、人2を左に座らせないといけない。P2 < P1 となる。

一部の $P$ の値に大小関係の制約ができたが、包含関係のみに由来するのでこの制約は推移的である。
つまり、$P_i \lt P_j$ かつ $P_j \lt P_k$ となる $(i,j,k)$ に対し、$P_i \lt P_k$ が必ず成り立ち、矛盾することはない。

この制約、つまり「入退館時刻が包含関係にある2人は、短い方を左のシートに座らせる」というルールさえ守っていれば、不満度最小は達成できる。

$i=1$ から、「シートの範囲と、この範囲のシートに座らせる人の集合」を分割していくように貪欲に求めていける。

例えば $N=8$ で、

$P_1 \gt P_i$ となるような $i$ : $\{3,5,8\}$
$P_1 \lt P_i$、または $1$ との制約がない $i$ : $\{2,4,6,7\}$

に分けられる場合、人 $1$ はなるべく左に座らせたい（$P_1$ を小さくしたい）ので、 $3,5,8$ のみ左に座らせ、人 $1$ は4番目のシートに座ることになる。$P_1=4$ と決まる。

シートに誰を座らせるか（$P$ の逆順列）の順列を $Q$ とすると、このように部分的に決まる。

i   1 2 3   4   5 6 7 8
Q  {3,5,8}  1  {2,4,6,7}

$i$ と $Q$（ひいては $P_i$ と $i$）の対応が分割され、左と右で再帰的に同じような問題と見なせる。

たとえば左では、$\{3,5,8\}$ のうち最小の番号の人が $3$ なので、$P_3$ の値を最小にすることを考える。

$\{5,8\}$ のうち、$P_3 \gt P_i$ となるような $i$ : $\{8\}$
$\{5,8\}$ のうち、$P_3 \lt P_i$ または制約がない $i$ : $\{5\}$

だったとすると、以下のように決まる。

i   1   2   3   4   5 6 7 8
Q  {8}  3  {5}  1  {2,4,6,7}

このように、グループのうち番号が最小の人の座るシートを決めていくと、$O(N^2)$ で解ける。

Python3

def solve(n, lrs):
    # matrix[i][j] = 0: iよりjは左に置くべき（Pi>Pj）  i が j を内包している
    # matrix[i][j] = 1: iよりjは右に置くべき（Pi<Pj）  それ以外
    matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        l1, r1 = lrs[i]
        for j in range(i + 1, n):
            l2, r2 = lrs[j]
            if l1 < l2 and r2 < r1:
                matrix[i][j] = 1

    ans = [0] * n

    def sub(segments, offset):
        left = []
        right = []
        i = min(segments)
        for j in segments:
            if i == j:
                continue
            if matrix[i][j] == 0:
                right.append(j)
            else:
                left.append(j)
        ans[i] = offset + len(left) + 1
        if left:
            sub(left, offset)
        if right:
            sub(right, offset + len(left) + 1)

    segments = list(range(n))
    sub(segments, 0)

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    lrs = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, lrs)
    print(*ans)

D - |A + A|

問題文

正整数 $M,K$ が与えられます。
以下の条件を全て満たす正整数 $N$ と整数列 $A=(A_1,A_2,\ldots, A_N)$ が存在するか判定し、存在するなら一つ求めてください。
- $1\le N\le M$
- $0\le A_i \lt M$ $(1\le i\le N)$
- $k\equiv A_i+A_j \pmod M$ を満たす添字の組 $(i,j)$ が存在するような整数 $0\le k \lt M$ がちょうど $K$ 個存在する。

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

制約

$1\le T\le 2\times 10^5$
$1\le K\le M\le 2\times 10^5$
全てのテストケースにおける $M$ の総和は $2\times 10^5$ 以下
入力される値は全て整数

解法

3つめの条件がちょっと分かりづらいが、要は100ますけいさんのように数列 $A$ を縦と横に書いて足し算(mod)して、その表に表れる数字の種類数が $K$ 個になるように $A$ を決めよ、と言っている。

  | 3  1  4
--+---------
3 | 6  4  7     2,4,5,6,7,8 の6種類
1 | 4  2  5
4 | 7  5  8

言わずもがな表の値は対角線を挟んで対称なので、右上の部分のみ考える。

いろいろ実験してみる。シンプルに、$A=(0,1,2,...)$ としてみると、

  | 0  1  2  3     A=(0,1,...,x) とすると、
--+------------    0～2x の 2x+1 個の値が現れる。
0 | 0  1  2  3
1 |    2  3  4
2 |       4  5
3 |          6

$A=(0,1,2,...,\frac{K-1}{2})$ とすることで、$K$ が奇数の場合は必ず構築できるとわかる。

では、$K$ が偶数の場合は？

何となく、$\mod{M}$ を利用することを考えると訳わかんなくなりそうなので、まずはなるべく和が $M$ 未満に収まるようなものを考えたい。
上記の場合は $0～2x$ の値が使われたが、では、$A=(0,2,3,...,x)$ とすると $1$ だけを使わないようにできるのでは？

     | 0  2  3  4  5
   --+---------------
   0 | 0  2  3  4  5
   2 |    4  5  6  7
   3 |       6  7  8
   4 |          8  9
   5 |            10
        ┘ ┘ ┘ ┘ ┘
種類数  1  3  6  8  10

$K \ge 6$ の偶数なら狙い通りとなり、$A=(0,2,3,...,\frac{K}{2})$ でできそう。
ただし、$K=M$ の時、たとえば $K=M=8$ の時、 $A=(0,2,3,4)$ とすると $4+4=8$ がmodで $0$ になってしまい、$7$ 種類になってしまう。

しかしこの場合は、そもそも $0～M-1$ を全て出現させれば良いので、適当に密に作ればよい。
$A=(0,1,...,M-1)$ などがあてはまる。

これを最初に判定して除けば、$K \ge 6$ の偶数ならできることが分かった。

残るは $K=2,4$ の時のみ。
愚直ケースを書いて調べると、$M$ が $K$ の倍数の時は、 $(0,\frac{M}{K},2\frac{M}{K},...,(K-1)\frac{M}{K})$ を和に全て出現させることで達成できることがわかる。

M=12  K=4

  | 0  3  6  9     K=M の場合の応用バージョン
--+------------
0 | 0  3  6  9
3 |    6  9  0
6 |       0  3
9 |          6

$K=2,4$ で $M$ が $K$ の倍数でない時にできない証明がなかなか難しいが、まぁ、愚直でここまで綺麗な法則が現れたら大丈夫やろと信じれば通る。

証明は公式Editorial参照。

解説 - AtCoder Regular Contest 200 (Div. 2)

まとめると、（上から順に判定して当てはまれば終了）

$M$ が $K$ の倍数なら、$A=(0,\frac{M}{K},2\frac{M}{K},...,(K-1)\frac{M}{K})$
$K$ が奇数なら、$A=(0,1,2,...,\frac{K-1}{2})$
$K$ が6以上の偶数なら、$A=(0,2,3,...,\frac{K}{2})$
それ以外は不可能

Python3

def solve(m, k):
    if m % k == 0:
        d = m // k
        ans = list(range(0, m, d))
        return ans

    if k == 2 or k == 4:
        return None

    if k % 2 == 1:
        ans = list(range(k // 2 + 1))
        return ans

    ans = [0] + list(range(2, k // 2 + 1))
    return ans


t = int(input())
for _ in range(t):
    m, k = map(int, input().split())
    ans = solve(m, k)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(len(ans))
        print(*ans)

E - popcount <= 2

問題文

正整数 $N,M$ が与えられます。
長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ であって、以下の条件を全て満たすものの個数を $998244353$ で割ったあまりを求めてください。
- $0\le A_i \lt 2^M$ $(1\le i\le N)$
- $\operatorname{popcount}(A_i\oplus A_j) \le 2$ $(1\le i \lt j\le N)$

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

制約

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

解法

丁寧な場合分け。

まず、条件を満たす数列 $A$ の各要素に対し $1$ 以上 $2^M$ 未満の同じ値をXORしたものも、また別の条件を満たす数列となる。
よって $A_1=0$ の場合を考えることとし、最終的な答えはそれを $2^M$ 倍すればよい。

$A_1=0$ の時、当然、他の全ての要素のpopcountは $2$ 以下でなければならない。

$\max(\operatorname{popcount}(A_i)) \le 1$

全ての $A_i$ が、$0$ または1つだけbitが立っている数列は条件を満たす。

$i=2～N$ につき、$A_i$ の選択肢が $M+1$ 通り、独立にあるので、$(M+1)^{N-1}$ 通り。

$\max(\operatorname{popcount}(A_i)) = 2$

愚直を書いて観察すると、3パターンに分かれて考えられそう。

①ある共通のbit1つと、他に高々1つのbitが立っている場合
②$\{00,01,10,11\}$ の4つからなる場合
③$\{000,011,101,110\}$ の4つからなる場合

①

こんなやつ

共通のbit位置が $M$ 通りある。それを固定したとき、$A_2～A_{N}$ に置く数は以下の $M+1$ 通りが選択肢としてあり得る。

a) 他にどこか立っている $M-1$ 通り
b) 共通のbitのみが立っている
c) $0$

このうち、「b) または c) のみからなる」ものは、$\max(\operatorname{popcount}(A_i)) \le 1$ で既に数えられている。

また、「a) または c) のみからなり、a) で共通のbitの他に立てたbitが全てで一致」するものは、 ①の過程で2回ずつ重複して数えられる。

よって、共通bitを固定すると $(M+1)^{N-1}-2^{N-1}-\frac{(2^{N-1}-1)(M-1)}{2}$ の組合せがある。
この $M$ 倍が①の場合の答えとなる。

②,③

補足すると、「$\{00,01,10,11\}$ の4つからなる」とは、$M$ 個中どこか2箇所のbitを選んで、それが $(0,0),(0,1),(1,0),(1,1)$ のどれか、他は $0$ である状態を示す。

どのbitを選ぶかは、②は ${}_M C_2$ 通り、③は ${}_M C_3$ 通りある。
これを固定した場合を考えて、あとで倍加する。

いずれも、4つ全てが出現する場合以外は既に数えられている。

$0$ は $A_1$ で必ず出現することに注意して包除原理を適用すると、 $A_2$ 以降の決め方は $4^{N-1} - 3 \times 3^{N-1} + 3 \times 2^{N-1} - 1$ 通りずつある。

この $({}_M C_2 + {}_M C_3)$ 倍が、②③の場合の答えとなる。

Python3

from collections import defaultdict


def naive(n, m):
    from itertools import product

    def check(aaa):
        diff_bits = 0
        for i in range(n):
            for j in range(n):
                xor = aaa[i] ^ aaa[j]
                if xor.bit_count() > 2:
                    return -1
                diff_bits |= xor
        return diff_bits.bit_count()

    sample = defaultdict(list)
    for aaa in product(range(1 << m), repeat=n):
        d = check(aaa)
        if d == -1:
            continue
        sample[d].append(aaa)

    ans = 0
    for d in sorted(sample.keys()):
        print(f'{d=} l={len(sample[d])} {sample[d][:5]=}')
        ans += len(sample[d])
    print(f'{ans=}')


def solve():
    MOD = 998244353
    INV2 = pow(2, -1, MOD)

    def main(n, m):

        # A1 = 0 に固定して考え、最後に 2^M 倍する。

        # 立ってるのが最大1個
        # A2以降のN-1個の要素は、M個のどれかが立っている or どれも立っていない
        ans = pow(m + 1, n - 1, MOD)

        # 立ってるのが最大2個
        # パターン1:
        # * 共通の1つのbitが立ってて、他に立ってるbitが高々1個（共通のbitしか立っていないものも含めM通り）
        # * または 0
        tmp = pow(m + 1, n - 1, MOD)  # 共通のbitが決まってる場合の全通り
        tmp -= pow(2, n - 1, MOD)  # 全てが（共通のbitしか立っていない or 0）の場合は重複する
        tmp -= (pow(2, n - 1, MOD) - 1) * (m - 1) * INV2  # 全てが 00 11 だけのものは、重複して2回ずつ数えられている
        ans += tmp * m  # 共通のbitの選び方
        ans %= MOD

        # パターン2:
        # * 000, 011, 110, 101 の4つの中から選ばれる
        # パターン3:
        # * 00, 01, 10, 11 の4つの中から選ばれる
        if n >= 4:
            # いずれのパターンも、4つ全てが含まれるものでなければ、これまでのものと重複する。
            tmp = pow(4, n - 1, MOD)
            tmp -= pow(3, n - 1, MOD) * 3
            tmp += pow(2, n - 1, MOD) * 3
            tmp -= 1
            mC3 = m * (m - 1) * (m - 2) // 6  # パターン2 の3bitの選び方
            mC2 = m * (m - 1) // 2  # パターン3 の2bitの選び方
            ans += tmp * (mC3 + mC2)
            ans %= MOD

        ans *= pow(2, m, MOD)
        ans %= MOD

        return ans

    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        ans = main(n, m)
        print(ans)
        # naive(n, m)


solve()

目次

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

A - Dot Product

問題文

制約

解法

$N=1$ のとき

$N=2$ のとき

$N \ge 3$ のとき

B - LCM

問題文

制約

解法

C - Movie Theater

問題文

制約

解法

D - |A + A|

問題文

制約

解法

E - popcount <= 2

問題文

制約

解法

$\max(\operatorname{popcount}(A_i)) \le 1$

$\max(\operatorname{popcount}(A_i)) = 2$

①

②,③