IOIString
SRM 452 · 2009-11-05 · by rng_58
SRM 452 · 2009-11-05 · by rng_58 · Math
Problem Statement
Problem Statement
A string s is called an IOI string if it satisfies the following two conditions:
String[] mask. Concatenate the elements of mask to get one string. Each '?' character in mask can be replaced with either 'I' or 'O'.
Return the number of different IOI strings that can be formed, modulo 1,000,000,007 (1E9+7).
- s contains only uppercase 'I' and uppercase 'O' letters.
- There is at least one pair of non-negative integers (a,b) such that the a-th (0-indexed) character of s is 'I', the (a+b)-th character is 'O', and the (a+2*b)-th character is 'I'.
Return the number of different IOI strings that can be formed, modulo 1,000,000,007 (1E9+7).
Constraints
- mask will contain between 1 and 50 elements, inclusive.
- Each element of mask will contain between 1 and 50 characters, inclusive.
- Each character in mask will be uppercase 'I' or uppercase 'O' or '?'.
Examples
0)
{"IO?"}
Returns: 1
Two strings can be formed here : "IOI" and "IOO". Only "IOI" is an IOI string.
1)
{"????"}
Returns: 4
There are four IOI strings of length 4 : "IIOI", "IOII", "IOIO", and "OIOI".
2)
{"?II"}
Returns: 0
No IOI string can be formed from "?II".
3)
{"I??O??I"}
Returns: 16
Character 0 is 'I', character 3 is 'O', and character 6 is 'I'. Therefore, all possible strings are IOI strings here.
4)
{"???I???????O???","???????????O??IO????????I???"}
Returns: 438952513
Don't forget to concatenate strings.
Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class IOIString with a public method int countIOIs(vector<string> mask) · 75 test cases · 2 s / 256 MB per case