洛谷P4163 [SCOI2007]排列 题解

题目链接：P4163 [SCOI2007]排列

题意：

给一个数字串 $s$ 和正整数 $d$ ，统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$）。例如 $123434$ 有 $90$ 种排列能被 $2$ 整除，其中末位为 $2$ 的有 $30$ 种，末位为 $4$ 的有 $60$ 种。

输入格式：

输入第一行是一个整数 $T$，表示测试数据的个数，以下每行一组 $s$ 和 $d$，中间用空格隔开。$s$ 保证只包含数字 $0,1,2,3,4,5,6,7,8,9$。

输出格式：

每个数据仅一行，表示能被 $d$ 整除的排列的个数。

数据范围：

$s$ 的长度不超过 $10$，$1\le d\le 1000$，$1\le T\le 15$。

直接暴力不知道卡不卡得过，我感觉不行。

这道题我们可以把原字符串中的字符看作一个可重集然后状压dp。

设 $f_{S,j}$ 表示用了集合 $S$ 的数字，且此时模 $d$ 的值为 $j$ 时的方案数，则（下面的 $\uparrow$ 表示 += ）

$$\begin{aligned} \large f_{S \cup\{k\},(10 j+k) \bmod d} \uparrow f_{S, j} && (k \not\in S) \end{aligned}$$

算重的问题很简单，组合数学嘛，只有把最后的 $f$ 除以「每个数的出现次数的阶乘的乘积」就好了

时间复杂度 $\mathcal{O}(2^{|s|}d)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

char s[15];
int n,d,cnt[15],f[2098][1050],fac[15];
void clear()
{
    memset(cnt, 0, sizeof(cnt));
    memset(f, 0, sizeof(f));
}
void solve()
{
    cin >> s >> d; clear();
    for(n = 0; s[n]; n++) ++cnt[s[n] &= 15];
    int mx = 1 << n; f[0][0] = 1;
    for(int i = 0,ti,tj; i < mx; i++)
        for(int j = 0; j < d; j++) if(f[i][j])
            for(int k = 0; k < n; k++) if((ti = i | (1 << k)) != i)
                { tj = (j * 10 + s[k]) % d; f[ti][tj] += f[i][j]; }
    int c = 1; for(int i = 0; i < 10; i++) c *= fac[cnt[i]];
    cout << (f[mx - 1][0] / c) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fac[0] = 1;
    for(int i = 1; i <= 11; i++) fac[i] = fac[i - 1] * i;
    int Q; cin >> Q; while(Q--) { solve(); }
    return 0;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/lydsy1072.html