洛谷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