Adding Solutions

Basic Debugging

Choosing a Language

Contest Strategy

Contests

Contributing

C++ With the Command Line

Data Types

How to Debug

Debugging C++

Expected Knowledge

Fast Input & Output

(Optional) C++ - Writing Generic Code

Input & Output

Introduction to Competitive Programming

(Optional) C++ - Lambda Expressions

Resources: Learning to Code

Introducing Modules

Olympiads

How to Practice

Resources: Competitive Programming

Resources: USA-Specific

Running Code Locally

Running Code Online

USACO Camp

USACO FAQs

USACO Monthlies

Using This Guide

Working With MDX

Ad Hoc Problems

Casework

Complete Search with Recursion

Additional Practice for USACO Bronze

Basic Complete Search

Introduction to Data Structures

Introduction to Graphs

Introduction to Greedy Algorithms

Introduction to Sets & Maps

Introduction to Sorting

Rectangle Geometry

Simulation

Time Complexity

Binary Search

Binary Search on a Sorted Array

Additional Practice for USACO Silver

Flood Fill

Introduction to Functional Graphs

Graph Traversal

Greedy Algorithms with Sorting

Intro to Bitwise Operators

Introduction to Tree Algorithms

More on Prefix Sums

Introduction to Prefix Sums

Priority Queues

Custom Comparators and Coordinate Compression

Two Pointers

DP on Trees - Solving For All Roots

Combinatorics

Additional Practice for USACO Gold

(Optional) Sorted Sets with Custom Comparators

Bitmask DP

Range DP

DP on Trees - Introduction

Disjoint Set Union

Digit DP

Divisibility

Hashing

(Optional) Hashmaps

Introduction to DP

More Operations on Sorted Sets

Knapsack DP

(Optional) LCA with Euler Tour

Longest Increasing Subsequence

Minimum Spanning Trees

(Optional) Meet In The Middle

Modular Arithmetic

Point Update Range Sum

Paths on Grids

Shortest Paths with Non-Negative Edge Weights

Sliding Window

Stacks

Optimizing Unimodal Functions

Topological Sort

(Optional) Euler Tour Technique

Shortest Paths with Unweighted Edges

2D Range Queries

Binary Jumping

(Optional) Bitsets

Centroid Decomposition

Additional Practice for USACO Platinum

Convex Hull

Convex Hull Trick

Divide & Conquer - DP

Divide & Conquer - SRQ

Sum over Subsets DP

Geometry Primitives

Heavy-Light Decomposition

Matrix Exponentiation

Small-To-Large Merging

Inclusion-Exclusion Principle

