Submission

Score: 60

User: krittaphot

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

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-04 15:34:18

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

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

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,unordered_set<int> &seen){
    if(depth==n){
        if (prime[value] && !seen.count(value)) {
    		seen.insert(value);
    		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'),seen);
        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);
        unordered_set<int> seen;
        ans=0;

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