bzoj#P1072. [SCOI2007]排列perm

[SCOI2007]排列perm

题目描述

给一个数字串 ss 和正整数 dd, 统计 ss 有多少种不同的排列能被 dd 整除(可以有前导 00)。例如 1234341234349090 种排列能被 22 整除,其中末位为 22 的有 3030 种,末位为 44 的有 6060 种。

输入格式

输入第一行是一个整数 TT,表示测试数据的个数。

接下来 TT 行,每行包含两个整数 ssdd,中间用空格隔开。ss 保证只包含数字 0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9

输出格式

每个数据仅一行,表示能被 dd 整除的排列的个数。

7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29
1
3
3628800
90
3
6
1398

提示

100%100\% 的数据满足:ss 的长度不超过 10101d1031\le d\le 10^31T151\le T\le 15

在前三个例子中,排列分别有 1,3,36288001,3,3628800 种,它们都是 11 的倍数。

题目来源

没有写明来源