LY1467 [ 20231113 NOIP 模拟赛 T3 ] Remember11

题意

给定 \(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;
}