fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MOD 1000000007
  5.  
  6. // Trả về true nếu hai ký tự a và b cùng loại phép (cùng chữ số hoặc cùng '+')
  7. bool check(char a, char b) {
  8.     if ((a >= '0' && a <= '9') && (b >= '0' && b <= '9')) return true;
  9.     if (a == '+' && b == '+') return true;
  10.     return false;
  11. }
  12.  
  13. void solve() {
  14.     int n;
  15.     cin >> n;
  16.     vector<char> bessie(n+1), elsie(n+1);
  17.     for (int i = 1; i <= n; i++) cin >> bessie[i];
  18.     for (int i = 1; i <= n; i++) cin >> elsie[i];
  19.  
  20.     // Xác định breakPoint riêng cho từng chuỗi (lần '0' cuối cùng)
  21.     int bpB = 0, bpE = 0;
  22.     for (int i = n; i >= 1; i--) {
  23.         if (bessie[i] == '0' && bpB == 0) bpB = i;
  24.         if (elsie[i] == '0' && bpE == 0)   bpE = i;
  25.     }
  26.     if (bpB == 0) bpB = 1;
  27.     if (bpE == 0) bpE = 1;
  28.  
  29.     // Tạo các chuỗi đã loại bỏ ×1 và cắt từ breakPoint
  30.     string B = "@", E = "@";
  31.     for (int i = n; i >= bpB; i--) {
  32.         if (bessie[i] != '1') B.push_back(bessie[i]);
  33.     }
  34.     for (int i = n; i >= bpE; i--) {
  35.         if (elsie[i] != '1') E.push_back(elsie[i]);
  36.     }
  37.     reverse(B.begin() + 1, B.end());
  38.     reverse(E.begin() + 1, E.end());
  39.  
  40.     int szB = (int)B.size() - 1;
  41.     int szE = (int)E.size() - 1;
  42.  
  43.     // DP[i][j][k]: số cách xen i ký tự B và j ký tự E,
  44.     // với k=0 là cuối cùng là B, k=1 là cuối cùng là E, và không vi phạm.
  45.     vector<vector<array<int,2>>> dp(szB+1,
  46.         vector<array<int,2>>(szE+1, {0,0}));
  47.  
  48.     dp[0][0][0] = dp[0][0][1] = 1;
  49.  
  50.     for (int i = 0; i <= szB; i++) {
  51.         for (int j = 0; j <= szE; j++) {
  52.             long long curB = dp[i][j][0];
  53.             long long curE = dp[i][j][1];
  54.  
  55.             // 1) Thêm một ký tự của Elsie → k = 1
  56.             if (j + 1 <= szE) {
  57.                 // E sau B luôn OK
  58.                 dp[i][j+1][1] = (dp[i][j+1][1] + curB) % MOD;
  59.                 // E sau E luôn OK
  60.                 dp[i][j+1][1] = (dp[i][j+1][1] + curE) % MOD;
  61.             }
  62.  
  63.             // 2) Thêm một ký tự của Bessie → k = 0
  64.             if (i + 1 <= szB) {
  65.                 // B sau B luôn OK
  66.                 dp[i+1][j][0] = (dp[i+1][j][0] + curB) % MOD;
  67.                 // B sau E: chỉ cấm khi cùng loại và j>0
  68.                 if (j == 0 || !check(B[i+1], E[j])) {
  69.                     dp[i+1][j][0] = (dp[i+1][j][0] + curE) % MOD;
  70.                 }
  71.             }
  72.         }
  73.     }
  74.  
  75.     int ans = (dp[szB][szE][0] + dp[szB][szE][1]) % MOD;
  76.     cout << ans << "\n";
  77. }
  78.  
  79. int main() {
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(nullptr);
  82.  
  83.     int t;
  84.     cin >> t;
  85.     while (t--) {
  86.         solve();
  87.     }
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
stdout
copy 
2
6
18
18
https://ideone.com/pN68Rx
language:
C++14 (gcc 8.3)
created:
7 days 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!