1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 22 #define INF 987654321 #define EPS 1e-9 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define all3 array<ll,3> #define all5 array<ll,5> #define vall5 vector<all5> #define vll vector<ll> #define vs vector<string> #define usll unordered_set<ll> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a)
using namespace std; ll mod = 1e9 + 7; ll fact[404]; ll dp[404][404][404]; ll gcd(ll p, ll q){ if(q==0) return p; return gcd(q, p%q); }
ll fac(ll n) { if(fact[n]) return fact[n]; return fact[n] = (n * fac(n - 1)) % mod; }
ll modpow(ll x, ll n) { if(n == 0) return 1; ll res = modpow(x, n>>1); res = (res * res) % mod; if(n&1) res = (res * x) % mod; return res; }
ll solve(ll n, string s) { memset(dp, 0, sizeof dp); for(ll i = 0; i <= n; i++) for(ll j = 0; j <=n ; j++) dp[i][j][1] = max(0ll, j - i + 1), dp[i][j][0] = 1; ll p = (2 * fac(n)) % mod; for(ll i = n - 1; i >= 0; i--) { for(ll j = i + 1; j < n; j++) { for(ll k = 2; k < n; k++) { if(j - i + 1 < k) break; if(s[i] == s[j]) { dp[i][j][k] = (dp[i][j-1][k] + dp[i+1][j][k] - dp[i+1][j-1][k] + dp[i+1][j-1][k-2]) % mod; p = (p + fac(k) * fac(n - k) % mod * dp[i+1][j-1][k-2]) % mod; } else { dp[i][j][k] = (dp[i][j-1][k] + dp[i+1][j][k] - dp[i+1][j-1][k] + mod) % mod; } } } } return (p * modpow(fac(n), mod - 2)) % mod; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc; cin >> tc; fact[0] = fact[1] = 1; for (ll i = 1; i <= tc; i++) { ll n; string s; cin>>n>>s; cout << "Case #" << i << ": "<<solve(n, s)<<endl; }
return 0; }
|