AtCoder Regular Contest 218 A～E問題メモ

AtCoder Regular Contest 218

A - Many Sets

• 長さ $M$ の正整数列が $N$ 個与えられます。$i$ 個目の正整数列は $A_i=(A_{i,1},A_{i,2},\dots,A_{i,M})$ です。
• これら $N$ 個の正整数列から $1$ 個ずつ要素を選ぶ方法は $M^N$ 通りあります。
• その全てに対する「選んだ要素に含まれる整数の種類数」の総和を $998244353$ で割った余りを求めてください。

• $1 \le N,M \le 500$
• $1 \le A_{i,j} \le NM$
• 入力は全て整数

以下のDPを定義する。ただし、要素は一様ランダムに選ばれるものとする。

• $\mathrm{DP}[i,a]:=i$ 番目の数列までで、要素 $a$ が1回以上選ばれている確率

初期値 $\mathrm{DP}[0,*]$ は全て $0$ とする。最終的に種類数の期待値は $\sum_a \mathrm{DP}[N,a]$ となり、問題の答えはそれに $M^N$ をかけたものとなる。

$i$ 番目の数列に $a$ が $c$ 個出現しているとすると、

• $\mathrm{DP}[i,a]+=(1-\mathrm{DP}[i-1,a]) \times \dfrac{c}{M}$

のように更新できる。 つまり、（$i-1$ までで $a$ が選ばれていない確率）×（$i$ で $a$ が選ばれる確率）だけ、$a$ の選ばれている確率が増える。

$i$ 番目の数列に出現しない要素に変化はないので、出現する箇所のみ更新すればよい。
また、実装の上では $i$ の次元は省略し、$\mathrm{DP}'[a]$ を直接更新していってよい。

計算量は $O(NM)$

Python3

from collections import Counter


def solve(n, m, aaas):
    MOD = 998244353
    INV_M = pow(m, MOD - 2, MOD)
    dp = [0] * (n * m + 1)
    for aaa in aaas:
        for a, c in Counter(aaa).items():
            dp[a] += (1 - dp[a]) * c * INV_M
            dp[a] %= MOD
    ans = sum(dp) * pow(m, n, MOD)
    ans %= MOD
    return ans


n, m = list(map(int, input().split()))
aaa = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, m, aaa)
print(ans)

B - All Minus

• 黒板に $N$ 個の非負整数 $A_1,A_2,\dots,A_N$ が書かれています。
• Alice と Bob がゲームをします。Alice から始めて以下の操作を交互に行い、黒板に書かれている整数を $0$ 個にした方が勝ちです。
  • 操作を行う時点で黒板に書かれている最小の非負整数を $m$ とする。
    • $m \gt 0$ のとき、$1$ 以上 $m$ 以下の正整数 $x$ を選ぶ。黒板に書かれている全ての整数をそれぞれ今の値から $x$ 引いた数に書き換える。
    • $m = 0$ のとき、黒板に書かれている $0$ のうち、$1$ 個以上を削除する。
• 両者が勝つために最善な行動をしたとき、勝つのがどちらか判定してください。

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

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• 全てのテストケースに対する $N$ の総和は $2 \times 10^5$ 以下
• 入力は全て整数

$A$ は昇順にソート済みとする。

棒グラフを描いてみると、ゲームで取れる行動の良い言い換えが見える。

A = (1, 2, 4, 4, 7)

→┝┓
  ├┗┓
  ├─┗━┓
  ├───┨
  ├───┗━━┓
  ├──────┨
                ↓

棒グラフの左上（矢印→の先）にコマを置き、以下のルールに沿って交互に動かし、右下↓に到達させた方が勝ちとなる。

• コマは、棒の上か右の線上のみ、右か下方向に動ける（太く示した部分）
• 1以上の任意の整数距離動かせる。
• 1回の移動の中で方向転換禁止

方向転換まで残り距離 $1$ なら、動かし方に選択の余地がない。
$A=(1,2,3,4,5,6)$ のような、ヨコ（前の要素との差分）もタテ（同じ値を持つ要素の個数）も1ずつしかない状態だと、両者とも選択の余地はないまま交互に動かすだけになる。

