CF1789E.Serval and Music Game
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Serval loves playing music games. He meets a problem when playing music games, and he leaves it for you to solve.
You are given n positive integers s1<s2<…<sn . f(x) is defined as the number of i ( 1≤i≤n ) that exist non-negative integers pi,qi such that:
si=pi⌊xsn⌋+qi⌈xsn⌉
Find out ∑x=1snx⋅f(x) modulo 998244353 .
As a reminder, ⌊x⌋ denotes the maximal integer that is no greater than x , and ⌈x⌉ denotes the minimal integer that is no less than x.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
The first line of each test cases contains a single integer n ( 1≤n≤106 ).
The second line of each test case contains n positive integers s1,s2,…,sn ( 1≤s1<s2<…<sn≤107 ).
It is guaranteed that the sum of n over all test cases does not exceed 106 , and the sum of sn does not exceed 107 .
输出格式
For each test case, print a single integer in a single line — the sum of x⋅f(x) over all possible x modulo 998244353 .
输入输出样例
输入#1
4 3 1 2 4 4 1 2 7 9 4 344208 591000 4779956 5403429 5 1633 1661 1741 2134 2221
输出#1
26 158 758737625 12334970
说明/提示
For the first test case, sn=4 , f(x) are calculated as followings:
- f(1)=1
- ⌊1sn⌋=4 , ⌈1sn⌉=4 .
- It can be shown that such p1,p2 and q1,q2 that satisfy the conditions don't exist.
- Let p3=1 and q3=0 , then s3=p3⋅⌊1sn⌋+q3⋅⌈1sn⌉=1⋅4+0⋅4=4 .
- f(2)=2
- ⌊2sn⌋=2 , ⌈2sn⌉=2 .
- It can be shown that such p1 and q1 that satisfy the conditions don't exist.
- Let p2=1 and q2=0 , then s2=p2⋅⌊2sn⌋+q2⋅⌈2sn⌉=1⋅2+0⋅2=2 .
- Let p3=0 and q3=2 , then s3=p3⋅⌊2sn⌋+q3⋅⌈2sn⌉=0⋅2+2⋅2=4 .
- f(3)=3
- ⌊3sn⌋=1 , ⌈3sn⌉=2 .
- Let p1=1 and q1=0 , then s1=p1⋅⌊3sn⌋+q1⋅⌈3sn⌉=1⋅1+0⋅2=1 .
- Let p2=0 and q2=1 , then s2=p2⋅⌊3sn⌋+q2⋅⌈3sn⌉=0⋅1+1⋅2=2 .
- Let p3=0 and q3=2 , then s3=p3⋅⌊3sn⌋+q3⋅⌈3sn⌉=0⋅1+2⋅2=4 .
- f(4)=3
- ⌊4sn⌋=1 , ⌈4sn⌉=1 .
- Let p1=1 and q1=0 , then s1=p1⋅⌊4sn⌋+q1⋅⌈4sn⌉=1⋅1+0⋅1=1 .
- Let p2=1 and q2=1 , then s2=p2⋅⌊4sn⌋+q2⋅⌈4sn⌉=1⋅1+1⋅1=2 .
- Let p3=2 and q3=2 , then s3=p3⋅⌊4sn⌋+q3⋅⌈4sn⌉=2⋅1+2⋅1=4 .
Therefore, the answer is ∑x=14x⋅f(x)=1⋅1+2⋅2+3⋅3+4⋅3=26 .
For the second test case:
- f(1)=f(2)=f(3)=1
- f(4)=3
- f(5)=f(6)=f(7)=f(8)=f(9)=4
For example, when x=3 we have f(3)=1 because there exist p4 and q4 :
9=1⋅⌊39⌋+2⋅⌈39⌉
It can be shown that it is impossible to find p1,p2,p3 and q1,q2,q3 that satisfy the conditions.
When x=5 we have f(5)=4 because there exist pi and qi as followings:
1=1⋅⌊59⌋+0⋅⌈59⌉
2=0⋅⌊59⌋+1⋅⌈59⌉
7=3⋅⌊59⌋+2⋅⌈59⌉
9=3⋅⌊59⌋+3⋅⌈59⌉
Therefore, the answer is ∑x=19x⋅f(x)=158.