Submission

Score: 60

User: krittaphot

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

Language: cpp

Time: 0.019 second

Submitted On: 2026-03-04 15:29:38

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

static const int LIM = 1000000;
vector<bool> prime(LIM+1, true);
vector<char> num;
vector<char> used;
vector<char> seen; 

void seive() {
    prime[0]=prime[1]=false;
    for(int i=2;i*i<=LIM;i++){
        if(prime[i]){
            for(int j=i*i;j<=LIM;j+=i) prime[j]=false;
        }
    }
}

int n;
int ans;

void dfs(int depth, int value){
    if(depth==n){
        if(prime[value] && !seen[value]){
            seen[value]=1;
            ans++;
        }
        return;
    }
    for(int i=0;i<n;i++){
        if(used[i]) continue;

        
        if(i>0 && num[i]==num[i-1] && !used[i-1]) continue;

        used[i]=1;
        dfs(depth+1, value*10 + (num[i]-'0'));
        used[i]=0;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m >> n;
    seive();

    while(m--){
        string s; cin >> s;
        num.assign(s.begin(), s.end());
        sort(num.begin(), num.end());

        used.assign(n, 0);
        seen.assign(LIM+1, 0);
        ans=0;

        dfs(0, 0);
        cout << ans << "\n";
    }
}