しかし、$A=(1,2,4,4,7)$ のように、ヨコやタテに距離 $2$ 以上が発生すると、その手番のプレイヤーは

• その距離を全て消費しきる
• その距離を $1$ だけ残して消費しきる

を自由に選択することで、攻守（？）を交替できる。

つまり、「次に出現する、距離 $2$ 以上の辺」があるなら再びそれを自分の手番にするように、 ないなら最後に自分が勝つように選択できる。

最初からシミュレーションして、

• 最初に距離 $2$ 以上の辺に遭遇した手番のプレイヤーが勝利
• 最後まで1つも無いなら、動かし方は一意なのでシミュレーションの結果が答え

$A$ が $0$ を含む場合はAliceは初手↓方向に動かすので注意。

Python3

import random
from collections import Counter


def naive(n, aaa, debug_print=True):
    aaa = tuple(sorted(aaa))
    memo = {}

    def sub(aaa, i):
        if (aaa, i) in memo:
            return memo[aaa, i]
        if i == n:
            return False
        if aaa[i] == 0:
            l = i
            while l < n and aaa[l] == 0:
                res = sub(aaa, l + 1)
                if res == False:
                    memo[aaa, i] = True
                    return True
                l += 1
            memo[aaa, i] = False
            return False
        a = aaa[i]
        for x in range(1, a + 1):
            new_aaa = (0,) * i + tuple(a - x for a in aaa[i:])
            res = sub(new_aaa, i)
            if res == False:
                memo[aaa, i] = True
                return True
        memo[aaa, i] = False
        return False

    ans = sub(aaa, 0)

    if debug_print:
        print(f'{n=} {aaa=}')
        print(memo)

    return ans


def solve(n, aaa):
    ans = True
    cnt = Counter(aaa)

    if 0 in cnt:
        if cnt[0] >= 2:
            return True
        ans = False
        del cnt[0]

    p = 0
    for a in sorted(cnt.keys()):
        c = cnt[a]
        if a - p >= 2:
            return ans
        ans = not ans
        if c >= 2:
            return ans
        ans = not ans
        p = a

    ans = not ans
    return ans


def check():
    n = 6
    lim = 6
    for _ in range(100):
        aaa = random.choices(range(lim + 1), k=n)
        ans1 = solve(n, aaa)
        ans2 = naive(n, aaa, False)
        if ans1 == ans2:
            continue
        print(f'==== NG ==== {ans1=} {ans2=}')
        print(f'{n}')
        print(*aaa)
    print('FINISH')

# check()

t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    if ans:
        print('Alice')
    else:
        print('Bob')

C - Amidakuji

• この問題はインタラクティブな問題です。
• 正整数 $N$ が与えられます。
• 正整数 $m$ と $m$ 個の $(1,2,\dots,N)$ の順列を好きに決め、出力してください。
  • このうち $i$ 個目の順列を $P_i=(P_{i,1},P_{i,2},\dots,P_{i,N})$ とします。
  • これは「$k→P_{i,k}$ という置換」を表すとし、「置換 $i$」と呼ぶこととします。
• その後、$(1,2,\dots,N)$ の順列 $Q=(Q_1,Q_2,\dots,Q_N)$ が与えられます。
• 以下の条件を全て満たすような正整数列 $A=(A_1,A_2,\dots,A_k)$ を出力してください。
  • $0 \le k \le 2N^2$
  • $A$ の要素は全て $1$ 以上 $m$ 以下
  • 数列 $R=(1,2,\dots,N)$ に対して、$i = 1,2,\dots,k$ の順に置換 $A_i$ を行うと $R = Q$ となる。

• 上記の問題を $Q$ によらずに正解する上での最小の $m$ を $m_{\min}$ とします。あなたの出力する $m$ は $m_{\min}$ でなければなりません。

• $3 \le N \le 500$
• $Q$ は $(1,2,\dots,N)$ の順列
• 入力は全て整数

少し問題がややこしい。複数の置換の組合せで $(1,2,3,...,N)→Q$ の置換を表現するが、$Q$ が先読みで分かってしまうと自明すぎるので、最初に使う置換を宣言させられる。

（言うて600点問題というメタ読みも含め） そこまで複雑な構築にはならず、ある程度 $m$ 個の数列は規則的なものになるはずと当たりを付ける。

