CodeForces 159D Palindrome pairs
string s が与えられる。
この中に、互いに素な回文、a,bのペアはいくつあるか。
想定解法はDPらしいけど、ごり押しで通った。計算量的にはO(n^2)かO(n^2logn)くらい?
#include <iostream> #include <vector> #include <string> using namespace std; typedef long long ll; int main(){ string s; cin >> s; vector<ll> sumto(s.size()); vector<ll> sumfrom(s.size()); for(int from=0;from<s.size();from++){ for(int to=from;to<s.size();to++){ bool ok = true; for(int i=from;i<=to;i++){ if(s[i] != s[from+to-i]){ ok = false; break; } } if(ok){ sumfrom[from]++; sumto[to]++; } } } ll ret = 0; for(int i=0;i<s.size();i++){ for(int j=i+1;j<s.size();j++){ ret += sumto[i] * sumfrom[j]; } } cout << ret << endl; return 0; }