fork download 
  1. #include<bits/stdc++.h>
  2. #include <string>
  3. using namespace std;
  4. typedef long long int ll;
  5.  
  6. #define mod 998244353
  7.  
  8. #define f2(n) for(long long int j=0;j<n;j++)
  9. #define p(n) cout<<n<<endl;
  10. #define f(n) for(long long int i=0;i<n;i++)
  11. #define io_boost ios_base::sync_with_stdio(false);cin.tie(NULL);
  12.  
  13.  
  14.  
  15.  
  16. inline int modular_inverse(ll a, ll m=mod) {
  17.     ll m1 = m;
  18.     ll y = 0, x = 1;
  19.     if (m == 1) {
  20.         return 0;
  21.     }
  22.     while (a > 1) {
  23.         ll q = a / m;
  24.         ll t = m;
  25.         m = a % m, a = t;
  26.         t = y;
  27.         y = x - q * y;
  28.         x = t;
  29.     }
  30.     if (x < 0) {
  31.         x += m1;
  32.     }
  33.     return x;
  34. }
  35.  
  36. ll solve(){
  37.  
  38.     string str1;
  39.     cin>>str1;
  40.    ll n=str1.size();
  41.     ll n1=0;
  42.  
  43.  
  44.     f(n)
  45.     {
  46.         if(str1[i]=='#'){n1++;}
  47.  
  48.  
  49.     }
  50.  
  51.     if(n1==1)
  52.     {
  53.         ll ans=1;
  54.         ans%=mod;
  55.         ll q=4;
  56.         q%=mod;
  57.         ans=(ans*modular_inverse(q))%mod;
  58.         cout<<ans<<" "<<ans<<" "<<ans<<" "<<ans<<endl;
  59.         }
  60.     else
  61.     {
  62.  
  63.  
  64.  
  65.       vector<char> temp;
  66.      vector<char> a;
  67.      for(int i=0;i<str1.size();i++)
  68.      {
  69.          if(str1[i]=='&'||str1[i]=='|'||str1[i]=='^')
  70.          {
  71.              temp.push_back(str1[i]);
  72.          }
  73.          else if(str1[i]==')'){
  74.              a.push_back(temp.back());
  75.              temp.pop_back();
  76.          }
  77.  
  78.      }
  79.  
  80.  
  81.         long long int ans00,ans11,ansaa,ansAA;
  82.  
  83.  
  84.     long long int q=4;
  85.  
  86.  
  87.     if(a[0]=='&')
  88.     {
  89.         ans00=9;
  90.         ans11=1;
  91.         ansaa=3;
  92.         ansAA=3;
  93.  
  94.         q*=4;
  95.     }
  96.     else if(a[0]=='|')
  97.     {
  98.         ans00=1;
  99.         ans11=9;
  100.         ansaa=3;
  101.         ansAA=3;
  102.  
  103.         q*=4;
  104.     }
  105.     else
  106.     {
  107.  
  108.         ans00=1;
  109.         ans11=1;
  110.         ansaa=1;
  111.         ansAA=1;
  112.         q=4;
  113.  
  114.     }
  115.  
  116.     for(ll i=1;i<a.size();i++)
  117.     {
  118.         if(a[i]=='&' && a[i-1]=='&')
  119.         {
  120.              q*=4;
  121.  
  122.              ll ansaap1=2*(ansaa)+ans11;
  123.              ll ansAAp1=2*(ansaa)+ans11;
  124.  
  125.              ll ans11p1=ans11;
  126.              ll ans00p1=(q-ans11p1-ansaap1-ansAAp1);
  127.             ans00=ans00p1;
  128.             ans11=ans11p1;
  129.             ansaa=ansaap1;
  130.             ansAA=ansAAp1;
  131.  
  132.  
  133.  
  134.         }
  135.         else if(a[i]=='&' && a[i-1]=='|')
  136.         {
  137.  
  138.             ll ansaap=((ans11)+2*(ansaa));
  139.              ll ansAAp=((ans11)+2*(ansaa));
  140.              ll ans00p=((ansaap*ansaap)/ans11);
  141.              ll ans11p=ans11;
  142.             ans00=ans00p;
  143.             ans11=ans11p;
  144.             ansaa=ansaap;
  145.             ansAA=ansAAp;
  146.  
  147.             q*=4%mod;
  148.  
  149.         }
  150.         else if(a[i]=='|' && a[i-1]=='&')
  151.         {
  152.  
  153.             ll ans00p2=ans00;
  154.  
  155.             ll ansaap2=(2*(ansaa)+ans00);
  156.              ll ansAAp2=(2*(ansaa)+ans00);
  157.              ll ans11p2=(((ansaap2)*(ansaap2))/ans00);
  158.             ans00=ans00p2;
  159.             ans11=ans11p2;
  160.             ansaa=ansaap2;
  161.             ansAA=ansAAp2;
  162.  
  163.             q*=4;
  164.         }
  165.  
  166.         else if(a[i]=='|' && a[i-1]=='|')
  167.         {
  168.  
  169.              q*=4;
  170.              ll ans00p3=ans00;
  171.              ll ansaap3=(ansaa)*2+ans00;
  172.              ll ansAAp3=(ansAA)*2+ans00;
  173.              ll ans11p3=q-ans00p3-ansaap3-ansAAp3;
  174.             ans00=ans00p3;
  175.             ans11=ans11p3;
  176.             ansaa=ansaap3;
  177.             ansAA=ansAAp3;
  178.  
  179.  
  180.         }
  181.         else if(a[i]=='&' && a[i-1]=='^')
  182.         {
  183.             ans00=ans11=ansaa=ansAA=1;
  184.             ans00*=9;
  185.             ans11*=1;
  186.             ansaa*=3;
  187.             ansAA*=3;
  188.             q*=4;
  189.         }
  190.         else if(a[i]=='|' && a[i-1]=='^')
  191.         {
  192.  
  193.             ans00=1;
  194.             ans11=9;
  195.             ansaa=3;
  196.             ansAA=3;
  197.             q*=4;
  198.         }
  199.         else if(a[i]=='^' && (a[i-1]=='^' || a[i-1]=='|' || a[i-1]=='&'))
  200.         {
  201.             q=4;
  202.              ans00=ans11=ansaa=ansAA=1;
  203.  
  204.         }
  205.     }
  206.  
  207. ans00%=mod;
  208. ans11%=mod;
  209. ansaa%=mod;
  210. ansAA%=mod;
  211.  
  212.     q%=mod;
  213.     ans00=(ans00*modular_inverse(q))%mod;
  214.     ans11=(ans11*modular_inverse(q))%mod;
  215.     ansaa=(ansaa*modular_inverse(q))%mod;
  216.     ansAA=(ansAA*modular_inverse(q))%mod;
  217.  
  218.     cout<<ans00<<" "<<ans11<<" "<<ansaa<<" "<<ansAA<<endl;
  219. }
  220. }
  221. int main()
  222. {
  223.  
  224.     ll test;
  225.     cin>>test;
  226.     while(test--)
  227.     {
  228.         solve();
  229.  
  230.     }
  231. }
  232.  
Runtime error #stdin #stdout 0s 4488KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/oL9GRQ
language:
C++ (gcc 8.3)
created:
5 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!