いくらかの試行錯誤の末、$m=2$ が必ず達成可能であることに気付く。

1. $1～N-1$ をローリングし、$N$ はそのまま動かない置換
2. $N-1$ と $N$ をswapし、他は動かない置換

$m=1$ が不可能な略証

要は、$1～N-1$ をループ式のベルトコンベアと見なし、 要素を $N$ にストックしては好きな位置に戻すことを繰り返して、任意の並びを作れる。

1つの要素を好きな位置に持っていくために

• 最大 $N-1$ 回のローリングで、対象要素を位置 $N-1$ に持ってくる
• swapして $N$ にストック
• 最大 $N-1$ 回のローリングで、挿入したい位置に持ってくる
• swap

計 $2N$ で達成可能となる。全体で約 $2N^2$ と見積もれ、まさに問題の条件通りなので確信度が高まる。

まずは考えやすくするため、「$(1,2,...,N)→Q$ にする置換列」と「$S→(1,2,...,N)$ にする置換列」が 同じになる $S$ を特定し、後者で考える。$S$ は、$Q$ の逆順列（indexと値が逆転したもの）とすればよい。

$S$ に対し、$i=2,3,...,N-1$ の順に、要素 $i$ を $i-1$ の直後に持ってこさせる。つまり、

• $i=2,3,...,N-1$ の順に、
  • 要素 $i$ がストック（位置 $N$）になければ、
    • 位置 $N-1$ までローリングする
    • swapする
  • 要素 $i-1$ を位置 $N-2$ までローリングする
  • swapする
• 最後に要素 $1$ が位置 $1$ に来るまでローリングする

とすることで構築できる。各操作は、実際に数列をその通りにシミュレーションして確かめて $O(N^3)$ なので十分間に合う。

なお、必要は無いが、工夫すれば最悪操作回数を約 $2N^2→N^2$ に減らせる。
最初に要素 $1$ の位置から要素 $2～N-1$ の相対的な挿入位置は決められるので、$i=2,3,...$ の順ではなく、 現在ストックに入っている値から、目標の位置に挿入（その際のswapによって新たにストックに入った要素をまた目標の位置に挿入……）していくと、可能となる。

Python3

def solve(n):
    print(2)
    roller = list(range(2, n)) + [1, n]
    print(*roller)
    swapper = list(range(1, n - 1)) + [n, n - 1]
    print(*swapper)

    def roll(aaa):
        return aaa[1:-1] + [aaa[0], aaa[-1]]

    def swap(aaa):
        aaa[-2], aaa[-1] = aaa[-1], aaa[-2]
        return aaa

    qqq = list(map(int, input().split()))
    bbb = [0] * n
    for i, q in enumerate(qqq):
        bbb[q - 1] = i

    ans = []
    if bbb.index(0) == n - 1:
        ans.append(2)
        bbb = swap(bbb)

    for k in range(1, n - 1):
        i = bbb.index(k)

        if i < n - 1 and bbb[(i - 1) % (n - 1)] == k - 1:
            continue

        if i < n - 1:
            while bbb[-2] != k:
                ans.append(1)
                bbb = roll(bbb)
            ans.append(2)
            bbb = swap(bbb)

        while bbb[-3] != k - 1:
            ans.append(1)
            bbb = roll(bbb)
        ans.append(2)
        bbb = swap(bbb)

    while bbb[0] != 0:
        ans.append(1)
        bbb = roll(bbb)

    print(len(ans), *ans)


n = int(input())
solve(n)

D - I like Increasing

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。
• ここで、整数列 $x=(x_1,x_2,\dots,x_k)$ に対して、$x$ のスコアを $x_i \lt x_{i+1}$ を満たす $i$ の個数と定めます。
• 以下のクエリを $Q$ 回処理してください。
  • $1 \le l \le r \le N$ を満たす正整数 $l,r$ が与えられる。$X = (P_l,P_{l+1},\dots,P_r)$ に対して以下の問題を解け。
    • $X$ の空でない部分列におけるスコアの最大値を $M$ とする。
    • $X$ の空でない部分列のうち、スコアが $M$ であるものの長さの最小値を求めよ。

• $1 \le N,Q \le 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列
• $1 \le l \le r \le N$
• 入力は全て整数

