fork download
  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
stdin
Standard input is empty
stdout
0