/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 1200 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) に対し、以下で f(A) を定めます。
- 1 \le i < j < k \le N を満たす整数の組 (i,j,k) に対する A_iA_j + A_k の最大値
長さ N かつ全要素が 1 以上 M 以下である正整数列 A のうち、f(A) \le K となるものの個数を 998244353 で割った余りを求めてください。
制約
- 3 \le N \le 10^9
- 1 \le M,K \le 10^4
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
3 5 4
出力例 1
9
条件を満たす数列は (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(2,1,2),(1,3,1),(3,1,1) の 9 個です。
入力例 2
4 5 7
出力例 2
66
入力例 3
123 456 789
出力例 3
436486661
入力例 4
1000000000 10000 10000
出力例 4
855626126
Score : 1200 points
Problem Statement
For a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N), define f(A) as follows:
- The maximum value of A_iA_j + A_k over all triples of integers (i,j,k) satisfying 1 \le i < j < k \le N.
Find the number, modulo 998244353, of length-N sequences A of positive integers with all elements between 1 and M, inclusive, such that f(A) \le K.
Constraints
- 3 \le N \le 10^9
- 1 \le M,K \le 10^4
Input
The input is given from Standard Input in the following format:
N M K
Output
Output the answer.
Sample Input 1
3 5 4
Sample Output 1
9
The sequences satisfying the condition are (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(2,1,2),(1,3,1),(3,1,1), which is nine sequences.
Sample Input 2
4 5 7
Sample Output 2
66
Sample Input 3
123 456 789
Sample Output 3
436486661
Sample Input 4
1000000000 10000 10000
Sample Output 4
855626126