スコアは、最長増加部分列（LIS）と似ているようで、意味合いは全く異なる。
LISはその定義上、1回も減少できないが、 本問題のスコアでは、連続した増加列を含めるためなら何回でも減少することができる。

「$M$ を最大化し長さを最小化する上で、$P_i$ を採用するなら、次に採用すべきは $P_j$ である」という関係性 $i→j$ が クエリに依らず決まっているとすると、関係性を $2$ 個、$4$ 個、$8$ 個、、、辿った先を前計算しておけば、 クエリの答えはダブリングで導ける。

、、、という解法が直感的に思いついたものの、 本番では関係性がクエリに依らない証明と、どういう法則で構築すれば良いかを詰め切れなかった。

公式Editorialによると、以下のように考えるとよい。

• $P$ を、連続した減少部分列に分解する。
  • $i$ 番目の減少部分列をグループ $i$ と呼ぶことにする。
  • $P_i$ が属するグループを、$G_i$ と表す。

  •                           group   1    2   3     4      5
    P  3 1 4 5 9 7 6 8 2   →       [3 1] [4] [5] [9 7 6] [8 2]
                                  G  1 1   2   3   4 4 4   5 5

• $P_i$ からは、以下の法則で辺を張る（関係性を決める）
  • $G_{i}$ が最後のグループなら、次に採用すべき $j$ は無い
  • グループ $G_{i}+1$ の内、$P_i$ より大きい要素が存在すれば、そのうち最小の要素へ辺を張る
  • 存在しなければ、$G_{i}$ の末尾要素へ辺を張る。

このように辺を張ってよい理由は、以下の通り。

まずスコアの最大値から考えると、

• 同じグループの中から複数採用して、スコアに貢献することは無い。
• 一方、グループ間を移動するときは、適切なペアを隣接させれば必ず $1$ 増加させることができる。
• よって、スコアの最大値は（グループ数$-1$）である。

よって、「グループから最低1要素ずつ選ぶ」「グループ間をまたぐときは必ず増加させるようにする」 というルールで採用要素を決めていけば、最大値を達成できる。

グループ $i$ で採用した要素 $p$ より大きい要素が $i+1$ にあれば次はそれを採用すればよいが、 無ければ同じグループ $i$ 内で（スコアには貢献しないが）$p$ より小さい要素を追加で採用して、 値を一旦“下げる”必要がある。
長さを最小化する上では、この「値を下げるために同じグループから追加で採用する回数」を最小化したいということになる。

この時、最後に採用した値が小さいほど、以降のグループ $i+1,i+2,...$ で値を下げずに採用できる範囲が増えるので、 なるべく小さい値を採用するように保って損しない。

よって、上記の辺の張り方が最適だと言える。

$P$ 全体ではなくクエリ $l,r$ に対して求めるときも同様の法則で $l$ が属するグループから $r$ が属するグループまでを1つずつ移動していけばよい。

これで、ダブリングによって答えが求められる。

ただし、端の処理には少し注意を要する。

• $G_l=G_r$ ならスコアは $0$。
  • 「空でない部分列」という条件があるため、答えは $1$
• そうでない場合、スタート地点は $l$ ではなく「$G_l$ の末尾要素」。（採用要素の末尾をなるべく小さく保つため）
• また、ダブリングのゴールは「$r$ を超えないところまで」でなく「$r-1$ を超えないところまで」とする。
  • その上で、到達頂点を $t$ とし、$G_t \lt G_r$ なら $+1$ する。
  • 「$r$ を超えないところまで」とした場合、$t→r$ が「同一グループだが値を一旦下げるための辺」だった時、$r$ を入れる意味は無いのに答えに入ってしまう

Python3

from bisect import bisect


