P5301 [GXOI/GZOI2019] 宝牌一大堆
#include<bits/stdc++.h>
#define pb push_back
#define fir first
#define sec second
#define mp make_pair
#define int long long
#define pii pair<int,int>
#define Blue_Archive return 0
using namespace std;
const int gsws[15] = {0,1,9,10,18,19,27,28,29,30,31,32,33,34};
template <typename T>
T Max(T x,T y) { return x > y ? x : y;}
template <typename T>
T Min(T x,T y) { return x < y ? x : y;}
template <typename T>
T Abs(T x) { return x < 0 ? -x : x;}
template <typename T>
T chkmax(T &x,T y) { return x = x > y ? x : y;}
template <typename T>
T &read(T &r)
{r = 0;bool w = 0;char ch = getchar();while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0,ch = getchar();while(ch >= '0' && ch <= '9') r =(r << 3) +(r << 1) +(ch ^ 48),ch = getchar();return r = w ? -r : r;
}int ans;
int cnt[35];
int g[40][10];
int f[40][10][5][6][6];bool baopai[35];namespace Calc
{int fac[15],pow2[50];inline void Cpre(){fac[0] = 1;for(int i = 1;i <= 10;++i){fac[i] = fac[i - 1] * i;}pow2[0] = 1;for(int i = 1;i <= 30;++i){pow2[i] = pow2[i - 1] * 2;}}inline int C(int x,int y) { return fac[x] / fac[y] / fac[x - y];}inline int cbp(int x,int y) { return baopai[x] ? pow2[y] : 1;}
}
using namespace Calc;
namespace How_to_get
{inline char getcha(){char ch;cin >> ch;return ch;}inline int getpai(){char ch = getcha();if(ch == '0'){return 0;}if(ch >= '1' && ch <= '9'){char ch2 = getcha();if(ch2 == 'm'){return ch - '0';}if(ch2 == 'p'){return 9 +(ch - '0');}if(ch2 == 's'){return 18 +(ch - '0');}}switch(ch){case 'E':return 28;case 'S':return 29;case 'W':return 30;case 'N':return 31;case 'Z':return 32;case 'B':return 33;case 'F':return 34;}return 0;}
}
using namespace How_to_get;inline void read1()
{int x = getpai();while(x){cnt[x]--;x = getpai();}
}inline void read2()
{int x = getpai();while(x){baopai[x] = 1;x = getpai();}
}inline int Gsws()
{Cpre();int sumq = 0,mul = 1,bps = 0;for(int i = 1;i <= 13;++i){if(cnt[gsws[i]] == 0){return 0;}}for(int i = 1;i <= 13;++i){mul *= cnt[gsws[i]];bps += baopai[gsws[i]];}for(int i = 1;i <= 13;++i){if(cnt[gsws[i]] <= 1){continue;}sumq = Max(sumq,mul / cnt[gsws[i]] * C(cnt[gsws[i]],2) * pow2[bps + baopai[gsws[i]]]);}return sumq * 13;
}inline void dp1(int l,int r)
{for(int i = l;i <= r;++i){for(int j = 0;j <= 4;++j){for(int k = 0;k <= 1;++k){for(int c1 = 0;c1 <= 4;++c1){for(int c2 = 0;c2 <= 4;++c2){if(!f[i][j][k][c1][c2]){continue;}if(j == 4 && k){chkmax(ans,f[i][j][k][c1][c2]);}if(j + 1 <= 4 && cnt[i + 1] >= 3){chkmax(f[i + 1][j + 1][k][3][c1],f[i][j][k][c1][c2] * C(cnt[i + 1],3) * cbp(i + 1,3));}for(int p = 1;p <= 2;++p){if(j + p <= 4 && i >= 2 && cnt[i + 1] >= p && c1 <= cnt[i] - p && c2 <= cnt[i - 1] - p){chkmax(f[i + 1][j + p][k][p][c1 + p],f[i][j][k][c1][c2] / C(cnt[i],c1) / C(cnt[i - 1],c2) * C(cnt[i + 1],p) * C(cnt[i],c1 + p) * C(cnt[i - 1],c2 + p) * cbp(i + 1,p) * cbp(i,p) * cbp(i - 1,p));}}if(j + 2 <= 4 && i >= 2 && cnt[i + 1] >= 4 && c1 < cnt[i] && c2 < cnt[i - 1]){chkmax(f[i + 1][j + 2][k][4][c1 + 1],f[i][j][k][c1][c2] / C(cnt[i],c1) / C(cnt[i - 1],c2) * C(cnt[i + 1],4) * C(cnt[i],c1 + 1) * C(cnt[i - 1],c2 + 1) * cbp(i + 1,4) * cbp(i,1) * cbp(i - 1,1));}if(cnt[i + 1] >= 2 && !k){chkmax(f[i + 1][j][1][2][c1],f[i][j][k][c1][c2] * C(cnt[i + 1],2) * cbp(i + 1,2));}if(j + 1 <= 4 && i >= 2 && cnt[i + 1] >= 3 && !k && c1 < cnt[i] && c2 < cnt[i - 1]){chkmax(f[i + 1][j + 1][1][3][c1 + 1],f[i][j][k][c1][c2] / C(cnt[i],c1) / C(cnt[i - 1],c2) * C(cnt[i + 1],3) * C(cnt[i],c1 + 1) * C(cnt[i - 1],c2 + 1) * cbp(i + 1,3) * cbp(i,1) * cbp(i - 1,1));}chkmax(f[i + 1][j][k][0][c1],f[i][j][k][c1][c2]);if(j + 2 <= 4 && i >= 2 && cnt[i + 1] >= 4 && !k && c1 < cnt[i] - 1 && c2 < cnt[i - 1] - 1){chkmax(f[i + 1][j + 2][1][4][c1 + 2],f[i][j][k][c1][c2] / C(cnt[i],c1) / C(cnt[i - 1],c2) * C(cnt[i + 1],4) * C(cnt[i],c1 + 2) * C(cnt[i - 1],c2 + 2) * cbp(i + 1,4) * cbp(i,2) * cbp(i - 1,2));}chkmax(f[i + 1][j][k][0][c1],f[i][j][k][c1][c2]);}}}}}
}inline void dp2(int l,int r)
{for(int i = l;i <= r;++i){for(int j = 0;j <= 4;++j){for(int k = 0;k <= 1;++k){for(int c1 = 0;c1 <= 4;++c1){for(int c2 = 0;c2 <= 4;++c2){if(!f[i][j][k][c1][c2]){continue;}if(j == 4 && k){chkmax(ans,f[i][j][k][c1][c2]);}if(j + 1 <= 4 && cnt[i + 1] >= 3){chkmax(f[i + 1][j + 1][k][3][c1],f[i][j][k][c1][c2] * C(cnt[i + 1],3) * cbp(i + 1,3));}if(cnt[i + 1] >= 2 && !k){chkmax(f[i + 1][j][1][2][c1],f[i][j][k][c1][c2] * C(cnt[i + 1],2) * cbp(i + 1,2));}chkmax(f[i + 1][j][k][0][c1],f[i][j][k][c1][c2]);}}}}}
}inline void solve()
{for(int i = 1;i <= 34;++i){cnt[i] = 4;baopai[i] = 0;}read1();read2();ans = 0;ans = Max(ans,Gsws());for(int i = 1;i <= 34;++i){for(int j = 0;j <= 4;++j){for(int k = 0;k <= 1;++k){for(int c1 = 0;c1 <= 4;++c1){for(int c2 = 0;c2 <= 4;++c2){f[i][j][k][c1][c2] = 0;}}}}}for(int i = 1;i <= 34;++i){for(int j = 0;j <= 7;++j){g[i][j] = 0;}}f[0][0][0][0][0] = 1;dp1(0,8);dp2(9,10);dp1(11,17);dp2(18,19);dp1(20,26);dp2(27,33);for(int c1 = 0;c1 <= 4;++c1){for(int c2 = 0;c2 <= 4;++c2){chkmax(ans,f[34][4][1][c1][c2]);}}g[0][0] = 7;for(int i = 0;i <= 33;++i){for(int j = 0;j <= 7;++j){if(!g[i][j]){continue;}if(j == 7){chkmax(ans,g[i][j]);}if(cnt[i + 1] >= 2 && j + 1 <= 7){chkmax(g[i + 1][j + 1],g[i][j] * C(cnt[i + 1],2) * cbp(i + 1,2));}chkmax(g[i + 1][j],g[i][j]);}}chkmax(ans,g[34][7]);cout << ans << '\n';
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);int T;read(T);while(T--) solve();Blue_Archive;
}
