OI题库

Bulls and Cows [Neal Wu, 2008]

Farmer John wants to position N (1 <= N <= 100,000) cows and bulls
in a single row to present at the annual fair.

FJ has observed that the bulls have been quite pugnacious lately;
if two bulls too close together in the line, they will argue and
begin to fight, ruining the presentation. Ever resourceful, FJ
calculated that any two bulls must have at least K (0 <= K < N)
cows between them in order to avoid a fight.

FJ would like you to help him by counting the number of possible
sequences of N bulls and cows that avoid any fighting. FJ considers
all bulls the to be the same and all cows to be the same; thus, two
sequences are only different if they have different kinds of cattle
in some position.

PROBLEM NAME: bullcow

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

SAMPLE INPUT (file bullcow.in):

4 2

INPUT DETAILS:

FJ wants a row of 4 cattle, but any two bulls must have at least
two cows in between them.

OUTPUT FORMAT:

* Line 1: A single integer representing the number of ways FJ could
        create such a sequence of cattle. Since this number can be
        quite large, output the result modulo 5,000,011.

SAMPLE OUTPUT (file bullcow.out):

6

OUTPUT DETAILS:

The following are the six possible sequences FJ could create (note that 'C'
stands for cow and 'B' stands for bull):
CCCC
BCCC
CBCC
CCBC
CCCB
BCCB