AtCoder Regular Contest 106 D,F問題メモ

AtCoder Regular Contest 106

D - Powers

問題

長さ $N$ の正整数列 $A_1,A_2,...,A_N$ と整数 $K$ が与えられる
各 $X=1,2,...,K$ について、 $\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X$ を $\mod{998244353}$ で求めよ
$2 \le N \le 2 \times 10^5$
$1 \le K \le 300$
$1 \le A_i \le 10^8$

解法

二項係数を使った式変形。結構このレベル帯では頻出。（そして毎度対応できない自分も自分だが）

公式解説の写経になってしまうが。

今回の形の2つのシグマは、「自分自身とはペアにしない、順番を入れ替えただけのペアは重複しない」ことを示すが、これを「自分自身とペアにしてもよく、順番を入れ替えたペアも2回数える」とすることで、上手くまとめる式が見えてくることがある。（自分自身とのペアは、後で引く）

$\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X = \frac{1}{2}(\sum_{L=1}^{N} \sum_{R=1}^{N} (A_L+A_R)^X - \sum_{i=1}^{N}(2A_i)^X)$

2つの項の足し算の累乗は、展開すると係数が二項係数になる（そのまんま）。さらに階乗の形に展開することで、添え字 $k$ が上手いこと揃う形になる。

$\begin{eqnarray} (A_L+A_R)^X &=& \sum_{k=0}^{X} {}_{X}C_{k}A_L^kA_R^{X-k} \\ &=& \sum_{k=0}^{X} X! \frac{A_L^k}{k!} \frac{A_R^{X-k}}{(X-k)!} \end{eqnarray}$

これを先ほどの式に代入すると、総和を取る順番を入れ替えることができる。

$\begin{eqnarray} \sum_{L=1}^{N} \sum_{R=1}^{N} (A_L+A_R)^X &=& \sum_{L=1}^{N} \sum_{R=1}^{N} \sum_{k=0}^{X} X! \frac{A_L^k}{k!} \frac{A_R^{X-k}}{(X-k)!} \\ &=& X! \sum_{k=0}^{X} (\sum_{L=1}^{N} \frac{A_L^k}{k!}) (\sum_{R=1}^{N} \frac{A_R^{X-k}}{(X-k)!}) \end{eqnarray}$

なので、 $\displaystyle \sum_{i=1}^{N} \frac{A_i^k}{k!}$ を $k=0～K$ まで前計算しておけばよい。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(inp):
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret
 
    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions
 
    k = inp[1]
    aaa = inp[2:]
    MOD = 998244353
 
    factorials, inversions = prepare_factorials(k, MOD)
 
    sums = np.zeros(k + 1, np.int64)
    for a in aaa:
        p = 1
        for i in range(k + 1):
            sums[i] += p
            p = p * a % MOD
 
    sums = sums % MOD * inversions % MOD
 
    buf = []
    for x in range(1, k + 1):
        ans = 0
        for r in range(x + 1):
            ans = (ans + sums[r] * sums[x - r]) % MOD
        ans = (ans - mod_pow(2, x, MOD) * sums[x]) % MOD * factorials[x] % MOD * inversions[2] % MOD
        buf.append(ans)
 
    return buf
 
 
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()
 
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)
 
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

            

        
      

E - Medals

問題

例

解法

Python3

F - Figures

問題

$N$ 個のフィギュアのパーツを $N-1$ 本の接続部品で繋いで連結にする
パーツ $i$ には穴が $d_i$ 個空いている
- 接続部品は、両端を異なるパーツの穴に差し込むことで、2つのパーツを繋げる役割を持つ
- 1つの穴には1つの接続部品しか差し込めない
パーツおよびパーツの穴はそれぞれ区別する、接続部品は区別しない
完成形が何種類あるか、 $\mod{998244353}$ で答えよ
$2 \le N \le 2 \times 10^5$
$1 \le d_i \lt 998244353$

解法

まず、辺 $N-1$ を繋ぐには $2(N-1)$ 個の穴が必要なので、 $S=d_1+d_2+...+d_N \lt 2(N-1)$ なら不可能。0通り。

