#P13046. [GCJ 2021 Finals] Divisible Divisions

    ID: 12847 Type: RemoteJudge 60000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划 DP数学2021数论中国剩余定理 CRTGoogle Code Jam

[GCJ 2021 Finals] Divisible Divisions

题目描述

We have a string S\mathbf{S} consisting of decimal digits. A division of S\mathbf{S} is created by dividing S\mathbf{S} into contiguous substrings. For example, if S\mathbf{S} is 0145217, two possible divisions are 014 5 21 7 and 0 14 52 17. Each digit must be used in exactly one substring, and each substring must be non-empty. If S\mathbf{S} has LL digits, then there are exactly 2L12^{L-1} possible divisions of it.

Given a positive integer D\mathbf{D}, a division of S\mathbf{S} is called divisible by D\mathbf{D} if for every pair of consecutive substrings, at least one of the integers they represent in base 10 is divisible by D\mathbf{D}. If D=7\mathbf{D}=7, the first example division above is divisible because 014, 21, and 7 represent integers divisible by 7. The second example division is not divisible because 52 and 17 are consecutive substrings and neither represents an integer divisible by 7. Dividing 0145217 as 0145217 is divisible by any D\mathbf{D} because there are no pairs of consecutive substrings.

Given S\mathbf{S} and D\mathbf{D}, count how many divisions of S\mathbf{S} exist that are divisible by D\mathbf{D}. Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+710^{9}+7 (10000000071000000007).

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} lines follow. Each line represents a test case with a string of digits S\mathbf{S} and a positive integer D\mathbf{D}, as mentioned above.

输出格式

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the number of different divisions of S\mathbf{S} that are divisible by D\mathbf{D}, modulo the prime 109+710^{9}+7 (10000000071000000007).

3
0145217 7
100100 10
5555 12
Case #1: 16
Case #2: 30
Case #3: 1

提示

Sample Explanation

In Sample Case #1, all 1616 divisible divisions of S\mathbf{S} are:

  • 0145217,
  • 0 145217,
  • 0 14 5217,
  • 0 14 5 217,
  • 0 14 5 21 7,
  • 0 14 521 7,
  • 0 145 217,
  • 0 145 21 7,
  • 0 14521 7,
  • 014 5217,
  • 014 5 217,
  • 014 5 21 7,
  • 014 521 7,
  • 0145 217,
  • 0145 21 7, and
  • 014521 7.

In Sample Case #2, there are 25=322^{5}=32 ways to divide in total. To get two consecutive substrings to not be divisible by 10, we need both of them to not end in 0. The only 2 ways of doing that are 1 001 001 \ 001 \ 00 and 1 001 0 01 \ 001 \ 0 \ 0, which means the other 30 divisions of S\mathbf{S} are divisible by 10.

In Sample Case #3, no possible substring represents an even integer, which in turn means it is not divisible by 12. Therefore, the only way to not have two consecutive substrings that are not divisible by 12 is to not have two consecutive substrings at all, which can be done in only 1 way: 5555.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 1D1061 \leq \mathbf{D} \leq 10^{6}.

Test Set 1 (10 Pts, Visible Verdict)

  • 11 \leq the length of S1000\mathbf{S} \leq 1000.

Test Set 2 (35 Pts, Hidden Verdict)

  • 11 \leq the length of S105\mathbf{S} \leq 10^{5}.