def solve(n, q, ppp, queries):
    group_id = [-1] * n
    group_id[0] = gid = 0
    cur_group = [-ppp[0]]
    groups = [cur_group]
    first_idx_for_group = [0]
    for i in range(1, n):
        p = ppp[i]
        if -cur_group[-1] < p:
            cur_group = [-p]
            groups.append(cur_group)
            first_idx_for_group.append(i)
            gid += 1
        else:
            cur_group.append(-p)
        group_id[i] = gid
    last_gid = gid

    nexts = [n] * n
    for i in range(n):
        p = ppp[i]
        g = group_id[i]
        if g == last_gid:
            break
        nxt_grp = groups[g + 1]
        j = bisect(nxt_grp, -p)
        if j == 0:
            nexts[i] = first_idx_for_group[g + 1] - 1
        else:
            nexts[i] = first_idx_for_group[g + 1] + j - 1

    doubling = [nexts + [n]]
    dbl_cnt = n.bit_length()
    for _ in range(dbl_cnt - 1):
        prev = doubling[-1]
        doubling.append([prev[prev[i]] for i in range(n + 1)])

    buf = []
    for l, r in queries:
        l -= 1
        r -= 1
        sg = group_id[l]
        tg = group_id[r]
        if sg == tg:
            buf.append(1)
            continue
        v = first_idx_for_group[sg + 1] - 1
        ans = 1
        for di in range(dbl_cnt - 1, -1, -1):
            if doubling[di][v] < r:
                ans += 1 << di
                v = doubling[di][v]
        if group_id[v] != tg:
            ans += 1
        buf.append(ans)

    return buf


n, q = map(int, input().split())
ppp = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, ppp, queries)
print('\n'.join(map(str, ans)))

E - Reverse and Reverse

• $(1,2,\dots,N)$ の順列 $p=(p_1,p_2,\dots,p_N)$ と正整数 $M$ に対して、以下の問題の答えを $f(p,M)$ と置きます。

• $p$ に対して以下の操作を $M$ 回行います。
  • $1 \le i \le N-1$ を満たす整数 $i$ を選び、$(p_1,p_2,\dots,p_i)$ と $(p_{i+1},p_{i+2},\dots,p_N)$ をそれぞれ反転する。形式的には、$p$ を $(p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1})$ に置き換える。
• 操作列としてあり得るものは $(N-1)^M$ 通りありますが、その全てに対する「$M$ 回の操作終了後の $p$ の転倒数」の総和を $998244353$ で割った余りを求めてください。

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。
• 以下のクエリを $Q$ 回処理してください。
  • $1 \le x \le N-1$ を満たす整数 $x$ と正整数 $K$ が与えられる。$P_x,P_{x+1}$ を swap する。その後、$f(P,K)$ を求めよ。

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列
• $1 \le x \le N-1$
• $1 \le K \le 10^9$
• 入力は全て整数

まず、$f(p,M)$ で行われるような操作は、 実際にやってみると「並びを反転させ、いくつか巡回シフトする」という操作に相当することが分かる。

1 2 3 4 5 6   →   3 2 1 6 5 4
~~~~~ ~~~~~

特に、偶数回操作すると並びは元に戻り、単に「$p$ をいくつか巡回シフト」した数列となる。
つまり、操作列自体はたくさんあっても、結果の種類数自体は非常に少ない。

$M$ が偶数として、$k=0,1,...,N-1$ のそれぞれに対し 「$(N-1)^M$ 通りの操作列のうち結果が $p$ を $k$ 回巡回シフトしたものと一致するのはいくつあるか？」を知りたい。

（また同様に、$M$ が奇数として、「$p$ を反転 + $k$ 回巡回シフトしたものと一致する個数」も）

これは、小さい $N,M$ で愚直に試すと、以下のようになる。

N=5
     k  0  1  2  3  4
M=2:    4  3  3  3  3
M=4:   52 51 51 51 51

M=1:    0  1  1  1  1
M=3:   12 13 13 13 13

• $M$ 偶数の時
  • $d=\dfrac{(N-1)^M-1}{N}$ として、$k=0$ のみ $d+1$、他は $d$
• $M$ 奇数の時
  • $d=\dfrac{(N-1)^M+1}{N}$ として、$k=0$ のみ $d-1$、他は $d$

という法則が見える。（証明は 公式Editorial参照）

つまり、以下の2つが分かれば、$N,M$ と合わせて答えが求められる。

• $I_0$: シフトしてない $P$ の転倒数
• $I_S$: $P$ を $0,1,2,...,N-1$ 回巡回シフトした数列それぞれの転倒数の総和

後は、「$x_i,x_{i+1}$ をswap」というクエリの操作によって生じる変化を、適切に $I_0,I_S$ に反映できればよい。

