作者： chenchen

It's the year 3000 , and Bessie became the first cow in space! During her journey between the stars, she found a number line with N (2≤N≤5⋅10⁵) points, numbered from 1 to N. All points are initially colored white. She can perform the following operation any number of times.

Choose a position i within the number line and a positive integer x. Then, color all the points in the interval [i,i+x−1] red and all points in [i+x , i+2x−1]
blue. All chosen intervals must be disjoint (i.e. no points in [ i, i+2x−1]
can be already colored red or blue). The entire interval must also fall within the number line (i.e. 1≤i≤i+2x−1≤N).

Farmer John gives Bessie a string s of length N consisting of characters R, B
, and X. The string represents Farmer John's color preferences for each point: s_i =R means the i'th point must be colored red, s_i =B means the i'th point must be colored blue, and s_i =X means there is no constraint on the color for the i'th point.

Help Bessie count the number of distinct ways for the number line to be colored while satisfying Farmer John's preferences. Two colorings are different if there is at least one corresponding point with a different color. Because the answer may be large, output it modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains an integer N.

The following line contains string s.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of distinct ways for the number line to be colored while satisfying Farmer John's preferences modulo 10⁹+7.

SAMPLE INPUT:

6
RXXXXB

SAMPLE OUTPUT:

5

Bessie can choose i=1,x=1(i.e. color point 1 red and point 2 blue) and i=3,x=2
(i.e. color points 3,4 red and points 5,6 blue) to produce the coloring RBRRBB.

The other colorings are RRBBRB, RBWWRB, RRRBBB, and RBRBRB.

SAMPLE INPUT:

6
XXRBXX

SAMPLE OUTPUT:

6

The six colorings are WWRBWW, WWRBRB, WRRBBW, RBRBWW, RBRBRB, and RRRBBB.

SAMPLE INPUT:

12

XBXXXXRXRBXX

SAMPLE OUTPUT:

18

SCORING:

Input 4: N≤500
Inputs 5-6: N≤10⁴
Inputs 7-13: All but at most 100 characters in s are X.
Inputs 14-23: No additional constraints

Problem credits: Chongtian Ma, Alex Liang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's N (1≤N≤10⁵ ) cows have been arranged into a line. The i
th cow has label a_i (1≤a_i ≤N). A group of cows can form a friendship group if they all have the same label and each cow is within x cows of all the others in the group, where x is an integer in the range [1,N]. Every cow must be in exactly one friendship group.

For each x from 1 to N , calculate the minimum number of friendship groups that could have formed.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line consists of an integer N.

The next line contains a₁...a_N , the labels of each cow.

OUTPUT FORMAT (print output to the terminal / stdout):

For each x from 1 to N , output the minimum number of friendship groups for that x on a new line.

SAMPLE INPUT:

9
1 1 1 9 2 1 2 1 1

SAMPLE OUTPUT:

7
5
4
4
4
4
4
3
3

Here are examples of how to assign cows to friendship groups for x=1
and x=2 in a way that minimizes the number of groups. Each letter corresponds to a different group.

SCORING:

Inputs 2-3: N≤5000
Inputs 4-7: a_i≤10 for all i
Inputs 8-11: No label appears more than 10 times.
Inputs 12-20: No additional constraints.

Problem credits: Chongtian Ma

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Moo! You are given an integer N (2≤N≤2000). Consider all permutations p=[p₀,p₁,…,p_N−1]of [0,1,2…,N−1]. Let f(p)=|p_i−p_i+1|denote the minimum absolute difference between any two consecutive elements of p. and let S denote the set of all p that achieve the maximum possible value of f(p).

You are additionally given K (0≤K≤N) constraints of the form p_i=j (0≤i, j<N). Count the number of permutations in S satisfying all constraints, modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤TN≤2⋅10⁴) and N, meaning that you will need to solve T independent test cases, each specified by a different set of constraints.

Each test case starts with K, followed by K lines each containing i and j. It is guaranteed that

The same i does not appear more than once within the same test case.
The same j does not appear more than once within the same test case.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, the answer modulo 10⁹+7 on a separate line.

SAMPLE INPUT:

3 4
0
1
1 1
2
0 2
2 3

SAMPLE OUTPUT:

2
0
1

The maximum possible value of f (p) is 2, and S={[2,0,3,1],[1,3,0,2]}.

SAMPLE INPUT:

9 11
2
0 5
6 9
3
0 5
6 9
1 0
4
0 5
6 9
1 0
4 7
5
0 5
6 9
1 0
4 7
2 6
6
0 5
6 9
1 0
4 7
2 6
9 3
7
0 5
6 9
1 0
4 7
2 6
9 3
5 2
8
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
9
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
10
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
8 10

