#PU1214. USACO 2022 February Contest, Platinum — Problem 3. Phone Numbers

    ID: 1399 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb22来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2022 February Contest, Platinum — Problem 3. Phone Numbers

USACO 2022 February Contest, Platinum — Problem 3. Phone Numbers

题目描述

Bessie has a new cell phone with nine buttons, laid out as follows: 123 456 789 Bessie is trying to type out a given phone number in a hurry, so she decides to save time by pressing multiple buttons at the same time with one of her hooves. Specifically, Bessie's hoof might press a single digit, two digits that share a side (for twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689). For example, if the phone number Bessie is trying to type is 123659874, she might attempt to save time by Pressing 1 and 2 at the same time. Pressing 3. Pressing 6, 5, 9, and 8 at the same time. Pressing 7 and 4 at the same time. Unfortunately, Bessie drastically overestimated her skill at performing this task - if Bessie's hoof pressess multiple buttons at the same time, then all of the digits will be typed in arbitrary order. So if Bessie attempts the above sequence of presses, she may end up typing 123596847 or 213659874 instead (or one of many other possibilities). Given a sequence of digits that Bessie has typed, count the number of phone numbers that she could have been trying to type modulo 109+710^9+7. Note: the time limit for this problem is 4s, twice the default.

输入格式

The first line contains TT (1≤T≤101\le T\le 10), the number of independent test cases to solve. The next TT lines each contain a nonempty string of the digits 1 through 9. It is guaranteed that the total length of these strings does not exceed 10510^5.

输出格式

For each test case, the number of phone numbers Bessie might have been trying to type modulo 109+710^9+7.

数据范围

In inputs 2-3, all phone numbers have length at most 88. In inputs 4-5, the phone number only contains 1, 2, and 3. In inputs 6-7, the phone number doesn't contain the digit 5. In inputs 8-9, the phone number only contains 5, 6, 8, and 9. In inputs 10-12, the sum of the string lengths does not exceed 10210^2. In inputs 13-15, the sum of the string lengths does not exceed 10310^3. In inputs 16-18, the sum of the string lengths does not exceed 10410^4. In inputs 19-21, no additional constraints. Problem credits: Nick Wu

样例

样例 1

5
1478
4455
5968
31313211
123659874
5
2
24
3
255
For the first case, Bessie might be trying to type any of the following five
phone numbers:
1478
1487
4178
4187
1748
For example, if Bessie was trying to type 4187, she might have tried pressing 1
and 4 at the same time and then tried pressing 7 and 8 at the same time.
For the third case, as the numbers form a square, Bessie might have been trying
to type any permutation of the input sequence.