CF - Santa's Bot

Author: Kevin Sheng


Official Editorial

Clarification: The optimization the author uses is this property of fractions modulo 998244353998244353 is this:

Say we had two fractions x=abx=\frac{a}{b} and y=cdy=\frac{c}{d}. Let ff be a function that calculates the "total" of a fraction (that is, the numerator times the modular inverse of the denominator). To find f(x+y)f(x + y), we can simply calculate f(x)+f(y)f(x) + f(y). Thus, to find the total of the overall probability, we can just add up all the totals of all the smaller probabilities, keeping a running sum as we go.

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
constexpr int MOD = 998244353;

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
/**
* https://codeforces.com/problemset/problem/1279/D
* 2
* 2 2 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!