$I_0$ は、swapが必ず隣接であることを活かして、各 $i$ に対し 「$j \lt i$ かつ $P_j \gt P_i$ を満たす $j$ の個数」などを管理しておくと、比較的簡単に差分更新できる。

一方、$I_S$ はなかなか上手くいかなかった。
ややトリッキーだが、以下のような方法で管理できる。以降、$P$ を $(0,1,...,N-1)$ の順列であるとする。

まず、$I_S$ を以下のように捉える。

• $P$ を1つだけ左巡回シフトした数列の、$P$ からの転倒数の差分は、次のように計算できる。
  • $P_0$ を左端から右端に移動させる
    • $P_0$ より小さい要素とのペアは、今まで転倒数に寄与していたのがしなくなる
    • $P_0$ より大きい要素とのペアは、今まで転倒数に寄与していなかったのがするようになる
  • 差分は $P_0$ の値によってのみ決まり、$N-1-2P_0$ である。
• 「$i$ 回目の左巡回シフトで発生する、1つ前との転倒数の差分」を、$c=(c_1,...,c_{N-1})$ とする。
  • $c_i=N-1-2P_{i-1}$ である。
• $c$ の累積和を $d=(d_1,...,d_{N-1})$ とする。
  • $P$ を $i$ 回巡回シフトした数列の転倒数は $I_0+d_i$ である。
• $d$ の総和を $D$ とする。
• $I_S=D+I_0 \times N$ である。

このように考えると、$I_0$ は適切に更新できているとして、$D$ の差分が分かればよいことになる。

$x$ と、$y=x+1$ のswapでは、

左巡回シフト時の転倒数差分の列
c  ......,    cx,      cy,      ...
                  ↓
c  ......,    cy,      cx,      ...

その累積和
d  ..., ○,  ○+cx,  ○+cx+cy,  ...
             ↓
d  ..., ○,  ○+cy,  ○+cy+cx,  ...

のような変化が発生し、他は変化しない。よって、$c_y-c_x = 2(P_x-P_y)$ だけ $D$ が増加すると計算できる。

捉え方を変えるだけで、意外と簡単に $O(1)$ で差分計算できることが分かる。

Python3

from atcoder.fenwicktree import FenwickTree


def solve(n, q, ppp, queries):
    MOD = 998244353

    fwt = FenwickTree(n)
    original_inversion = 0
    cur_lap_inversion_diff = 0  # 元の順列の転倒数に対し、それを何回かシフトした状態の転倒数の差分
    total_lap_inversion_diff = 0  # ↑の1周通しての合計
    count_hi = []

    for i in range(n):
        p = ppp[i] - 1
        hi = i - fwt.sum(0, p)
        fwt.add(p, 1)
        count_hi.append(hi)
        original_inversion += hi
        cur_lap_inversion_diff += n - 1 - p * 2
        total_lap_inversion_diff += cur_lap_inversion_diff

    buf = []
    INV_N = pow(n, -1, MOD)
    ALL_PAIR = (n * (n - 1) // 2) % MOD
    for x, k in queries:
        x -= 1
        y = x + 1

        cx = count_hi[x]
        cy = count_hi[y]
        total_lap_inversion_diff += 2 * (ppp[x] - ppp[y])
        if ppp[x] < ppp[y]:
            original_inversion += 1
            cx += 1
        else:
            original_inversion -= 1
            cy -= 1

        lap_inversion = total_lap_inversion_diff + original_inversion * n

        ppp[x], ppp[y] = ppp[y], ppp[x]
        count_hi[x], count_hi[y] = cy, cx

        if k % 2 == 0:
            lap_count = (pow(n - 1, k, MOD) - 1) * INV_N % MOD
            ans = (lap_inversion * lap_count + original_inversion) % MOD
        else:
            oi = ALL_PAIR - original_inversion
            li = (ALL_PAIR * n) - lap_inversion
            lap_count = (pow(n - 1, k, MOD) + 1) * INV_N % MOD
            ans = (li * lap_count - oi) % MOD
        buf.append(ans)

    return buf


n, q = map(int, input().split())
ppp = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, ppp, queries)
print('\n'.join(map(str, ans)))