Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。
- N 桁の正整数である。
- X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1
制約
- N は整数
- 2 \le N \le 10^6
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
4
出力例 1
203
4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。
入力例 2
2
出力例 2
25
入力例 3
1000000
出力例 3
248860093
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.
- X is an N-digit positive integer.
- Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.
Constraints
- N is an integer.
- 2 \le N \le 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
4
Sample Output 1
203
Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.
Sample Input 2
2
Sample Output 2
25
Sample Input 3
1000000
Sample Output 3
248860093
Be sure to find the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます。
以下の条件を満たす長さ N の整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するならば一つ出力してください。
- 各 i=1,2,\ldots,N に対して L_i\leq X_i\leq R_i
- \displaystyle \sum_{i=1}^N X_i=0
制約
- 1\leq N\leq 2\times 10^5
- -10^9\leq L_i\leq R_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
存在しない場合は No を出力せよ。存在する場合は条件を満たす整数列 X を以下の形式で出力せよ。
Yes X_1 X_2 \ldots X_N
答えが複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 3 5 -4 1 -2 3
出力例 1
Yes 4 -3 -1
数列 X=(4,-3,-1) は問題の条件をすべて満たします。ほかにも (3,-3,0) や (5,-4,-1) などが条件を満たします。
入力例 2
3 1 2 1 2 1 2
出力例 2
No
条件を満たす整数列 X は存在しません。
入力例 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
出力例 3
Yes -66 -57 31 -6 89 9
Score : 350 points
Problem Statement
You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).
Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.
- L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
- \displaystyle \sum_{i=1}^N X_i = 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq L_i \leq R_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
If no solution exists, print No. Otherwise, print an integer sequence X that satisfies the conditions in the following format:
Yes X_1 X_2 \ldots X_N
If multiple solutions exist, any of them will be considered correct.
Sample Input 1
3 3 5 -4 1 -2 3
Sample Output 1
Yes 4 -3 -1
The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).
Sample Input 2
3 1 2 1 2 1 2
Sample Output 2
No
No sequence X satisfies the conditions.
Sample Input 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
Sample Output 3
Yes -66 -57 31 -6 89 9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
空でない文字列 S が与えられます。S の各文字は (, ), ? のいずれかです。
S に含まれる ? の個数を x とすると、? を ( あるいは ) に置き換えて新しい文字列を作る方法は 2^x 通りありますが、このうち新しくできた文字列が括弧列となるような置き換え方の数を 998244353 で割った余りを求めてください。
ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。
- 空文字列
- ある括弧列 A が存在して、
(, A,)をこの順に連結した文字列 - ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列
制約
- S は長さ 3000 以下の
(,),?からなる空でない文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
(???(?
出力例 1
2
S を ()()() あるいは (())() に置き換えると括弧列となります。
他の置き換え方で新しくできた文字列が括弧列となることはないので、2 を出力します。
入力例 2
)))))
出力例 2
0
入力例 3
??????????????(????????(??????)?????????(?(??)
出力例 3
603032273
998244353 で割った余りを出力してください。
Score : 400 points
Problem Statement
You are given a non-empty string S consisting of (, ), and ?.
There are 2^x ways to obtain a new string by replacing each ? in S with ( and ), where x is the number of occurrences of ? in S. Among them, find the number, modulo 998244353, of ways that yield a parenthesis string.
A string is said to be a parenthesis string if one of the following conditions is satisfied.
- It is an empty string.
- It is a concatenation of
(, A, and), for some parenthesis string A. - It is a concatenation of A and B, for some non-empty parenthesis strings A and B.
Constraints
- S is a non-empty string of length at most 3000 consisting of
(,), and?.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
(???(?
Sample Output 1
2
Replacing S with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so 2 should be printed.
Sample Input 2
)))))
Sample Output 2
0
Sample Input 3
??????????????(????????(??????)?????????(?(??)
Sample Output 3
603032273
Print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の数列 A=(A_0,A_1,\ldots,A_{N-1}) が与えられます。
最初の時点では空の皿があり、高橋君は次の操作を K 回繰り返します。
- 皿の中のアメの個数を X とする。皿に A_{(X\bmod N)} 個のアメを追加する。 ただし、X\bmod N で X を N で割った余りを表す。
K 回の操作の後で、皿の中には何個のアメがあるか求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^{12}
- 1 \leq A_i\leq 10^6
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K
A_0 A_1 \ldots A_{N-1}
出力
答えを出力せよ。
入力例 1
5 3 2 1 6 3 1
出力例 1
11
皿の中のアメの個数は次のように変化します。
- 1 回目の操作において、X=0 であるので、アメは A_{(0\mod 5)}=A_0=2 個追加されます。
- 2 回目の操作において、X=2 であるので、アメは A_{(2\mod 5)}=A_2=6 個追加されます。
- 3 回目の操作において、X=8 であるので、アメは A_{(8\mod 5)}=A_3=3 個追加されます。
よって、3 回の操作の後で、皿には 11 個のアメがあります。出力する値は N で割った余りではない事に注意してください。
入力例 2
10 1000000000000 260522 914575 436426 979445 648772 690081 933447 190629 703497 47202
出力例 2
826617499998784056
答えは 32 bit 整数型に収まらない場合があります。
Score : 500 points
Problem Statement
You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.
- Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.
Find how many candies are on the dish after the K operations.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^{12}
- 1 \leq A_i\leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
A_0 A_1 \ldots A_{N-1}
Output
Print the answer.
Sample Input 1
5 3 2 1 6 3 1
Sample Output 1
11
The number of candies on the dish transitions as follows.
- In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
- In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
- In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.
Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.
Sample Input 2
10 1000000000000 260522 914575 436426 979445 648772 690081 933447 190629 703497 47202
Sample Output 2
826617499998784056
The answer may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
2 以上の整数 N および素数 P が与えられます。
下図のような 2N 頂点 (3N-2) 辺のグラフ G を考えます。
より具体的には、頂点を順に頂点 1, 頂点 2, \ldots, 頂点 2N、 辺を順に辺 1, 辺 2, \ldots, 辺 (3N-2) とすると、各辺は次のように頂点を結んでいます。
- 1\leq i\leq N-1 について、辺 i は頂点 i と頂点 i+1 を結んでいる。
- 1\leq i\leq N-1 について、辺 (N-1+i) は頂点 N+i と頂点 N+i+1 を結んでいる。
- 1\leq i\leq N について、辺 (2N-2+i) は頂点 i と頂点 N+i を結んでいる。
i=1,2,\ldots ,N-1 について、次の問題を解いてください。
G の 3N-2 本の辺からちょうど i 本の辺を取り除く方法であって、辺を取り除いた後のグラフも連結であるようなものの個数を P で割ったあまりを求めよ。
制約
- 2 \leq N \leq 3000
- 9\times 10^8 \leq P \leq 10^9
- N は整数である。
- P は素数である。
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
N-1 個の整数を空白区切りで出力せよ。 ただし、k 番目の整数は i=k に対する答えである。
入力例 1
3 998244353
出力例 1
7 15
N=3 の場合について、取り除いた後のグラフも連結となるように、ちょうど 1 本の辺を取り除く方法は次の 7 通りです。
取り除いた後のグラフも連結となるように、ちょうど 2 本の辺を取り除く方法は次の 15 通りです。
よって、これらを P=998244353 で割ったあまりである 7, 15 をこの順に出力します。
入力例 2
16 999999937
出力例 2
46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
P で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
You are given an integer N greater than or equal to 2 and a prime P.
Consider the graph G with 2N vertices and (3N-2) edges shown in the figure below.
More specifically, the edges connect the vertices as follows, where the vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex 2N, and the edges are labeled as Edge 1, Edge 2, \ldots, Edge (3N-2).
- For each 1\leq i\leq N-1, Edge i connects Vertex i and Vertex i+1.
- For each 1\leq i\leq N-1, Edge (N-1+i) connects Vertex N+i and Vertex N+i+1.
- For each 1\leq i\leq N, Edge (2N-2+i) connects Vertex i and Vertex N+i.
For each i=1,2,\ldots ,N-1, solve the following problem.
Find the number of ways, modulo P, to remove exactly i of the 3N-2 edges of G so that the resulting graph is still connected.
Constraints
- 2 \leq N \leq 3000
- 9\times 10^8 \leq P \leq 10^9
- N is an integer.
- P is a prime.
Input
Input is given from Standard Input in the following format:
N P
Output
Print N-1 integers, the i-th of which is the answer for i=k, separated by spaces.
Sample Input 1
3 998244353
Sample Output 1
7 15
In the case N=3, there are 7 ways, shown below, to remove exactly one edge so that the resulting graph is still connected.
There are 15 ways, shown below, to remove exactly two edges so that the resulting graph is still connected.
Thus, these numbers modulo P=998244353 should be printed: 7 and 15, in this order.
Sample Input 2
16 999999937
Sample Output 2
46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
Be sure to print the numbers modulo P.