fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 998244353;
  4.  
  5. vector<bool> isPrime;
  6. vector<vector<vector<int>>> primesByLen;
  7. vector<vector<vector<vector<int>>>> cand; 
  8. // cand[len][k][prefix] = list các index của prime (độ dài len) có prefix độ dài k = prefix
  9.  
  10. void sieve(int N=100000){
  11.     isPrime.assign(N+1,true);
  12.     isPrime[0]=isPrime[1]=false;
  13.     for(int i=2;i*i<=N;i++) if(isPrime[i])
  14.         for(int j=i*i;j<=N;j+=i) isPrime[j]=false;
  15. }
  16.  
  17. vector<int> toDigits(int x,int n){
  18.     vector<int>d(n);
  19.     for(int i=n-1;i>=0;i--){ d[i]=x%10; x/=10; }
  20.     return d;
  21. }
  22.  
  23. int n;
  24. vector<vector<int>> board;
  25. long long ans;
  26.  
  27. void dfs(int row){
  28.     if(row==n){ ans=(ans+1)%MOD; return; }
  29.  
  30.     // tạo prefix (row chữ số đầu tiên)
  31.     int prefix=0;
  32.     for(int j=0;j<row;j++) prefix = prefix*10 + board[j][row];
  33.  
  34.     // duyệt ứng viên từ cand
  35.     for(int idx : cand[n][row][prefix]){
  36.         const auto &dig = primesByLen[n][idx];
  37.         bool ok=true;
  38.         vector<pair<int,int>> changed;
  39.  
  40.         for(int j=row;j<n;j++){
  41.             if(board[row][j]!=-1 && board[row][j]!=dig[j]){ ok=false; break; }
  42.             if(board[j][row]!=-1 && board[j][row]!=dig[j]){ ok=false; break; }
  43.         }
  44.         if(!ok) continue;
  45.  
  46.         for(int j=row;j<n;j++){
  47.             if(board[row][j]==-1){ board[row][j]=dig[j]; changed.push_back({row,j}); }
  48.             if(board[j][row]==-1){ board[j][row]=dig[j]; changed.push_back({j,row}); }
  49.         }
  50.  
  51.         dfs(row+1);
  52.  
  53.         for(auto [x,y]:changed) board[x][y]=-1;
  54.     }
  55. }
  56.  
  57. int main(){
  58.     ios::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.  
  61.     sieve();
  62.  
  63.     primesByLen.assign(6,{});
  64.     // collect primes by length
  65.     for(int x=2;x<100000;x++) if(isPrime[x]){
  66.         int len = to_string(x).size();
  67.         primesByLen[len].push_back(toDigits(x,len));
  68.     }
  69.  
  70.     // build cand
  71.     cand.assign(6,{});
  72.     for(int len=1; len<=5; len++){
  73.         cand[len].assign(len+1,{});
  74.         for(int k=0;k<=len;k++){
  75.             cand[len][k].assign((int)pow(10,k),{});
  76.         }
  77.         for(int i=0;i<(int)primesByLen[len].size();i++){
  78.             int prefix=0;
  79.             cand[len][0][0].push_back(i);
  80.             for(int k=1;k<=len;k++){
  81.                 prefix = prefix*10 + primesByLen[len][i][k-1];
  82.                 cand[len][k][prefix].push_back(i);
  83.             }
  84.         }
  85.     }
  86.  
  87.     int T; cin>>T;
  88.     while(T--){
  89.         int p; cin>>p;
  90.         n = to_string(p).size();
  91.         board.assign(n,vector<int>(n,-1));
  92.         auto d = toDigits(p,n);
  93.  
  94.         for(int j=0;j<n;j++){
  95.             board[0][j]=d[j];
  96.             board[j][0]=d[j];
  97.         }
  98.  
  99.         ans=0;
  100.         dfs(1);
  101.         cout<<ans%MOD<<"\n";
  102.     }
  103. }
  104.  
Success #stdin #stdout 0.01s 7616KB
comments (?)
stdin
copy 
14
4441
479
4987
233
7741
7127
4127
5689
5483
6053
1637
7901
2063
71
stdout
copy 
1376
25
813
30
1278
1185
1185
1389
1585
0
954
0
0
4
https://ideone.com/U8LPwx
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!