解题思路

本题要求利用正整数 $x$ 的所有十进制数位（卡片）重新排列，拼接成无前导零的整数，并统计其中能被 $k$ 整除的不同整数的个数。由于 $x$ 最多有 $15$ 个数位，直接生成所有排列的时间复杂度过高（阶乘级），需要使用状态压缩动态规划进行优化。

把 $x$ 的每一位看作一张独立的卡片，用二进制整数 $i$ 表示已经使用了哪些位置的卡片（ $1$ 表示已使用）。定义：

dp[i][j] = \text{使用集合 } i \text{ 中的卡片按某种顺序拼接，组成的整数模 } k \text{ 等于 } j \text{ 的方案数。}

题目内容

小 Z 有一组数字卡片，每张卡片上写有一个十进制数字，这些卡片原本按顺序组成了正整数 $x$ 。小 Z 希望用所有卡片（必须全部使用）重新拼接成不同的整数，且不允许产生前导零。请你帮忙计算：在拼接出的所有不同整数中，有多少个能够被给定的整数 $k$ 整除？

注意：相同的整数只算一次。

约束： $x$ 的十进制表示长度不超过 $15$ （即 $1 \le x \le 10^{15}$ ）， $k$ 满足 $1 \le k \le 100$ 。