No.3571 Sigma Problems Problem
タグ : / 解いたユーザー数 27
作問者 :
kazuppa
/ テスター :
ゆにたりー卿
👑 
loop0919
ぽえ
はじめに
この問題は第2回 岩井星人アンソロジープログラミングコンテスト Div.1にて没になった問題です。
kazuppaからは代わりにMake 81181819 with only 0,1,or 8を出題しましたので、そちらもよろしくお願いします。
問題文
以下の問題について考えます（以後、この問題を小問と呼びます）。
長さ $N$ の整数列 $A$ および正整数 $M$ が与えられます。ただし、 $A$ の要素は全て $0$ 以上 $M$ 未満です。
また、 $f(x,y)=(x+y)\bmod M$ と定義します。
$\displaystyle\sum_{i=1}^{N-1} \displaystyle\sum_{j=i+1}^{N}f(A_i,A_j)$ を求めてください。
正整数 $N,M$ が与えられます。
このとき、条件を満たす $A$ は全部で $M^N$ 個存在します。そのすべての小問の答えの総和を $998244353$ で割った余りを求めてください（以降、この問題を本問と呼びます）。
$T$ 個のテストケースが与えられるので、全てについて解を求めてください。
入力
$T$ $Testcase_1$ $Testcase_2$ $\vdots$ $Testcase_T$また、各テストケースは次の形で渡されます。
$N\ M$
制約
- $1\leq T\leq 10^5$
- $1\leq N,M\leq 10^{18}$
- 入力は全て整数
出力
$i$ 行目には $i$ 番目のテストケースの答えを出力してください。
最後に改行してください。サンプル
サンプル1
入力
5 3 2 8 8 169 231 411 892 1000000000000000 1000000000000000
出力
12 645922815 435837943 117185670 917198649
テストケース1の説明をします。
たとえば、 $A=(1,0,1)$ のとき、
$f(A_1,A_2)=(1+0)\bmod 2=1$
$f(A_1,A_3)=(1+1)\bmod 2=0$
$f(A_2,A_3)=(0+1)\bmod 2=1$
よって、この小問の答えは $1+0+1=2$ となります。
同様にして考えていくと、本問の答えは $0+2+2+2+2+2+2+0=12$ となります。
小問の答えは $M$ で割らないことに注意してください。また、本問の答えは $998244353$ で割った余りで出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。