Submission

Score: 60

User: Imorange

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

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-04 19:30:03

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

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

vector<char> num;
vector<char> used;

int n;
int ans;

void sieve() {
    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;
        }
    }
}

void dfs(int depth, int value){
    if(depth == n){
        if(prime[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'));
        used[i] = 0;
    }
}

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

    int m;
    cin >> m >> n;

    sieve();

    while(m--){
        string s; 
        cin >> s;
        num.assign(s.begin(), s.end());
        sort(num.begin(), num.end());
        used.assign(n, 0);
        ans = 0;

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