fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[2010][2010];
  5. int l;
  6. int mod = 1000000007;
  7. string s;
  8. int cal (int i, int j) {
  9.     if (i < 0 || j > l) {
  10.         return 0;
  11.     }
  12.     if (dp[i][j] != 0) {
  13.         return dp[i][j];
  14.     }
  15.     int temp;
  16.     if (s[i] == s[j]) {
  17.         temp = (cal(i+1, j) % mod + cal(i, j-1)%mod)%mod + 1;
  18.         temp = temp % mod;
  19.     }else {
  20.         temp = (cal(i+1, j) % mod + cal(i, j-1)%mod)%mod;
  21.         temp = temp - cal(i+1, j-1)%mod;
  22.         temp = temp + mod;
  23.         temp = temp % mod;
  24.     }
  25.     dp[i][j] = temp;
  26.     cout<<temp<<endl;
  27.     return temp;
  28. }
  29.  
  30.  
  31. int main() {
  32.  
  33. 	//relevant code here
  34. 	int test;
  35. 	cin>>test;
  36. 	while (test--) {
  37. 	    s.clear();
  38. 	    cin>>s;
  39. 	    l = s.size(); 
  40. 	    memset (dp, 0, sizeof (dp));
  41. 	    cout<<cal(0, l-1)<<endl;
  42. 	}
  43.  
  44. 	return 0;
  45. }
Runtime error #stdin #stdout 0s 31848KB
comments (?)
stdin
copy 
2
aaaaa
ababa
stdout
copy 
Standard output is empty
https://ideone.com/YgPZtu
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!