daily pastebin goal
29%
SHARE
TWEET

d.cpp

a guest Jun 21st, 2015 212 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define SET(t,v) memset((t), (v), sizeof(t))
  5. #define ALL(x) x.begin(), x.end()
  6. #define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
  7. #define REP(i,n) for(ll i=0;i<n;i++)
  8.  
  9. #if __cplusplus > 199711L
  10. #define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
  11. #else
  12. #define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
  13. #endif
  14.  
  15. #define IREP(in,i,n) for(ll i=in;i<n;i++)
  16. #define IN(a,b) ( (b).find(a) != (b).end())
  17. #define PB push_back
  18. #define MP make_pair
  19.  
  20. typedef long long ll;
  21. typedef long double LD;
  22. typedef pair<int,int> pii;
  23.  
  24. #define NDEBUG
  25.  
  26. #ifdef DEBUG
  27. #define dbg(msg) msg
  28. #define dbgp(msg) cerr << msg << endl;
  29. #define var(v) cerr << #v << " = " << v << endl;
  30. #else
  31. #define dbg(msg) //msg
  32. #define dbgp(msg) //cerr << msg << endl;
  33. #define var(v) //cerr << #v << " = " << v << endl;
  34. #endif
  35.  
  36. #define MOD 1000000003
  37.  
  38. ll dp[1010][1010];
  39.  
  40. ll solve(){
  41.     string s1;
  42.     string s2;
  43.     cin >> s1 >> s2;
  44.  
  45.     // Just debugging
  46.     var(s1);
  47.     var(s1.size());
  48.     var(s2);
  49.     var(s2.size());
  50.  
  51.     // Clear to 0
  52.     memset(dp, 0, sizeof dp);
  53.  
  54.     // Two loop
  55.     REP(i,s1.size()){
  56.         REP(i2,s2.size()){
  57.  
  58.             if(i == 0){
  59.  
  60.                 // If on boundary but not on 0,0, use neighbour value as initial value
  61.                 if(i2 == 0){
  62.                 }else{
  63.                     dp[i][i2] = dp[i][i2-1];
  64.                 }
  65.  
  66.                 // If the character is the same, add one more subsequence
  67.                 if(s1[i] == s2[i2]){
  68.                     dp[i][i2] += 1;
  69.                 }
  70.                 dp[i][i2] %= MOD;
  71.  
  72.             }else if(i2 == 0){
  73.  
  74.                 // Same thing as previous one, but different side
  75.                 if(i == 0){
  76.                 }else{
  77.                     dp[i][i2] = dp[i-1][i2];
  78.                 }
  79.  
  80.                 if(s1[i] == s2[i2]){
  81.                     dp[i][i2] += 1;
  82.                 }
  83.                 dp[i][i2] %= MOD;
  84.  
  85.             }else{
  86.  
  87.                 if(s1[i] == s2[i2]){
  88.                     // If the character is the same,
  89.                     // Add another subsequence
  90.                     // And the number of subsequence onf i-1 and i2-1
  91.                     // But since we are going to subtract it anyway, we just skip the subtraction
  92.                     dp[i][i2] += 1;
  93.  
  94.                     // Count from above and side is added
  95.                     dp[i][i2] %= MOD;
  96.                     dp[i][i2] += dp[i-1][i2];
  97.                     dp[i][i2] %= MOD;
  98.                     dp[i][i2] += dp[i][i2-1];
  99.                     dp[i][i2] %= MOD;
  100.  
  101.                     // Skip subtraction
  102.                     //dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
  103.                     //dp[i][i2] %= MOD;
  104.  
  105.                 }else{
  106.                     // If the character is not the same,
  107.                     // We add the number of subsequence above and on size
  108.                     // But because both of them contain the number of subsequence from the diagonal i-1 and i2-1,
  109.                     // We need to remove minus that.
  110.                     // Remember the formula |A union B| = |A| + |B| - |A intersect B|
  111.  
  112.                     dp[i][i2] += dp[i-1][i2];
  113.                     dp[i][i2] %= MOD;
  114.                     dp[i][i2] += dp[i][i2-1];
  115.                     dp[i][i2] %= MOD;
  116.  
  117.                     dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
  118.                     dp[i][i2] %= MOD;
  119.                 }
  120.             }
  121.  
  122.         }
  123.     }
  124.  
  125.     // Just debugging
  126.     dbg(
  127.     REP(i,s1.size()){
  128.         REP(i2,s2.size()){
  129.             cerr << dp[i][i2] << " ";
  130.         }
  131.         cerr << endl;
  132.     }
  133.     )
  134.  
  135.     return (dp[s1.size()-1][s2.size()-1]+1)%MOD;
  136. }
  137.  
  138. int main(int argv, char** argc){
  139.     cin.sync_with_stdio(0);
  140.  
  141.     int t = INT_MAX;
  142.     cin >> t;
  143.     REP(i,t){
  144.         printf("Case #%lld: %lld\n",i+1,solve());
  145.     }
  146.  
  147.     return 0;
  148. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top