fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <map>
  7. using namespace std;
  8.  
  9.  
  10. int main() {
  11.     int p;
  12.     cin >> p;
  13.     while(p--){
  14.         int n,i,j,ans=0;
  15.         bool ok;
  16.         cin >> n;
  17.         string a,b;
  18.         cin >> a >> b;
  19.         map<string,bool> use;
  20.         string z1[606],z2[606],b1[606],b2[606],s1[606][606],s2[606][606],t1[606][606],t2[606][606];
  21.         z1[0]+=a[0];
  22.         z1[0]+=b[0];
  23.         z2[0]+=b[0];
  24.         z2[0]+=a[0];
  25.         for(i=1;i<n;i++){
  26.             z1[i]+=a[i];
  27.             z1[i]+=z1[i-1];
  28.             z1[i]+=b[i];
  29.             z2[i]+=b[i];
  30.             z2[i]+=z2[i-1];
  31.             z2[i]+=a[i];
  32.         }
  33.         for(i=n-1;i>=0;i--){
  34.             b1[i]+=a[i];
  35.             b1[i]+=b1[i+1];
  36.             b1[i]+=b[i];
  37.             b2[i]+=b[i];
  38.             b2[i]+=b2[i+1];
  39.             b2[i]+=a[i];
  40.         }
  41.         for(i=0;i<n;i++){
  42.             for(j=i;j<n;j++){
  43.                 if((i+j)%2==0){
  44.                     s1[i][j]+=s1[i][j-1];
  45.                     s1[i][j]+=a[j];
  46.                     s1[i][j]+=b[j];
  47.                 }
  48.                 else{
  49.                     s1[i][j]+=s1[i][j-1];
  50.                     s1[i][j]+=b[j];
  51.                     s1[i][j]+=a[j];
  52.                 }
  53.             }
  54.         }
  55.         for(i=0;i<n;i++){
  56.             for(j=i;j<n;j++){
  57.                 if((i+j)%2==0){
  58.                     s2[i][j]+=s2[i][j-1];
  59.                     s2[i][j]+=b[j];
  60.                     s2[i][j]+=a[j];
  61.                 }
  62.                 else{
  63.                     s2[i][j]+=s2[i][j-1];
  64.                     s2[i][j]+=a[j];
  65.                     s2[i][j]+=b[j];
  66.                 }
  67.             }
  68.         }
  69.         for(i=n-1;i>=0;i--){
  70.             for(j=i;j>=0;j--){
  71.                 if((i+j)%2==0){
  72.                     t1[i][j]+=t1[i][j+1];
  73.                     t1[i][j]+=a[j];
  74.                     t1[i][j]+=b[j];
  75.                 }
  76.                 else{
  77.                     t1[i][j]+=t1[i][j+1];
  78.                     t1[i][j]+=b[j];
  79.                     t1[i][j]+=a[j];
  80.                 }
  81.             }
  82.         }
  83.         for(i=n-1;i>=0;i--){
  84.             for(j=i;j>=0;j--){
  85.                 if((i+j)%2==0){
  86.                     t2[i][j]+=t2[i][j+1];
  87.                     t2[i][j]+=b[j];
  88.                     t2[i][j]+=a[j];
  89.                 }
  90.                 else{
  91.                     t2[i][j]+=t2[i][j+1];
  92.                     t2[i][j]+=a[j];
  93.                     t2[i][j]+=b[j];
  94.                 }
  95.             }
  96.         }
  97.         for(i=0;i<n;i++){
  98.             string h;
  99.             for(j=i;j>=0;j--) h+=a[j];
  100.             for(j=0;j<=i;j++) h+=b[j];
  101.             if(i==n-1){
  102.                 if(use[h]==0){
  103.                     ans++;
  104.                     use[h]=1;
  105.                 }
  106.                 continue;
  107.             }
  108.             int g=i+1;
  109.                 for(int gg=g;gg<n;gg++){
  110.                     string hh;
  111.                     hh+=h;
  112.                     hh+=s2[g][gg];
  113.                     if(gg==n-1){
  114.                         if(use[hh]==0){
  115.                             ans++;
  116.                             use[hh]=1;
  117.                         }   
  118.                         continue;
  119.                     }
  120.                     if((g+gg)%2==0){
  121.                         hh+=b1[gg+1];
  122.                     }
  123.                     if((g+gg)%2==1){
  124.                         hh+=b2[gg+1];
  125.                     }
  126.                     if(use[hh]==0){
  127.                         ans++;
  128.                         use[hh]=1;
  129.                     }
  130.                 }
  131.  
  132.         }
  133.         for(i=0;i<n;i++){
  134.             string h;
  135.             for(j=i;j<n;j++) h+=a[j];
  136.             for(j=n-1;j>=i;j--) h+=b[j];
  137.             if(i==0){
  138.                 if(use[h]==0){
  139.                     ans++;
  140.                     use[h]=1;
  141.                 }
  142.                 continue;
  143.             }
  144.             int g=i-1;
  145.                 for(int gg=g;gg>=0;gg--){
  146.                     string hh=h;
  147.                     hh+=t2[g][gg];
  148.                     if(gg==0){
  149.                         if(use[hh]==0){
  150.                             ans++;
  151.                             use[hh]=1;
  152.                         }   
  153.                         continue;
  154.                     }
  155.                     if((g+gg)%2==0){
  156.                         hh+=z1[gg-1];
  157.                     }
  158.                     if((g+gg)%2==1){
  159.                         hh+=z2[gg-1];
  160.                     }
  161.                     if(use[hh]==0){
  162.                         ans++;
  163.                         use[hh]=1;
  164.                     }
  165.                 }
  166.         }
  167.         for(i=0;i<n;i++){
  168.             string h;
  169.             for(j=i;j>=0;j--) h+=b[j];
  170.             for(j=0;j<=i;j++) h+=a[j];
  171.             if(i==n-1){
  172.                 if(use[h]==0){
  173.                     ans++;             
  174.                     use[h]=1;
  175.                 }
  176.                 continue;
  177.             }
  178.             int g=i+1;
  179.                 for(int gg=g;gg<n;gg++){
  180.                     string hh=h;
  181.                     hh+=s1[g][gg];
  182.                     if(gg==n-1){
  183.                         if(use[hh]==0){
  184.                             ans++;
  185.                             use[hh]=1;
  186.                         }   
  187.                         continue;
  188.                     }
  189.                     if((g+gg)%2==0){
  190.                         hh+=b2[gg+1];
  191.                     }
  192.                     if((g+gg)%2==1){
  193.                         hh+=b1[gg+1];
  194.                     }
  195.                     if(use[hh]==0){
  196.                         ans++;
  197.                         use[hh]=1;
  198.                     }
  199.                 }
  200.         }
  201.         for(i=0;i<n;i++){
  202.             string h;
  203.             for(j=i;j<n;j++) h+=b[j];
  204.             for(j=n-1;j>=i;j--) h+=a[j];
  205.             if(i==0){
  206.                 if(use[h]==0){
  207.                     ans++;
  208.                     use[h]=1;
  209.                 }
  210.                 continue;
  211.             }
  212.             int g=i-1;
  213.                 for(int gg=g;gg>=0;gg--){
  214.                     string hh=h;
  215.                     hh+=t1[g][gg];
  216.                     if(gg==0){
  217.                         if(use[hh]==0){
  218.                             ans++;
  219.                             use[hh]=1;
  220.                         }   
  221.                         continue;
  222.                     }
  223.                     if((g+gg)%2==0){
  224.                         hh+=z2[gg-1];
  225.                     }
  226.                     if((g+gg)%2==1){
  227.                         hh+=z1[gg-1];
  228.                     }
  229.                     if(use[hh]==0){
  230.                         ans++;
  231.                         use[hh]=1;
  232.                     }
  233.                 }
  234.         }
  235.         cout<<ans<<endl;
  236.     }
  237.     return 0;
  238. }
Success #stdin #stdout 0.01s 9104KB
comments (?)
stdin
copy 
3
2
aa
aa
3
dab
abd
5
ababa
babab
stdout
copy 
1
8
2
https://ideone.com/cEFiLO
language:
C++ (gcc 8.3)
created:
7 years 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!