We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)
We have to apologize to antontrygubO_o a bit here -- the rejection count mentioned in the editorial for Codeforces Round #655 (Div. 2) actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:
Rejection Counts
- A: 12
- B: 16
- C: 6
- D: 19
- E: 18
- F: 2
Total: 73
Without further ado, here are the tutorials for each of the problems:
Tutorial is loading...
Solution (Kotlin) by golions
import java.io.*
import java.util.*
import kotlin.math.*
fun main(){
val f = BufferedReader(InputStreamReader(System.`in`))
for(q in 1..f.readLine().toInt()){
val n = f.readLine().toInt()
val array = f.readLine().split(" ").map{it.toInt()}.toHashSet()
if(array.size == 1){
println(n)
} else {
println(1)
}
}
}
Solution (Java) by MagentaCobra
/*
Omkar orz
*/
import java.util.*;
import java.io.*;
import java.math.*;
public class ModelPasswordA
{
public static void main(String omkar[]) throws Exception
{
BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(infile.readLine());
int T = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
while(T-->0)
{
int N = Integer.parseInt(infile.readLine());
int[] arr = new int[N];
st = new StringTokenizer(infile.readLine());
for(int i=0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
int res = N;
for(int i=1; i < N; i++)
if(arr[i] != arr[i-1])
res = 1;
sb.append(res+"\n");
}
System.out.print(sb);
}
}
Solution (C++) by hugopm
#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;
void solve() {
int n; cin >> n;
vector<int> vec(n);
for (int i = 0; i < n; ++i) {
cin >> vec[i];
}
sort(all(vec));
if (vec.front() == vec.back()) cout << n << "\n";
else cout << "1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int nbTests;
cin >> nbTests;
for (int iTest = 0; iTest < nbTests; ++iTest) {
solve();
}
}
Preparation: hu_tao
Tutorial is loading...
Solution (Kotlin) by Tlatoani
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() {
val jin = BufferedReader(InputStreamReader(System.`in`))
val out = StringBuilder()
for (c in 1..jin.readLine().toInt()) {
val line = jin.readLine().split(" ")
val n = line[0].toInt()
val k = line[1].last().toString().toInt() % 2
val array = jin.readLine().split(" ").map { it.toLong() }.toLongArray()
var m = array.max()!!
for (j in 0 until n) {
array[j] = m - array[j]
}
if (k == 0) {
m = array.max()!!
for (j in 0 until n) {
array[j] = m - array[j]
}
}
out.appendln(array.joinToString(" "))
}
print(out)
}
Solution (Java) by MagentaCobra
//Omkar, Holy Light
import java.util.*;
import java.io.*;
import java.math.*;
public class ModelB
{
public static void main(String omkar[]) throws Exception
{
//query based
BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(infile.readLine());
int T = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
while(T-->0)
{
st = new StringTokenizer(infile.readLine());
int N = Integer.parseInt(st.nextToken());
long K = Long.parseLong(st.nextToken())%2;
if(K == 0) K = 2;
int[] arr = new int[N];
st = new StringTokenizer(infile.readLine());
for(int i=0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
for(int turns=0; turns < K; turns++)
{
int max = arr[0];
for(int x: arr)
max = Math.max(max, x);
for(int i=0; i < N; i++)
arr[i] = max-arr[i];
}
for(int i=0; i < N; i++)
{
sb.append(arr[i]);
if(i+1 < N)
sb.append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}
Solution (C++) by tfg
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int t;
std::cin >> t;
while(t--) {
int n;
long long k;
std::cin >> n >> k;
std::vector<int> a(n);
for(int i = 0; i < n; i++) {
std::cin >> a[i];
}
if(k > 1) {
k = 2 + k % 2;
}
while(k--) {
int mx = -1000000000;
for(int i = 0; i < n; i++) {
mx = std::max(mx, a[i]);
}
for(int i = 0; i < n; i++) {
a[i] = mx - a[i];
}
}
for(int i = 0; i < n; i++) {
std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
}
}
}
Idea: hu_tao
Preparation: hu_tao
Tutorial is loading...
Solution (Kotlin) by Tlatoani
import kotlin.math.max
fun main() {
for (c in 1..readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val hs = readLine()!!.split(" ").map { it.toLong() }
var answer = 0L
for (j in 1 until n) {
answer += max(0L, hs[j - 1] - hs[j])
}
println(answer)
}
}
Solution (Java) by qlf9
import java.util.*;
import java.io.*;
public class OmkarAndWaterslide {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(f.readLine());
while(t-->0){
int n = Integer.parseInt(f.readLine());
long[] arr = new long[n];
StringTokenizer st = new StringTokenizer(f.readLine());
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
long ans = 0;
for(int i = 0; i < n-1; i++){
ans+=Math.max(0, arr[i]-arr[i+1]);
}
out.println(ans);
}
out.close();
}
}
Solution (C++) by tfg
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int t;
std::cin >> t;
while(t--) {
int n;
std::cin >> n;
long long last = 0;
long long ans = 0;
while(n--) {
long long x;
std::cin >> x;
x += ans;
if(x >= last) {
last = x;
} else {
ans += last — x;
}
}
std::cout << ans << '\n';
}
}
Idea: qlf9
Preparation: qlf9
Tutorial is loading...
Solution (Kotlin) by Tlatoani
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() {
val jin = BufferedReader(InputStreamReader(System.`in`))
val out = StringBuilder()
for (c in 1..jin.readLine().toInt()) {
val n = jin.readLine().toInt()
val s = jin.readLine()
if (s.all { it == s[0] }) {
out.appendln((n + 2) / 3)
} else {
var k = 0
while (s[k] == s[0]) {
k++
}
var answer = 0
var curr = 0
var chara = s[k]
for (j in k until k + n) {
if (s[j % n] == chara) {
curr++
} else {
answer += curr / 3
curr = 1
chara = s[j % n]
}
}
answer += curr / 3
out.appendln(answer)
}
}
print(out)
}
Solution (Java) by qlf9
import java.util.*;
import java.io.*;
public class OmkarAndBedWars {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(f.readLine());
while(t-->0){
int n = Integer.parseInt(f.readLine());
String str = f.readLine();
boolean same = true;
for(int i = 1; i < n; i++){
if(str.charAt(i) != str.charAt(0)){
same = false;
break;
}
}
if(same){
out.println((n+2)/3);
continue;
}
ArrayList<Integer> count = new ArrayList<Integer>();
int last = 0;
int cnt = 1;
for(int i = 1; i < n; i++){
if(str.charAt(i) == str.charAt(last)){
cnt++;
}else{
count.add(cnt);
last = i;
cnt = 1;
}
}
if(str.charAt(n-1) == str.charAt(0)){
count.set(0, count.get(0)+cnt);
}else{
count.add(cnt);
}
int sum = 0;
for(int i: count) sum+=(i/3);
out.println(sum);
}
out.close();
}
}
Solution (C++) by Ari
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, ans = 0;
cin >> n;
string s;
cin >> s;
int cnt = 0;
while(s.size() && s[0] == s.back()) {
cnt++;
s.pop_back();
}
if(s.empty()) {
if(cnt <= 2) {
cout << "0\n";
return;
}
if(cnt == 3) {
cout << "1\n";
return;
}
cout << (cnt + 2) / 3 << '\n';
return;
}
s.push_back('$');
for(int i = 0; i + 1 < s.size(); i++) {
cnt++;
if(s[i] != s[i + 1]) {
ans += cnt / 3;
cnt = 0;
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
Idea: Tlatoani
Preparation: Tlatoani
Tutorial is loading...
Solution (Kotlin) by Tlatoani
fun main() {
val n = readLine()!!.toInt()
for (x in 1..n) {
for (y in 1..n) {
if (x % 2 == 0) {
print(1L shl (x + y))
} else {
print(0)
}
print(" ")
}
println()
}
val q = readLine()!!.toInt()
for (j in 1..q) {
val k = readLine()!!.toLong()
var x = 1
var y = 1
print("1 1 ")
for (e in 3..2 * n) {
if ((x % 2 == 0) == (((k shr e) % 2L) == 1L)) {
y++
} else {
x++
}
print("$x $y ")
}
println()
}
}
Solution (Java) by golions
//make sure to make new file!
import java.io.*;
import java.util.*;
public class DuckSolution{
public static void main(String[] args)throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(f.readLine());
long[][] board = new long[n][n];
board[0][0] = 0L;
board[n-1][n-1] = 0L;
for(int k = 0; k < n; k++){
for(int j = 0; j < n; j++){
if(k == 0 && j == 0) continue;
if(k == n-1 && j == n-1) continue;
if(k%2 == 0){
board[k][j] = 1L << k+j;
}
}
}
for(int k = 0; k < n; k++){
StringJoiner sj = new StringJoiner(" ");
for(int j = 0; j < n; j++){
sj.add("" + board[k][j]);
}
out.println(sj.toString());
}
out.flush();
int q = Integer.parseInt(f.readLine());
for(int t = 0; t < q; t++){
long i = Long.parseLong(f.readLine());
ArrayList<Integer> x = new ArrayList<Integer>();
ArrayList<Integer> y = new ArrayList<Integer>();
int curx = 0;
int cury = 0;
x.add(1);
y.add(1);
while(curx < n-1 || cury < n-1){
if(curx == n-1){
cury++;
} else if(cury == n-1){
curx++;
} else {
long and = Math.max(board[curx+1][cury],board[curx][cury+1]);
if(((i & and) > 0) ^ (board[curx+1][cury] > 0)){
cury++;
} else {
curx++;
}
}
x.add(curx+1);
y.add(cury+1);
}
StringJoiner sj = new StringJoiner(" ");
for(int k = 0; k < x.size(); k++){
sj.add("" + x.get(k) + " " + y.get(k));
}
out.println(sj.toString());
out.flush();
}
out.close();
}
}
Solution (C++) by hugopm
#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int side; cin >> side;
vector<vector<ll>> grid(side, vector<ll>(side, 0));
for (int i = 0; i < side; ++i) {
for (int j = 0; j < side; ++j) {
if ((i-j+side)&2LL) grid[i][j] = (1LL << (i+j));
cout << grid[i][j] << " \n"[j==side-1];
}
}
cout << flush;
int nbQuery; cin >> nbQuery;
for (int iQuery = 0; iQuery < nbQuery; ++iQuery) {
ll sum; cin >> sum;
cout << "1 1";
int row = 0, col = 0;
for (int diag = 0; diag < 2*side-2; ++diag) {
ll should = sum&(1LL<<(diag+1));
if (row+1<side && grid[row+1][col] == should) ++row;
else ++col;
cout << " " << row+1 << " " << col+1;
}
cout << endl << flush;
}
}
Idea: Tlatoani
Preparation: Tlatoani and golions
Tutorial is loading...
EDIT: The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:
If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.
If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $$$\alpha$$$ that can be immediately applied on the vector.
Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).
Therefore, applying other (different) operations cannot prevent operation $$$\alpha$$$ from being able to be applied, so operation $$$\alpha$$$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $$$\alpha$$$ does not occur initially, then operation $$$\alpha$$$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.
Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).
Solution (Kotlin) by Tlatoani
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val jin = BufferedReader(InputStreamReader(System.`in`))
val n = jin.readLine().toLong()
val tokenizer = StringTokenizer(jin.readLine())
var sum = 0L
for (j in 0L until n) {
sum += tokenizer.nextToken().toLong() - j
}
val joiner = StringJoiner(" ")
for (j in 0L until n) {
joiner.add(((sum / n) + (if (j < sum % n) 1L else 0L) + j).toString())
}
println(joiner)
}
Solution (Java) by qlf9
import java.util.*;
import java.io.*;
public class OmkarAndLandslideNumber2 {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
long n = Long.parseLong(f.readLine());
long sum = 0;
StringTokenizer st = new StringTokenizer(f.readLine());
for(int i = 0; i < n; i++){
sum+=Long.parseLong(st.nextToken());
}
long k = ((sum - n*(n - 1)/2) / n);
long diff = sum - (n*k + n*(n - 1)/2);
StringBuilder ans = new StringBuilder();
for(long i = 0; i < n; i++){
if(i < diff){
ans.append(k+i+1L);
ans.append(" ");
}else{
ans.append(k+i);
ans.append(" ");
}
}
out.println(ans.toString().trim());
out.close();
}
}
Solution (C++) by Devil
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
ll n;
cin >> n;
ll s = 0;
for (ll x, i = 0; i < n; ++i)
cin >> x, s += x;
ll l = (s - n * (n-1) / 2) / n + 1;
s = l * n + n * (n-1) / 2 - s;
for (int i = 0; i < n; ++i)
cout << l + i - (n-i <= s) << " \n"[i+1==n];
return 0;
}
Idea: Tlatoani
Preparation: Tlatoani and qlf9
Tutorial is loading...
Solution (Kotlin) by Tlatoani
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min
fun main() {
val jin = BufferedReader(InputStreamReader(System.`in`))
var line = jin.readLine().split(" ")
val n = line[0].toInt()
val m = line[1].toInt()
val k = line[2].toInt()
val dpLeft = IntArray(1 shl k) { n + 1 }
val dpRight = IntArray(1 shl k) { -1 }
var original = jin.readLine().reversed().toInt(2)
var goal = jin.readLine().reversed().toInt(2)
val permutation = IntArray(k) { it }
dpLeft[original] = 0
dpRight[goal] = 0
for (j in 1..n) {
line = jin.readLine().split(" ")
val a = line[0].toInt() - 1
val b = line[1].toInt() - 1
var c = (original shr permutation[a]) and 1
var d = (original shr permutation[b]) and 1
original -= c shl permutation[a]
original -= d shl permutation[b]
original += d shl permutation[a]
original += c shl permutation[b]
c = (goal shr permutation[a]) and 1
d = (goal shr permutation[b]) and 1
goal -= c shl permutation[a]
goal -= d shl permutation[b]
goal += d shl permutation[a]
goal += c shl permutation[b]
dpLeft[original] = min(dpLeft[original], j)
dpRight[goal] = j
c = permutation[a]
d = permutation[b]
permutation[a] = d
permutation[b] = c
}
var best = -1
var l = -1
var r = -1
for (mask in (1 shl k) - 1 downTo 0) {
for (e in 0 until k) {
if ((mask shr e) and 1 != 0) {
dpLeft[mask - (1 shl e)] = min(dpLeft[mask - (1 shl e)], dpLeft[mask])
dpRight[mask - (1 shl e)] = max(dpRight[mask - (1 shl e)], dpRight[mask])
}
}
if (dpLeft[mask] + m <= dpRight[mask] && Integer.bitCount(mask) > best) {
best = Integer.bitCount(mask)
l = dpLeft[mask] + 1
r = dpRight[mask]
}
}
println(k - Integer.bitCount(original) - Integer.bitCount(goal) + (2 * best))
println("$l $r")
}
Solution (Java) by qlf9
import java.io.*;
import java.util.*;
public class OmkarAndPies {
public static int INF = Integer.MAX_VALUE/2;
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int bitstr = Integer.parseInt(f.readLine(), 2);
int goal = Integer.parseInt(f.readLine(), 2);
int[] arr1 = new int[n];
int[] arr2 = new int[n];
for(int i = 0; i < n; i++){
st = new StringTokenizer(f.readLine());
arr1[i] = Integer.parseInt(st.nextToken());
arr2[i] = Integer.parseInt(st.nextToken());
}
int[] lefts = new int[n+1];
int[] rights = new int[n+1];
rights[0] = goal;
lefts[0] = bitstr;
int[] permutation = new int[k];
int[] indices = new int[k];
for(int i = 0; i < k; i++){
permutation[i] = i;
indices[i] = i;
}
for(int i = 0; i < n; i++){
int temp = indices[arr1[i]-1];
indices[arr1[i]-1] = indices[arr2[i]-1];
indices[arr2[i]-1] = temp;
permutation[indices[arr1[i]-1]] = arr1[i]-1;
permutation[indices[arr2[i]-1]] = arr2[i]-1;
lefts[i+1] = applyPermutation(indices, bitstr, k);
rights[i+1] = applyPermutation(indices, goal, k);
}
int[] dpLeft = new int[(1 << k)];
int[] dpRight = new int[(1 << k)];
Arrays.fill(dpLeft, INF);
Arrays.fill(dpRight, -INF);
for(int i = 0; i <= n; i++){
dpLeft[lefts[i]] = Math.min(dpLeft[lefts[i]], i);
dpRight[rights[i]] = Math.max(dpRight[rights[i]], i);
}
for(int i = (1 << k)-1; i > 1; i--){
int temp = i;
int count = 0;
while(temp != 0){
if(temp % 2 == 1){
dpLeft[i-(1 << count)] = Math.min(dpLeft[i-(1 << count)], dpLeft[i]);
dpRight[i-(1 << count)] = Math.max(dpRight[i-(1 << count)], dpRight[i]);
}
temp/=2;
count++;
}
}
for(int i = 0; i < (1 << k); i++){
if(dpLeft[i] == 2 && dpRight[i] == 8){
System.out.println(i);
}
}
int maxVal = -INF;
int intLeft = -1;
int intRight = -1;
for(int i = 0; i < (1 << k); i++){
if(dpRight[i]-dpLeft[i] < m) continue;
int a1 = lefts[dpLeft[i]];
int a2 = rights[dpRight[i]];
int count = 0;
for(int j = 0; j < k; j++){
if(a1 % 2 == a2 % 2) count++;
a1/=2;
a2/=2;
}
if(count > maxVal){
maxVal = count;
intLeft = dpLeft[i]+1;
intRight = dpRight[i];
}
}
out.println(maxVal);
out.println(intLeft + " " + intRight);
out.close();
}
public static int applyPermutation(int[] permutation, int bitstr, int k){
int ans = 0;
for(int i = k-1; i >= 0; i--){
if(bitstr % 2 == 1){
ans += (1 << (k-permutation[i]-1));
}
bitstr/=2;
}
return ans;
}
}
Solution (C++) by mohammedehab2002
#include <bits/stdc++.h>
using namespace std;
int p[20],dp[2][(1<<20)];
int getmask(string s)
{
int ans=0;
for (int i=0;i<s.size();i++)
ans|=((s[i]-'0')<<i);
return ans;
}
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
string a,b;
cin >> a >> b;
for (int i=0;i<k;i++)
p[i]=i;
for (int i=0;i<(1<<k);i++)
{
dp[0][i]=1e9;
dp[1][i]=-1e9;
}
dp[0][getmask(a)]=0;
dp[1][getmask(b)]=0;
for (int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x--;
y--;
swap(p[x],p[y]);
string aa(k,'0'),bb(k,'0');
for (int j=0;j<k;j++)
{
aa[p[j]]=a[j];
bb[p[j]]=b[j];
}
dp[0][getmask(aa)]=min(dp[0][getmask(aa)],i);
dp[1][getmask(bb)]=i;
}
int o1=count(a.begin(),a.end(),'1'),o2=count(b.begin(),b.end(),'1');
pair<int,pair<int,int> > ans(0,{0,0});
for (int i=(1<<k)-1;i>=0;i--)
{
if (dp[1][i]-dp[0][i]>=m)
ans=max(ans,make_pair(k-(o1+o2-2*__builtin_popcount(i)),make_pair(dp[0][i]+1,dp[1][i])));
for (int j=0;j<k;j++)
{
if (i&(1<<j))
{
dp[0][i^(1<<j)]=min(dp[0][i^(1<<j)],dp[0][i]);
dp[1][i^(1<<j)]=max(dp[1][i^(1<<j)],dp[1][i]);
}
}
}
printf("%d\n%d %d",ans.first,ans.second.first,ans.second.second);
}
Idea: Tlatoani
Preparation: Tlatoani
Tutorial is loading...
Solution (C++) by zscoder
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int MOD = 998244353;
vector<int> fact;
vector<int> ifact;
vector<int> pow2;
int add(int a, int b)
{
a+=b;
while(a>=MOD) a-=MOD;
return a;
}
void radd(int &a, int b)
{
a=add(a,b);
}
int mult(int a, int b)
{
return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
a=mult(a,b);
}
int modpow(int a, int b)
{
int r=1;
while(b)
{
if(b&1) r=mult(r,a);
a=mult(a,a);
b>>=1;
}
return r;
}
int choose(int a, int b)
{
if(a<0) return 0;
if(b<0) return 0;
if(a<b) return 0;
if(b==0) return 1;
if(a==b) return 1;
return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
return modpow(a,MOD-2);
}
void init(int _n)
{
fact.clear(); ifact.clear(); pow2.clear();
fact.resize(_n+1);
ifact.resize(_n+1);
pow2.resize(_n+1);
pow2[0]=1;
ifact[0]=1;
fact[0]=1;
for(int i=1;i<=_n;i++)
{
pow2[i]=add(pow2[i-1],pow2[i-1]);
fact[i]=mult(fact[i-1],i);
//ifact[i]=mult(ifact[i-1],inv[i]);
}
ifact[_n] = inverse(fact[_n]);
for(int i=_n-1;i>=1;i--)
{
ifact[i] = mult(ifact[i + 1], i + 1);
}
}
int solve_slow(int n, int m)
{
vi f(n+1,0);
for(int k=1;k<=n;k++)
{
int sum=0;
for(int l=1;l<=k;l++)
{
for(int i=0;i<=n;i++)
{
int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
radd(sum, mult(coeff, add(f[k-l],i+1)));
}
}
{
int l=0;
int sumcoeff=0;
for(int i=0;i<=n;i++)
{
int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
radd(sum, mult(coeff, i+1));
radd(sumcoeff,coeff);
}
int actualcoeff = add(1,MOD-sumcoeff);
assert(actualcoeff!=0);
f[k]=mult(inverse(actualcoeff),sum);
}
}
return f[n];
}
int solve_fast(int n, int m)
{
vi f(n+1,0);
int presum=0;
for(int k=1;k<=n;k++)
{
int sum=mult(presum,choose(n+m,m+k));
radd(sum,mult(fact[m-1],mult(choose(m+k+1,m+1),choose(n+m+1,m+k+1))));
int outsidecoeff = mult(fact[k],mult(fact[n-k],mult(ifact[n+m],m)));
sum = mult(sum, outsidecoeff);
f[k]=mult(mult(m+k,mult(ifact[k],fact[k-1])),sum);
//f[k]=mult(mult(k,mult(fact[m+k-1],ifact[m+k])),sum);
radd(presum,mult(fact[m+k-1],mult(ifact[k],f[k])));
}
return f[n];
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
init(int(1e7)+100);
int n,m; cin>>n>>m;
//cout<<solve_slow(n,m)<<'\n';
cout<<solve_fast(n,m)<<'\n';
}
Solution (Java) by qlf9
import java.util.*;
import java.io.*;
public class ZSShufflesCards {
public static long MOD = 998244353;
public static long[] fact;
public static long[] invfact;
public static long[] pow2;
public static int MAX = 4000005;
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
fact = new long[MAX];
invfact = new long[MAX];
pow2 = new long[MAX];
fact[0] = 1;
invfact[0] = 1;
pow2[0] = 1;
for(int i = 1; i < MAX; i++){
pow2[i] = add(pow2[i-1], pow2[i-1]);
fact[i] = mult(fact[i-1], i);
}
invfact[MAX-1] = inverse(fact[MAX-1]);
for(int i = MAX-2; i >= 1; i--){
invfact[i] = mult(invfact[i+1], i+1);
}
long[] ans = new long[n+1];
long currsum = 0;
for(int k = 1; k <= n; k++){
long sum = mult(currsum, ncr(n+m, m+k));
sum = add(sum,mult(fact[m-1],mult(ncr(m+k+1,m+1),ncr(n+m+1,m+k+1))));
long outsidecoeff = mult(fact[k],mult(fact[n-k],mult(invfact[n+m],m)));
sum = mult(sum, outsidecoeff);
ans[k]=mult(mult(m+k,mult(invfact[k],fact[k-1])),sum);
currsum = add(currsum,mult(fact[m+k-1],mult(invfact[k],ans[k])));
}
out.println(ans[n]);
out.close();
}
public static long add(long a, long b){
return((a+b)%MOD+MOD)%MOD;
}
public static long mult(long a, long b){
return((a*b)%MOD+MOD)%MOD;
}
public static long pow(long a, long b){
long ans = 1;
while(b > 0){
if((b&1) == 1) ans = mult(ans, a);
a = mult(a, a);
b>>=1;
}
return ans;
}
public static long ncr(long a, long b){
if(a<0) return 0;
if(b<0) return 0;
if(a<b) return 0;
if(b==0) return 1;
if(a==b) return 1;
return mult(fact[(int)a],mult(invfact[(int)b],invfact[(int)(a-b)]));
}
public static long inverse(long a){
return pow(a, MOD-2);
}
}
Solution (Kotlin) by Tlatoani
const val MOD = 998244353L
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val factorial = LongArray(4000002)
factorial[0] = 1L
for (j in 1..4000001) {
factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
}
val factInv = LongArray(4000002)
factInv[4000001] = factorial[4000001] pow -1
for (j in 4000000 downTo 0) {
factInv[j] = ((j + 1).toLong() * factInv[j + 1]) % MOD
}
fun choose(a: Int, b: Int) = if (a < 0 || b < 0 || b > a) 0L else (factorial[a] * ((factInv[b] * factInv[a - b]) % MOD)) % MOD
val answer = LongArray(n + 1)
var currSum = 0L
for (k in 1..n) {
var sum = currSum * choose(n + m, m + k)
sum %= MOD
sum += factorial[m - 1] * ((choose(m + k + 1, m + 1) * choose(n + m + 1, m + k + 1)) % MOD)
sum %= MOD
sum *= (factorial[k] * ((factorial[n - k] * ((factInv[n + m] * m.toLong()) % MOD)) % MOD)) % MOD
sum %= MOD
answer[k] = sum * (((m + k).toLong() * ((factInv[k] * factorial[k - 1]) % MOD)) % MOD)
answer[k] %= MOD
currSum += factorial[m + k - 1] * ((factInv[k] * answer[k]) % MOD)
currSum %= MOD
}
println(answer[n])
}
const val MOD_TOTIENT = MOD.toInt() - 1
infix fun Long.pow(power: Int): Long {
var e = power
e %= MOD_TOTIENT
if (e < 0) {
e += MOD_TOTIENT
}
if (e == 0 && this == 0L) {
return this
}
var b = this % MOD
var res = 1L
while (e > 0) {
if (e and 1 != 0) {
res *= b
res %= MOD
}
b *= b
b %= MOD
e = e shr 1
}
return res
}
Idea: zscoder
Preparation: zscoder
Tutorial is loading...
Solution (C++) by KLPP
#include<bits/stdc++.h>
using namespace std;
#define MAX 262144
#define MAXN 1000000
long long int a[MAXN],b[MAXN];
using cd = complex<double>;
const double PI = acos(-1);
vector<cd> A(MAX),B(MAX);
vector<cd> Amx(MAX),Bmx(MAX);
vector<cd> Amn(MAX),Bmn(MAX);
vector<cd> E11(MAX),E12(MAX),E21(MAX),E22(MAX);
vector<cd> SQ1(MAX),SQ2(MAX);
vector<cd> V(MAX);
vector<long long int> A1(MAX),A2(MAX);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}
void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){
for(int i=0;i<a.size();i++){
c[i]=a[i]*b[i];
}
}
int main(){
long long int n,m,q;
scanf("%lld %lld %lld",&n,&m,&q);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
for(int i=0;i<m;i++){
scanf("%lld",&b[i]);
}
for(int i=0;i<MAX;i++){
A[i]=cd(0,0);
Amn[i]=cd(0,0);
Amx[i]=cd(0,0);
B[i]=cd(0,0);
Bmn[i]=cd(0,0);
Bmx[i]=cd(0,0);
}
for(int i=0;i<n;i++){
A[a[i]]+=cd(1,0);
}
for(int i=0;i<n-1;i++){
Amn[min(a[i],a[i+1])]+=cd(1,0);
}
for(int i=0;i<n-1;i++){
Amx[max(a[i],a[i+1])]+=cd(1,0);
}
for(int i=0;i<m;i++){
B[b[i]]+=cd(1,0);
}
for(int i=0;i<m-1;i++){
Bmn[min(b[i],b[i+1])]+=cd(1,0);
}
for(int i=0;i<m-1;i++){
Bmx[max(b[i],b[i+1])]+=cd(1,0);
}
fft(A,0);
fft(Amn,0);
fft(Amx,0);
fft(B,0);
fft(Bmn,0);
fft(Bmx,0);
prod(A,Bmn,E11);
prod(Amn,B,E12);
prod(Amx,B,E21);
prod(A,Bmx,E22);
prod(Amn,Bmn,SQ1);
prod(Amx,Bmx,SQ2);
prod(A,B,V);
fft(E11,1);
fft(E12,1);
fft(E21,1);
fft(E22,1);
fft(SQ1,1);
fft(SQ2,1);
fft(V,1);
for(int i=0;i<MAX;i++){
A1[i]=round(SQ1[i].real())-round(E11[i].real())-round(E12[i].real())+round(V[i].real());
A2[i]=round(SQ2[i].real())-round(E21[i].real())-round(E22[i].real())+round(V[i].real());
}
for(int i=1;i<MAX;i++){
A2[i]+=A2[i-1];
}
for(int i=MAX-2;i>-1;i--){
A1[i]+=A1[i+1];
}
for(int i=0;i<q;i++){
int query;
scanf("%d",&query);
//cout<<A1[query]<<" "<<A2[query-1]<<endl;
printf("%lld\n",A1[query]-A2[query-1]);
}
return 0;
}
Idea: KLPP
Preparation: KLPP
