小强向你请教了一个奇妙的数学题:给定两个数n和m,小强可以通过对n里面的数位进行重新排列。

现在小强请你帮他计算出经过重新排列后所得到的数中满足不含有前导零并且能够整除m的数字有
多少个?

注意:相同的数只算一次

n < 1e15
m < 100

这题是SCOI2007魔改了条件

原题的方案里可以包含前导零。其实只需要判断一下如果当前状态是全0则表示有前导零的状态，不进行转移即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 16, M = 110;
ll n, m;
ll f[1 << N][M];
vector<int> v;
bool vis[10];
int ze = 0;

int main()
{
    // time_t startt = clock();

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int T; 
    T = 1;
    while(T--)  
    {
        cin >> n >> m;
        while(n) v.push_back(n % 10), n /= 10;
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++) if(v[i] == 0) ze++;

        f[0][0] = 1;
        for(int i = 0; i < 1 << v.size(); i++)
        {
            memset(vis, 0, sizeof vis);
            for(int j = 0; j < v.size(); j++)
            {
                if(i & (1 << j)) continue;
                if(vis[v[j]]) continue;
                int mask = i | (1 << j);
                if(mask < (1 << ze)) continue;
                vis[v[j]] = 1;
                for(int k = 0; k < m; k++)
                {
                    f[mask][(k * 10 + v[j]) % m] += f[i][k];  
                }        
            }
        }
        cout << f[(1 << v.size()) - 1][0] << endl;
    }
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}