Submission

Score: 60

User: august

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

Language: cpp

Time: 0.164 second

Submitted On: 2026-03-19 21:26:18

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

const int mx = 1e6+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);

        for (auto &x : p) {
            if (check > x && check % x == 0) 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;
}

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

    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[i] = true;
        }
    }

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

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

        int del=1;
        for (int i=0; i<67; 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';

    }
}