题目大意：给你一个长度为 n 的 字符串表示一个乘法，一次操作随机选两个字符进行交换，进行m次操作，让你求出所有可能操作
的答案和。 (1 <= n, m <= 50)
思路：巨难。。 对于固定位置的三个字符来说，把中间的看成*, 两边的为a，b， 这个产生的贡献为，a * b * C，C只与a, b和 * 的位置有关，
所以我们只要求出a*b的贡献就好啦。
我们定义dp[ a ][ b ][ c ][ k ] 表示三个字符分别是a，b，c， b在中间，还需要交换 k次的答案。
最后枚举三个位置求答案。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define pii pair<int, int> #define y1 skldjfskldjg #define y2 skldfjsklejg using namespace std; const int N = 100 + 7; const int M = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 +7; char s[56]; int n, m, a[56], cnt[11]; LL f[11][11][11][51], ten[56]; void add(LL &a, LL b) { a += b; if(a >= mod) a -= mod; } LL dp(int a, int b, int c, int m) { // printf("%d %d %d %d $$ ", a, b, c, m); if(!m) return b == 10 ? a * c : 0; if(a > c) swap(a, c); LL &ans = f[a][b][c][m]; if(~ans) return ans; ans = 0; add(ans, dp(c, b, a, m - 1)); // a <-> c add(ans, dp(b, a, c, m - 1)); // a <-> b add(ans, dp(a, c, b, m - 1)); // b <-> c LL num = (n - 3) * (n - 4) / 2; if(num) add(ans, num * dp(a, b, c, m - 1) % mod); // a, b, c 之外的两个数相互交换 int t[11]; memcpy(t, cnt, sizeof(t)); t[a]--; t[b]--; t[c]--; for(int i = 0; i <= 10; i++) { // a, b, c 之外的一个数与 a 或 b 或 c 交换 if(!t[i]) continue; add(ans, t[i] * dp(i, b, c, m - 1) % mod); //挑一种数与a交换 add(ans, t[i] * dp(a, i, c, m - 1) % mod); //挑一种数与b交换 add(ans, t[i] * dp(a, b, i, m - 1) % mod); //挑一种数与c交换 } return ans; } int main() { ten[0] = 1; for(int i = 1; i <= 55; i++) ten[i] = ten[i - 1] * 10 % mod; int T; scanf("%d", &T); for(int cas = 1; cas <= T; cas++) { memset(f, -1, sizeof(f)); memset(cnt, 0, sizeof(cnt)); scanf("%d%s", &m, s); n = strlen(s); printf("Case #%d: ", cas); for(int i = 0; i < n; i++) { a[i] = (s[i] == '*' ? 10 : s[i] - '0'); cnt[a[i]]++; } LL ans = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { for(int k = j + 1; k < n; k++) { add(ans, ten[j - i - 1] * ten[n - k - 1] % mod * dp(a[i], a[j], a[k], m) % mod); } } } printf("%lld ", ans); } return 0; } /* 2 1 1*2 2 1*2 */