_kiran_iitm | Logout
You have +357! Wow!
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 1098 (Div. 2)
E1. Amanojaku and Sequence (Easy Version) Contest is running
time limit per test: 4 seconds
00:59:03
memory limit per test: 512 megabytes
Contestant
Tinkerbell of Inequality
— Taboo Japan Disentanglement
This is the easy version of the problem. The difference between the versions is that in
this version, q = 1 and op = 2. You can hack only if you solved all versions of this
→ Submit?
problem.
For a sequence s , let |s| denote its length. Language: GNU G++23 14.2 (64 bit, msys2
Choose
For a non-negative integer sequence c, define f (c) as the sum of the squares of its prefix file:
Choose File No file chosen
sums: Be careful: there is 50 points penalty for
submission which fails the pretests or
|c| i
2
resubmission (except failure on the first test,
denial of judgement or similar verdicts).
f (c) = ∑ (∑ cj ) .
"Passed pretests" submission verdict doesn't
i=1 j=1 guarantee that the solution is absolutely
correct and it will pass system tests.
Now define g(b, m) as follows.
Submit
Let b be an integer sequence such that bi ≥ −1 for every i , and let m be a non-negative
integer. A non-negative integer sequence c is called valid for (b, m) if all of the following
conditions hold: → Score table
|c| = |b| ; Score
Problem A 350
|c|
∑ ci = m;
i=1
for every 1 ≤ i ≤ |b| , if bi ≥ 0 , then ci = bi ; otherwise, if bi = −1 , then ci may be Problem B 525
any non-negative integer. Problem C1 1050
The value g(b, m) is defined as the sum of f (c) over all valid sequences c for (b, m) . If Problem C2 700
there is no such sequence, then g(b, m) = 0. Problem D 1750
You are given an array a of length n, where ai ≥ −1 , and q queries of the following one Problem E1 1400
type: Problem E2 1050
Problem F 2450
Given three integers l, r , and m, compute g([al , al+1 , … , ar ], m) modulo
998 244 353 , where [al , al+1 , … , ar ] denotes the subarray of a from position l to
∗ Successful hack 100
position r . Unsuccessful hack -50
Unsuccessful submission -50
∗
An array a is a subarray of an array b if a can be obtained from b by the deletion of several (possibly, zero or
all) elements from the beginning and several (possibly, zero or all) elements from the end. Resubmission -50
* If you solve problem on 01:15 from the first attempt
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
4
1 ≤ t ≤ 10 ). The description of the test cases follows.
For each test case, the first line contains two integers n and q (1
5
≤ n ≤ 3 ⋅ 10 ,q = 1 ).
The second line contains n integers a1 , a2 , … , an (−1 ≤ ai ≤ 10
6
).
Then q lines follow. Each line describes a query in the following format. The first integer op is
2.
2lrm : compute g([al , al+1 , … , ar ], m) modulo 998 244 353 (1 ≤ l ≤ r ≤ n ,
6
0 ≤ m ≤ 10 ).
It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 105 .
Output
For each test case, for every query of the second type, output the value of
g([al , al+1 , … , ar ], m) modulo 998 244 353 on a line.
Example
input Copy
10
5 1
4 -1 7 6 -1
2 2 2 2
5 1
4 -1 8 6 -1
2 3 3 0
5 1
4 -1 8 6 -1
2 4 5 8
5 1
4 -1 8 6 7
2 3 5 21
5 1
4 -1 8 6 7
2 3 5 22
4 1
-1 -1 -1 -1
2 1 1 4
4 1
-1 -1 -1 -1
2 1 2 5
4 1
-1 -1 -1 -1
2 1 3 6
4 1
-1 -1 -1 -1
2 1 4 7
4 1
-1 -1 3 -1
2 1 4 5
output Copy
4
0
100
701
0
16
205
1736
12180
286
Note
In the first test case:
l = r = 2 and m = 2 . The subarray is [a2 ] = [−1] , so the only valid sequence is c = [2] .
2
Thus, the answer is 2 = 4 .
In the third test case:
l = 4 ,r = 5 , and m = 8. The subarray is [a4 , a5 ] = [6, −1]. Since c1 is fixed at 6 and
c1 + c2 = m , we obtain c = [6, 2]. The prefix sums are 6 and 8, giving
2 2
f (c) = 6 + (6 + 2) = 36 + 64 = 100.
In the seventh test case:
The subarray is [a1 , a2 ] = [−1, −1]. All valid sequences satisfy c1 + c2 = 5 with
c1 , c2 ≥ 0, namely [0, 5], [1, 4], … , [5, 0] . Summing f (c) over all such sequences yields
205.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/16/2026 21:20:23UTC+5.5 (l1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by