Santa's Bot

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
 const _components = {
 a: "a",
 code: "code",
 h2: "h2",
 p: "p",
 pre: "pre",
 strong: "strong",
 ...props.components
 }, {CPPSection, HeaderLink, Info, JavaSection, LanguageSection, MATHSPAN} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!Info) _missingMdxReference("Info", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: _jsx(_components.a, {
 href: "https://codeforces.com/blog/entry/72577",
 rel: "nofollow",
 target: "_blank",
 children: "Official Editorial (C++)"
 })
 }), "\n", _jsxs(_components.p, {
 children: ["Clarification: The optimization the author uses is this property of fractions\nmodulo ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "998244353",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>998244353</mn></mrow><annotation encoding=\"application/x-tex\">998244353</annotation></semantics></math>998244353"
 }), " is this:"]
 }), "\n", _jsx(Info, {
 children: _jsxs(_components.p, {
 children: ["Say we had two fractions ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "x=\\frac{a}{b}",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>x</mi><mo>=</mo><mfrac><mi>a</mi><mi>b</mi></mfrac></mrow><annotation encoding=\"application/x-tex\">x=\\frac{a}{b}</annotation></semantics></math>x=ba​"
 }), " and ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "y=\\frac{c}{d}",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>y</mi><mo>=</mo><mfrac><mi>c</mi><mi>d</mi></mfrac></mrow><annotation encoding=\"application/x-tex\">y=\\frac{c}{d}</annotation></semantics></math>y=dc​"
 }), ". Let ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "f",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>f</mi></mrow><annotation encoding=\"application/x-tex\">f</annotation></semantics></math>f"
 }), " be a\nfunction that calculates the \"total\" of a fraction (that is, the numerator times\nthe modular inverse of the denominator). To find ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "f(x + y)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>f</mi><mo stretchy=\"false\">(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">f(x + y)</annotation></semantics></math>f(x+y)"
 }), ", we can simply\ncalculate ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "f(x) + f(y)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>f</mi><mo stretchy=\"false\">(</mo><mi>x</mi><mo stretchy=\"false\">)</mo><mo>+</mo><mi>f</mi><mo stretchy=\"false\">(</mo><mi>y</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">f(x) + f(y)</annotation></semantics></math>f(x)+f(y)"
 }), ". Thus, to find the total of the overall probability, we\ncan just add up all the totals of all the smaller probabilities, keeping a\nrunning sum as we go."]
 })
 }), "\n", _jsxs(_components.h2, {
 id: "implementation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#implementation",
 children: _jsx(HeaderLink, {})
 }), "Implementation"]
 }), "\n", _jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity:"
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(N \\log(\\text{MOD}))",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mi>N</mi><mi>log</mi><mo>⁡</mo><mo stretchy=\"false\">(</mo><mtext>MOD</mtext><mo stretchy=\"false\">)</mo><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(N \\log(\\text{MOD}))</annotation></semantics></math>O(Nlog(MOD))"
 }), ", where ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "N = \\sum_{i=1}^{n} k_i \\le 10^6",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>N</mi><mo>=</mo><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><msub><mi>k</mi><mi>i</mi></msub><mo>≤</mo><msup><mn>10</mn><mn>6</mn></msup></mrow><annotation encoding=\"application/x-tex\">N = \\sum_{i=1}^{n} k_i \\le 10^6</annotation></semantics></math>N=∑i=1n​ki​≤106"
 }), "\nis the total number of wanted items across all kids."]
 }), "\n", _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <iostream>\n#include <unordered_map>\n#include <vector>\n\nusing std::cout;\nusing std::endl;\nusing std::vector;\n\nconstexpr int MOD = 998244353;\n\n// from /gold/modular\nlong long pow_mod(long long base, long long exp) {\n\tbase %= MOD;\n\tlong long result = 1;\n\twhile (exp > 0) {\n\t\tif (exp % 2 == 1) // if n is odd\n\t\t\tresult = result * base % MOD;\n\t\tbase = base * base % MOD;\n\t\texp /= 2; // divide by two\n\t}\n\treturn result;\n}\n\nlong long mod_inv(long long n) { return pow_mod(n, MOD - 2); }\n\nlong long frac_total(long long num, long long denom) {\n\treturn ((num % MOD) * mod_inv(denom)) % MOD;\n}\n\nint main() {\n\tint child_num;\n\tstd::cin >> child_num;\n\tvector<vector<int>> children(child_num);\n\tstd::unordered_map<int, int> wanter_nums;\n\tfor (int c = 0; c < child_num; c++) {\n\t\tint wanted_num;\n\t\tstd::cin >> wanted_num;\n\t\tfor (int i = 0; i < wanted_num; i++) {\n\t\t\tint item;\n\t\t\tstd::cin >> item;\n\t\t\twanter_nums[item]++;\n\t\t\tchildren[c].push_back(item);\n\t\t}\n\t}\n\n\tlong long prob = 0;\n\tfor (const vector<int> &c : children) {\n\t\tfor (const int &i : c) {\n\t\t\tint num = 1 * 1 * wanter_nums[i];\n\t\t\tlong long denom = child_num * (long long)c.size() * child_num;\n\t\t\tprob = (prob + frac_total(num, denom)) % MOD;\n\t\t}\n\t}\n\n\tcout << prob << endl;\n}\n"
 })
 })
 }), _jsx(JavaSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "import java.io.BufferedReader;\nimport java.io.IOException;\nimport java.io.InputStreamReader;\nimport java.util.Arrays;\nimport java.util.HashMap;\n\n/**\n * https://codeforces.com/problemset/problem/1279/D\n * 2\n * 2 2 1\n * 1 1 should output 124780545\n */\npublic class SantaBot {\n\tprivate static final int MOD = 998244353;\n\tpublic static void main(String[] args) throws IOException {\n\t\tBufferedReader read = new BufferedReader(new InputStreamReader(System.in));\n\t\tint childNum = Integer.parseInt(read.readLine());\n\n\t\tint[][] children = new int[childNum][];\n\t\tHashMap<Integer, Integer> wanterNum = new HashMap<>();\n\t\tfor (int c = 0; c < childNum; c++) {\n\t\t\tint[] raw = Arrays.stream(read.readLine().split(\" \"))\n\t\t\t .mapToInt(Integer::parseInt)\n\t\t\t .toArray();\n\t\t\tchildren[c] = Arrays.copyOfRange(raw, 1, raw.length);\n\t\t\tfor (int i : children[c]) {\n\t\t\t\twanterNum.put(i, wanterNum.getOrDefault(i, 0) + 1);\n\t\t\t}\n\t\t}\n\n\t\tlong probTotal = 0;\n\t\tfor (int[] c : children) {\n\t\t\tlong denom = (long)childNum * c.length * childNum;\n\t\t\tfor (int i : c) {\n\t\t\t\tint num = wanterNum.get(i);\n\t\t\t\tprobTotal = (probTotal + fracTotal(num, denom)) % MOD;\n\t\t\t}\n\t\t}\n\t\tSystem.out.println(probTotal);\n\t}\n\n\tprivate static long fracTotal(long num, long denom) {\n\t\treturn ((num % MOD) * modInv(denom)) % MOD;\n\t}\n\n\tprivate static long modInv(long n) { return pow(n, MOD - 2); }\n\n\t// from /gold/modular\n\tprivate static long pow(long base, long exp) {\n\t\tif (exp < 0) { throw new IllegalArgumentException(\"exp must be nonnegative\"); }\n\t\tbase %= MOD;\n\t\tlong res = 1;\n\t\twhile (exp > 0) {\n\t\t\tif (exp % 2 == 1) { res = res * base % MOD; }\n\t\t\tbase = base * base % MOD;\n\t\t\texp /= 2;\n\t\t}\n\t\treturn res;\n\t}\n}\n"
 })
 })
 })]
 })]
 });
}
function MDXContent(props = {}) {
 const {wrapper: MDXLayout} = props.components || ({});
 return MDXLayout ? _jsx(MDXLayout, {
 ...props,
 children: _jsx(_createMdxContent, {
 ...props
 })
 }) : _createMdxContent(props);
}
return {
 frontmatter,
 default: MDXContent
};
function _missingMdxReference(id, component) {
 throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}

Info

CPPSection

JavaSection

LanguageSection

Implementation

Join the USACO Forum!