fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. static const int MOD = 998244353;
  5.  
  6. // Sieve up to 99999
  7. vector<bool> sievePrimes(int N) {
  8.     vector<bool> isPrime(N + 1, true);
  9.     isPrime[0] = isPrime[1] = false;
  10.     for (int i = 2; i * 1LL * i <= N; ++i) if (isPrime[i]) {
  11.         for (int j = i * i; j <= N; j += i) isPrime[j] = false;
  12.     }
  13.     return isPrime;
  14. }
  15.  
  16. // Convert integer to zero-padded string of length n
  17. string toZ(int x, int n) {
  18.     string s(n, '0');
  19.     for (int i = n - 1; i >= 0; --i) {
  20.         s[i] = char('0' + (x % 10));
  21.         x /= 10;
  22.     }
  23.     return s;
  24. }
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(false);
  28.     cin.tie(nullptr);
  29.  
  30.     // Precompute prime masks and candidate strings
  31.     const int LIM = 99999;
  32.     auto isPrime = sievePrimes(LIM);
  33.     // cand[n][d] -> vector of strings (length n) that are primes and start with digit d
  34.     array<array<vector<string>, 10>, 6> cand; // index n in [0..5], we’ll use 1..5
  35.  
  36.     for (int n = 1; n <= 5; ++n) {
  37.         int up = 1;
  38.         for (int i = 0; i < n; ++i) up *= 10;
  39.         for (int x = 0; x < up; ++x) {
  40.             if (!isPrime[x]) continue;
  41.             string s = toZ(x, n);
  42.             cand[n][s[0]-'0'].push_back(s);
  43.         }
  44.     }
  45.  
  46.     int t;
  47.     if (!(cin >> t)) return 0;
  48.     while (t--) {
  49.         string p;            // p is guaranteed prime and without leading zero
  50.         cin >> p;
  51.         int n = (int)p.size();
  52.  
  53.         // rows[1..n], 1-indexed for clarity; row 1 fixed to p
  54.         vector<string> rows(n + 1);
  55.         rows[1] = p;
  56.  
  57.         // DFS with pruning
  58.         function<long long(int)> dfs = [&](int k) -> long long {
  59.             if (k > n) return 1;          // all rows chosen
  60.             if (k == 1) return dfs(2);    // row 1 already fixed
  61.  
  62.             int lead = p[k-1] - '0';      // column 1 equals digit p_k due to symmetry
  63.             long long ways = 0;
  64.  
  65.             for (const string& s : cand[n][lead]) {
  66.                 // s must match previously fixed symmetric constraints:
  67.                 // for all j < k: s[j-1] == rows[j][k-1]
  68.                 bool ok = true;
  69.                 for (int j = 1; j < k; ++j) {
  70.                     if (s[j-1] != rows[j][k-1]) { ok = false; break; }
  71.                 }
  72.                 if (!ok) continue;
  73.                 rows[k] = s;
  74.                 ways += dfs(k + 1);
  75.                 if (ways >= MOD) ways -= MOD;
  76.             }
  77.             return ways % MOD;
  78.         };
  79.  
  80.         cout << dfs(1) % MOD << '\n';
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
1
13
stdout 
2
https://ideone.com/pcAnkS
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!