fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define N 710
  5. #define mod 1000000007
  6.  
  7. int dp[2][N][N];
  8. int all[2][N][N];
  9. int pos[2],pre[2][N];
  10. int cnt[2];
  11.  
  12. int main()
  13. {
  14.  
  15.     string s1,s2;
  16.     cin >> s1 >> s2;
  17.     pos[0]=pos[1]=-1;
  18.     for(int i=0; i<s1.size(); i++)
  19.     {
  20.         pre[0][i]=pos[0];
  21.         pre[1][i]=pos[1];
  22.         pos[s1[i]-'0']=i;
  23.     }
  24.     for(int i=0; i<s2.size(); i++) cnt[s2[i]-'0']++;
  25.     int ans=0;
  26.     for(int p=0; p<s1.size(); p++)
  27.     {
  28.         int nw=s1[p]-'0';
  29.         if(nw==0)
  30.         {
  31.             if(pre[nw][p]==-1)
  32.             {
  33.                 dp[0][1][0]=1;
  34.                 all[0][1][0]=1;
  35.                 for(int i=1; i<=cnt[1]; i++)
  36.                 {
  37.                     dp[0][1][i]=all[1][0][i];
  38.                     all[0][1][i]=all[1][0][i];
  39.                 }
  40.             }
  41.             else
  42.             {
  43.                 for(int i=cnt[0]; i>=0; i--)
  44.                 {
  45.                     for(int j=cnt[1]; j>=0; j--)
  46.                     {
  47.                         if(i>0) dp[0][i][j]=dp[0][i-1][j];
  48.                         else dp[0][i][j]=0;
  49.                         if(i>0) dp[0][i][j]+=all[1][i-1][j];
  50.                         dp[0][i][j]%=mod;
  51.                         all[0][i][j]+=dp[0][i][j];
  52.                         all[0][i][j]%=mod;
  53.                     }
  54.                 }
  55.             }
  56.             memset(all[1],0,sizeof (all[1]));
  57.             ans+=dp[0][cnt[0]][cnt[1]];
  58.             ans%=mod;
  59.  
  60.         }
  61.         else
  62.         {
  63.             if(pre[nw][p]==-1)
  64.             {
  65.                 dp[1][0][1]=1;
  66.                 all[1][0][1]=1;
  67.                 for(int i=1; i<=cnt[0]; i++)
  68.                 {
  69.                     dp[1][i][1]=all[0][i][0];
  70.                     all[1][i][1]=all[0][i][0];
  71.                 }
  72.             }
  73.             else
  74.             {
  75.                 for(int i=cnt[0]; i>=0; i--)
  76.                 {
  77.                     for(int j=cnt[1]; j>=0; j--)
  78.                     {
  79.                         if(j>0) dp[1][i][j]=dp[1][i][j-1];
  80.                         else dp[1][i][j]=0;
  81.                         if(j>0) dp[1][i][j]+=all[0][i][j-1];
  82.                         dp[1][i][j]%=mod;
  83.                         all[1][i][j]+=dp[1][i][j];
  84.                         all[1][i][j]%=mod;
  85.                     }
  86.                 }
  87.             }
  88.             memset(all[0],0,sizeof (all[0]));
  89.             ans+=dp[1][cnt[0]][cnt[1]];
  90.             ans%=mod;
  91.         }
  92.     }
  93.     cout<<ans<<endl;
  94.  
  95.  
  96. }
  97.  
  98.  
Success #stdin #stdout 0s 4196KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/imNQNu
language:
C++14 (clang 8.0)
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!