#PU1070. USACO 2020 December Contest, Platinum — Problem 3. Cowmistry
USACO 2020 December Contest, Platinum — Problem 3. Cowmistry
USACO 2020 December Contest, Platinum — Problem 3. Cowmistry
题目描述
Bessie has been procrastinating on her cow-mistry homework and now needs your help! She needs to create a mixture of three different cow-michals. As all good cows know though, some cow-michals cannot be mixed with each other or else they will cause an explosion. In particular, two cow-michals with labels and can only be present in the same mixture if ().
输入格式
The first line contains two integers and . Each of the next lines contains two space-separated integers and . It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, for each .
输出格式
The number of mixtures of three different cow-michals Bessie can create, modulo .
数据范围
Test cases 3-4 satisfy . Test cases 5-6 satisfy for some integer . Test cases 7-11 satisfy . Test cases 12-16 satisfy . Test cases 17-21 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
1 13
0 199
4280
We can split the chemicals into 13 groups that cannot cross-mix: $(0\ldots 15)$,
$(16\ldots 31)$, $\ldots$ $(192\ldots 199)$. Each of the first twelve groups
contributes $352$ unique mixtures and the last contributes $56$ (since all
$\binom{8}{3}$ combinations of three different cow-michals from
$(192\ldots 199)$ are okay), for a total of
$352\cdot 12+56=4280$.
样例 2
6 147
1 35
48 103
125 127
154 190
195 235
240 250
267188
提示
integers and . This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,
Bessie has () boxes of cow-michals and the -th box contains cow-michals labeled through inclusive . No two boxes have any cow-michals in common. She wants to know how many unique mixtures of three different cow-michals she can create. Two mixtures are considered different if there is at least one cow-michal present in one but not the other. Since the answer may be very large, report it modulo .