ACM-ICPC 2017 Asia Urumqi： H. Count Numbers（DP+矩阵快速幂优化）

40 阅读 0 评论 27 点赞

我是靠谱客的博主正直彩虹，最近开发中收集的这篇文章主要介绍ACM-ICPC 2017 Asia Urumqi： H. Count Numbers（DP+矩阵快速幂优化），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Now Alice wants to sum up all integers whose digit sum is exactly $a^b$ .

However we all know the number of this kind of integers are unlimited. So she decides to sum up all these numbers

whose each digit is non-zero.

Since the answer could be large, she only needs the remainder when the answer divided by a given integer .

Input

The input has several test cases and the first line contains the integer $(1 \leq t \leq 400)$ which is the number of test cases.

For each test case, a line consisting of three integers $(1 \leq a, b \leq 20)$ and $(2 \leq p \leq 1 0^^{9})$ describes the restriction of the digit sum and the given integer .

Output

For each test case, output a line with the required answer.

Here we provide an explanation of the following sample output. All integers satisfying the restriction in the input are and $1111$ . The sum of them all is and that is exactly the sample output.

样例输入

5
2 1 1000000
3 1 1000000
2 2 1000000
3 3 1000000
10 1 1000000

样例输出

题解：记 F[i]表示数位和为 i 的不含 0 整数有多少个，再记 G[i]表示数位和为 i 的不含 0 整数的和。

那么 F[i] = sum F[i-j]，G[i] = sum 10*G[i-j]+j*F[i-j]，其中 j 枚举了最低位的数字，并从 1 遍历到 9。不妨同时维护相邻的 9 个位置的值（共 18 个），则可以构造 18 阶矩阵 A，实现它的快速转移。整个问题的答案也对应了 A 的 a^b次幂。可以利用矩阵乘法的结合律实现它的快速计算。

F[8] F[7] F[6] F[5] F[4] F[3] F[2] F[1] F[0] G[8] G[7] G[6] G[5] G[4] G[3] G[2] G[1] G[0]

伴随矩阵A：

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

考虑到a^b可能非常大，就用了JAVA来写。

import java.util.*;
import java.math.*;
public class Main {
static long MOD;
static class lenka
{
long a[][]=new long[20][20];
lenka()
{
for(int i=0;i<18;i++)
{
for(int j=0;j<18;j++)a[i][j]=0;
}
}
}
static lenka cla(lenka a,lenka b)
{
lenka c=new lenka();
for(int i=0;i<18;i++)
{
for(int j=0;j<18;j++)
{
for(int k=0;k<18;k++)
{
c.a[i][j]+=a.a[i][k]*b.a[k][j]%MOD;
c.a[i][j]%=MOD;
}
}
}
return c;
}
static long POW(BigInteger n)
{
lenka a=new lenka();
lenka res=new lenka();
for(int i=0;i<18;i++)res.a[i][i]=1;
for(int i=0;i<9;i++)
{
a.a[i][0]=1;
a.a[i][9]=i+1;
}
for(int i=1;i<9;i++)
{
a.a[i-1][i]=1;
a.a[i+8][i+9]=1;
}
for(int i=9;i<18;i++)a.a[i][9]=10;
while(n.compareTo(BigInteger.ZERO)>0)
{
if(n.mod(new BigInteger("2")).compareTo(BigInteger.ONE)==0)res=cla(a,res);
a=cla(a,a);
n=n.divide(new BigInteger("2"));
}
long d[]={128,64,32,16,8,4,2,1,1,23817625,2165227,196833,17891,1625,147,13,1,0};
long ans=0;
for(int i=0;i<18;i++)
{
ans+=(d[i]%MOD)*res.a[i][17]%MOD;
ans%=MOD;
}
return ans;
}
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
while((T--)>0)
{
BigInteger a=cin.nextBigInteger();
int b=cin.nextInt();
MOD=cin.nextLong();
System.out.println(POW(a.pow(b)));
}
}
}