Submission

Score: 60

User: august

Problemset: การเรียงสับเปลี่ยน

Language: cpp

Time: 0.060 second

Submitted On: 2026-03-20 09:01:46

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mx = 1e7+5;
bool prime[mx];
vector<int> p;
int m,n;


int fnd(string &a, vector<bool> &vst, string &s) {
    if (a.size() >= n) {
        int check = stoi(a);

        if (prime[check]) return 0;
        //cout<< a<< ' ';
        return 1;
    }   
    

    int sm=0;
    for (int i=0; i<n; i++) {
        if (vst[i]) continue;
        string tem=a+s[i];

        vst[i] = true;
        sm+=fnd(tem, vst, s);
        vst[i] = false;
    }
    return sm;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>> m>> n;

    prime[0] = prime[1] = true;
    for (int i=2; i*i<mx; i++) {
        if (prime[i]) continue;
        p.push_back(i);
        for (int j=i*i; j<mx; j+=i) {
            prime[j] = true;
        }
    }

    while (m--) {
        string s;
        cin>> s;

        while (s.size() < n) s = '0'+s;

        vector<bool> vst(n, false);
        vector<int> cnt(256, 0);
        for (auto &x : s) cnt[x]++;

        int del=1;
        for (int i=48; i<58; i++) if (cnt[i]!=0) {
            int mul=1;
            while (cnt[i] != 1) {
                mul*=cnt[i]--;
            }
            del*=mul;
        }

        string tem = "";
    
        cout<< fnd(tem, vst, s)/del<< '\n';

    }
}