SAMPLE OUTPUT:

6
6
1
1
1
1
1
1
1

p=[5,0,6,1,7,2,9,4,10,3,8] should be counted for all test cases.

SAMPLE INPUT:

10 11
0
1
3 8
2
3 8
5 7
3
3 8
5 7
4 2
4
3 8
5 7
4 2
10 6
5
3 8
5 7
4 2
10 6
8 10
6
3 8
5 7
4 2
10 6
8 10
1 9
7
3 8
5 7
4 2
10 6
8 10
1 9
7 5
8
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
9
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
6 0

SAMPLE OUTPUT:

160
20
8
7
2
1
1
1
1
1

p=[4,9,3,8,2,7,0,5,10,1,6]should be counted for all test cases.

SAMPLE INPUT:

5 987
3
654 321
543 210
432 106
2
654 321
543 210
1
654 321
1
0 493
0

SAMPLE OUTPUT:

0
538184948
693625420
932738155
251798971
Make sure to output the answer modulo 10⁹+7.

SCORING:

Input 5: N=15
Input 6: N=2000
Inputs 7-9: For all test cases, the constraint p₀=⌊N/2⌋ appears.
Inputs 10-13: For all test cases, there exists some constraint p_i =j with j equal to ⌊N/2⌋.
Inputs 14-20: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has a string of length N(1≤N≤3⋅10⁵) consisting solely of the characters M and O. For each position i of the string, there is a cost c_i to change the character at that position to the other character (1≤c_i≤10⁸).

Bessie thinks the string will look better if it contains more moos of length L
(1≤L≤min(N,3)). A moo of length L is an M followed by L−1 Os.

For each positive integer k from 1 to ⌊N/L⌋ inclusive, compute the minimum cost to change the string to contain at least k substrings equal to a moo of length L.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains L and N.

The next line contains Bessie's length-N string, consisting solely of Ms and Os.

The next line contains space-separated integers c₁…c_N.

OUTPUT FORMAT (print output to the terminal / stdout):

Output ⌊N/L⌋ lines, the answer for each k in increasing order.

SAMPLE INPUT:

1 4
MOOO
10 20 30 40

SAMPLE OUTPUT:

0
20
50
90

SAMPLE INPUT:

3 4
OOOO
50 40 30 20

SAMPLE OUTPUT:

40

SAMPLE INPUT:

2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

SAMPLE OUTPUT:

0
0
0
0
0
12851185
35521020
60232254
99881782
952304708

SAMPLE INPUT:

3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

SAMPLE OUTPUT:

0
0
0
44743602
119332891
207066974

SCORING:

Input 5: L=3,N≤5000
Input 6: L=1
Inputs 7-10: L=2
Inputs 11-18: L=3

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's N (1≤N≤5⋅10⁵) cows are each assigned a bitstring of length K that is not all zero (1≤K≤20). Different cows may be assigned the same bitstring.

The Jaccard similarity of two bitstrings is defined as the number of set bits in their bitwise intersection divided by the number of set bits in their bitwise union. For example, the Jaccard similarity of the bitstrings 11001 and 11010 would be 2/4.

For each cow, output the sum of her bitstring's Jaccard similarity with each of the N cows' bitstrings including her own, modulo 10⁹+7. Specifically, if the sum is equal to a rational number a/b where a and b are integers sharing no common factors, output the unique integer x in the range [0,10⁹+7) such that bx−a is divisible by 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and K.

The next N lines each contain an integer i∈(0,2^K), representing a cow associated with the length-K binary representation of i.

INPUT FORMAT (input arrives from the terminal / stdin):

Output the sum modulo 10⁹+7 for each cow on a separate line.

SAMPLE INPUT:

4 2
1
1
2
3

SAMPLE OUTPUT:

500000006
500000006
500000005
500000006

The cows are associated with the following bitstrings: [01,01,10,11].

For the first cow, the sum is  sim(1,1)+sim(1,1)+sim(1,2)+sim(1,3)=1+1+0+1/2≡500000006(mod 10⁹+7).

The second cow's bitstring is the same as the first cow's, so her sum is the same as above.

For the third cow, the sum is

sim(2,1)+sim(2,1)+sim(2,2)+sim(2,3)=0+0+1+1/2≡500000005(mod 10⁹+7).

SCORING:

Inputs 2-15: There will be two test cases for each of K∈{10,15,16,17,18,19,20}.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划