以下、 $S \ge 2(N-1)$ でとりあえず完成させることはできるとする。

ケイリーの公式というのがあって、区別できる $N$ 頂点の木が何種類できるかは $N^{N-2}$ となるらしい。

今回の問題はそれを直接使うわけでは無いが、Wikiにある導出の方法が参考になる。（「double counting法を用いた証明」の部分）

全体を連結にして2つ以上の成分に分かれたりしないように数えあげるには、「あるパーツを1つ選び、それを自身の連結成分とは異なる穴に接続する」ことを繰り返すとよい。

その際、「自身を繋ぎに行くための穴」を1つ確保しておかないと、たとえば穴が1つしか無いパーツなど、うっかりそこに他のパーツを繋がれてしまっては困る。
なので、まずは各パーツに1つ、そのような特殊穴を決めておこうとなる。特殊穴の決め方は $d_1 \times d_2 \times ... \times d_N$ 。

このように繋いでしまっては、連結にできなくなる
①  ①  ②    →    ①--①  ②

自身を繋ぎにいく特殊穴を1つ確保して、他から繋がれる穴は特殊穴以外から選ぶ
,   ,   ,           ,   ,
⓪  ⓪  ①    →    ⓪  ①--⓪

特殊穴以外の穴を「普通穴」とする。

まず、初期状態で各パーツバラバラなので特殊穴（＝連結成分）は $N$ 個、普通穴は $S-N$ 個ある。

ここで、繋ぎに行くパーツから先に固定してしまうと上手くいかない。
相方となる、「そのパーツが含まれる連結成分以外の普通穴の個数」がパーツによって変わるので、まとめての計算ができない。

しかし、繋がれる普通穴から先に固定すると「そこに繋ぎに行く特殊穴」は、その時の連結成分の数から自身(1個)を除いたものなので、どの普通穴に対しても同じとなる。

固定する方を変えるだけで計算が可能になるのは不思議不思議。

ともかく、 $i$ 回の接続操作を行った後、 $i+1$ 回目の操作では、残る普通穴は $S-N-i$ 個、特殊穴のうち選ばれた普通穴が含まれる連結成分以外に存在するものは $N-1-i$ 個となる。
つまり、繋ぎ方は $(S-N-i)(N-1-i)$ 通りとなる。

$N-2$ 回の接続を行ったら、残っている連結成分は2つなので、その特殊穴同士を結んで完成。
（この、最後の2つになるまで接続するという操作、いまいち腑に落ちてない。最後の1つまで接続したら使われない特殊穴が余ることになり、穴の数がギリギリだった場合に破綻するとか、他の場合に上手くいかないことはわかるんだけど、2つまで接続して最後を特殊穴同士で繋いで上手く数え上げられている、という感覚が掴めてない……）

ここから、重複を除いていく。

この数え上げ方では、辺（接続部品）も区別された場合の数となっている。（1番目の接続に使用した辺、2番目の接続に使用した辺、…）
そのため、 $(N-2)!$ で割る。

また、特殊穴の決め方が違う場合でも、同じものが出来上がる場合がある。

○→◎↔○←○    A←B: Bの特殊穴をAの普通穴に繋ぎにいった
    ↑            A↔B: 最後に特殊穴同士を繋いだ
    ○
                  左の2つの完成形が（図では表現し切れていないが、穴も含めて）同じとする。
○↔◎←○←○    ◎で示した頂点の特殊穴として、
    ↑            上図は右の頂点と、下図は左の頂点との接続に使用する穴が選ばれ、
    ○            それぞれそこが最後に接続された形。

完成形が同じだが特殊穴の選び方が異なる、というのは「最後に接続された辺がどれか」に依存する。それが決まれば、グラフの作り方からして、最後の辺を中心として各パーツ、それに近い方の穴が特殊穴となるので、特殊穴の選ばれ方は一意に決まる。

最後の辺がどれか、の場合の数は辺の数だけ、つまり $N-1$ 個ある。これでもまた割る。

これで、重複が除けた。

式でまとめると、 $\displaystyle d_1d_2 ... d_N \frac{\prod_{i=0}^{N-3}(N-1-i)(S-N-i)}{(N-1)!}$ となる。

Python3