No.3571 Sigma Problems Problem
Introduction
This problem was rejected from The 2nd Iwai Seijin Anthology Programming Contest Div.1.
kazuppa instead set Make 81181819 with only 0,1,or 8, so please check that one out as well.
Problem Statement
Consider the following problem (hereafter called the sub-problem).
You are given an integer sequence $A$ of length $N$ and a positive integer $M$. All elements of $A$ are at least $0$ and less than $M$.
Also, define $f(x,y)=(x+y)\bmod M$.
Find $\displaystyle\sum_{i=1}^{N-1} \displaystyle\sum_{j=i+1}^{N}f(A_i,A_j)$.
You are given positive integers $N,M$.
There are $M^N$ sequences $A$ satisfying the conditions. Find the sum of the answers to all of these sub-problems, modulo $998244353$ (hereafter, this problem is called the main problem).
You are given $T$ test cases; solve all of them.
Input
$T$ $Testcase_1$ $Testcase_2$ $\vdots$ $Testcase_T$Each test case is given in the following format.
$N\ M$
Constraints
- $1\leq T\leq 10^5$
- $1\leq N,M\leq 10^{18}$
- All input values are integers.
Output
On the $i$-th line, output the answer to the $i$-th test case.
Print a newline at the end.Sample
Sample 1
Input
5 3 2 8 8 169 231 411 892 1000000000000000 1000000000000000
Output
12 645922815 435837943 117185670 917198649
Let us explain test case 1.
For example, when $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$
Thus, the answer to this sub-problem is $1+0+1=2$.
Continuing in the same way, the answer to the main problem is $0+2+2+2+2+2+2+0=12$.
Note that the answer to the sub-problem is not taken modulo $M$. Also note that the answer to the main problem should be output modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kazuppa
ゆにたりー卿
ぽえ