题意
给定 \(n\) 个数，求将她们收尾拼接形成 \(11\) 的倍数的方案数。
Sol
数数题。
众所周知，是 \(11\) 的倍数意味着将该数错位相减 \(mod 11 = 0\)。
注意到偶数位数的数与奇数位数的数的贡献是不同的。
考虑将她们分开计算，然后合并。
设 \(f_{ijk}\) 表示前 \(i\) 个 奇数，其中有 \(j\) 个是 正贡献，\(mod 11 = k\)。
\(g_{ijk}\) 同理。
考虑合并，注意到如果在两个奇数中间插入偶数对位数的奇偶没有贡献。显然 \(f_{n1, n1/2, k}\) 对答案有贡献。
枚举偶数的数量、以及 \(mod 11\) 即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 2005, mod = 147744151;
vector <int> s1, s2;
array <array <array <int, 11>, N>, 2> f, g;
int cal(int x) {
while (x >= 11) x -= 11;
while (x < 0) x += 11;
return x;
}
void Mod(int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
array <int, 6005> fac, inv;
int pow_(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1) ans = ans * x % p;
x = x * x % p;
k >>= 1;
}
return ans;
}
void init() {
fac[0] = 1;
for (int i = 1; i <= 6000; i++)
fac[i] = fac[i - 1] * i % mod;
inv[6000] = pow_(fac[6000], mod - 2, mod);
for (int i = 6000; i; i--)
inv[i - 1] = inv[i] * i % mod;
}
int C(int n, int m) {
if (n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int Stab(int n, int m) {
if (m == 0) return n == 0;
return C(n + m - 1, m - 1);
}
void solve() {
s1.clear(), s2.clear();
int n = read();
for (int i = 1; i <= n; i++) {
int x = read();
if (to_string(x).size() & 1) s1.push_back(x % 11);
else s2.push_back(x % 11);
}
array <int, 11> tp1; tp1.fill(0);
array <array <int, 11>, N> tp2; tp2.fill(tp1);
f.fill(tp2), g.fill(tp2);
f[0][0][0] = g[0][0][0] = 1;
for (int i = 0; i < (int)s1.size(); i++) {
array <int, 11> tp;
tp.fill(0);
f[(i + 1) & 1].fill(tp);
for (int j = 0; j <= i; j++) {
for (int k = 0; k < 11; k++) {
int tp = f[i & 1][j][k];
f[(i + 1) & 1][j + 1][cal(k - s1[i])] += tp;
Mod(f[(i + 1) & 1][j + 1][cal(k - s1[i])]);
f[(i + 1) & 1][j][cal(k + s1[i])] += tp;
Mod(f[(i + 1) & 1][j][cal(k + s1[i])]);
}
}
}
for (int i = 0; i < (int)s2.size(); i++) {
array <int, 11> tp;
tp.fill(0);
g[(i + 1) & 1].fill(tp);
for (int j = 0; j <= i; j++) {
for (int k = 0; k < 11; k++) {
int tp = g[i & 1][j][k];
g[(i + 1) & 1][j + 1][cal(k - s2[i])] += tp;
Mod(g[(i + 1) & 1][j + 1][cal(k - s2[i])]);
g[(i + 1) & 1][j][cal(k + s2[i])] += tp;
Mod(g[(i + 1) & 1][j][cal(k + s2[i])]);
}
}
}
/* write(f[s1.size() & 1][s1.size() / 2][2]), puts(""); */
int ans = 0;
for (int i = 0; i <= (int)s2.size(); i++) {
for (int k = 0; k < 11; k++) {
int tp1 = fac[s1.size() / 2] * fac[s1.size() - s1.size() / 2] % mod
* fac[i] % mod * fac[s2.size() - i] % mod,
tp2 = Stab(i, s1.size() - s1.size() / 2)
* Stab(s2.size() - i, s1.size() / 2 + 1) % mod,
tp3 = f[s1.size() & 1][s1.size() / 2][(11 - k) % 11] * g[s2.size() & 1][i][k] % mod;
ans += tp1 * tp2 % mod * tp3 % mod;
Mod(ans);
}
}
write(ans), puts("");
}
signed main() {
freopen("remember.in", "r", stdin);
freopen("remember.out", "w", stdout);
init();
int T = read();
while (T--) solve();
return 0;
}