CF - Santa's Bot
Author: Kevin Sheng
Clarification: The optimization the author uses is this property of fractions modulo is this:
Say we had two fractions and . Let be a function that calculates the "total" of a fraction (that is, the numerator times the modular inverse of the denominator). To find , we can simply calculate . 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!