CF 856C Eleventh Birthday

標籤： cfdpmath

题意

给定 $n$ 个数，问将这些数字排列后拼起来是 $11$ 的倍数的方案数（相同的数排列不同算多种）。

解析

首先注意到 $10 \equiv -1 \pmod{11}$。即加入某个数，若它之前有奇位数，则其贡献为负，否则贡献为正，最后若贡献和为 $11$ 的倍数，则原数字是 $11$ 的倍数。

因此考虑将长度为奇数的数与长度为偶数的数分开考虑，用 $f(i, j, k)$ 表示考虑到第 $i$ 个奇数，$j$ 个贡献为正，贡献和为 $k$ 的方案数，用 $g(i, j, k)$ 表示考虑到第 $i$ 个偶数，$j$ 个贡献为正，贡献和为 $k$ 的方案数，最后统计答案把两个乘起来即可。

注意 $n$ 较大，需要滚动数组。

void solve()
{
    int n;
    scanf("%d", &n);
    vector<int> odd, even;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        int m = x % 11;
        int len = std::log10(x) + 1;
        if (len % 2 == 0) even.emplace_back(m);
        else odd.emplace_back(m);
    }
    
    vector<vector<vector<int>>>
        f(2, vector<vector<int>>(odd.size() + 1, vector<int>(11))),
        g(2, vector<vector<int>>(even.size() + 1, vector<int>(11)));
 
    int odd_tot_pos = (odd.size() + 1) / 2;
    f[0][0][0] = g[0][0][0] = 1;
    for (int i = 0; i < odd.size(); i++) {
        for (int j = 0; j <= odd.size(); j++) std::ranges::fill(f[(i + 1) & 1][j], 0);
        for (int j = 0; j <= odd_tot_pos && j <= i; j++) {
            int pos = odd_tot_pos - j;
            int neg = odd.size() - i - pos;
            for (int k = 0; k < 11; k++) {
                if (pos > 0) {
                    f[(i + 1) & 1][j + 1][(k + odd[i]) % 11] += (long long)f[i & 1][j][k] * pos % MODN;
                    f[(i + 1) & 1][j + 1][(k + odd[i]) % 11] %= MODN;
                } 
                if (neg > 0) {
                    f[(i + 1) & 1][j][(k + 11 - odd[i]) % 11] += (long long)f[i & 1][j][k] * neg % MODN;
                    f[(i + 1) & 1][j][(k + 11 - odd[i]) % 11] %= MODN;
                }
            }
        }
        // for (int j = 0; j <= odd_tot_pos; j++) {
        //     for (int k = 0; k < 11; k++) {
        //         printf("f[%d][%d][%d] = %d\n", i + 1, j, k, f[(i + 1) & 1][j][k]);
        //     }
        // }
    }
    for (int i = 0; i < even.size(); i++) {
        for (int j = 0; j <= even.size(); j++) std::ranges::fill(g[(i + 1) & 1][j], 0);
        for (int j = 0; j <= i; j++) {
            int pos = odd.size() / 2 + 1 + j;
            int neg = odd.size() + 1 + i - pos;
            for (int k = 0; k < 11; k++) {
                if (pos > 0) {
                    g[(i + 1) & 1][j + 1][(k + even[i]) % 11] += (long long)g[i & 1][j][k] * pos % MODN;
                    g[(i + 1) & 1][j + 1][(k + even[i]) % 11] %= MODN;
                }
                if (neg > 0) {
                    g[(i + 1) & 1][j][(k + 11 - even[i]) % 11] += (long long)g[i & 1][j][k] * neg % MODN;
                    g[(i + 1) & 1][j][(k + 11 - even[i]) % 11] %= MODN;
                }
            }
        }
        // for (int j = 0; j <= even.size(); j++) {
        //     for (int k = 0; k < 11; k++) {
        //         printf("g[%d][%d][%d] = %d\n", i + 1, j, k, g[i][j][k]);
        //     }
        // }
    }
 
    int ans = 0;
    for (int j = 0; j <= even.size(); j++) {
        for (int k = 0; k < 11; k++) {
            ans += (long long)f[odd.size() & 1][odd_tot_pos][k] * g[even.size() & 1][j][(11 - k) % 11] % MODN;
            ans %= MODN;
        }
    }
    printf("%d\n", ans);
}

UPD: 2023-07-04

今天是 2023 年 7 月 4 日，模拟赛又一次考到这题了，狗日的成外能搞点新东西吗。

思路不变。求完 $f$ 后，可以直接把偶数长度的数插入到已经排好的奇数长度数中。插入一个偶数长度的数不会改变其他值的贡献正负性，非常好处理，令 $h(i, j, k)$（即下面代码中的 g）表示在已经排好所有奇数长度的数后，考虑前 $i$ 个偶数长度的数，有 $j$ 个偶数长度的数贡献为正，贡献和为 $k$ 的方案数。这样统计答案稍微方便点。

由于今天考试的题数据范围小了点，就懒得写滚动数组了。

template <typename T>
using vec = std::vector<T>;

template <typename T>
using vec2 = vec<vec<T>>;

template <typename T>
using vec3 = vec2<vec<T>>;

int main()
{
	int n;
	std::cin >> n;
	std::vector<int> odds, evens;
	for (int i = 0; i < n; i++) {
		std::string s;
		std::cin >> s;
		int x = 0;
		for (auto i : s) {
			x = (x * 10 + i - '0') % 11;
		}
		if (s.size() % 2 == 1) odds.emplace_back(x);
		else evens.emplace_back(x);
	}

	int odd_pos_tot = (odds.size() + 1) / 2;
	int odd_neg_tot = odds.size() - odd_pos_tot;
	vec3<int> f(odds.size() + 1, vec2<int>(odd_pos_tot + 1, vec<int>(11, 0)));

	f[0][0][0] = 1;
	for (int i = 0; i < (int)odds.size(); i++) {
		int v = odds[i];
		for (int j = 0; j <= std::min(i, odd_pos_tot); j++) {
			int pos = odd_pos_tot - j;
			int neg = odd_neg_tot - (i - j);
			for (int k = 0; k < 11; k++) {
				if (pos) (f[i + 1][j + 1][(k + v) % 11] += 
					  (long long)f[i][j][k] * pos % M) %= M;
				if (neg) (f[i + 1][j][(k + 11 - v) % 11] += 
					  (long long)f[i][j][k] * neg % M) %= M;
			}
		}
	}

	int even_pos_ori = odds.size() / 2 + 1;
	int even_neg_ori = (odds.size() + 1) / 2;
	vec3<int> g(evens.size() + 1, vec2<int>(evens.size() + 1, vec<int>(11, 0)));
	g[0][0] = f[odds.size()][odd_pos_tot];
	for (int i = 0; i < (int)evens.size(); i++) {
		int v = evens[i];
		for (int j = 0; j <= i; j++) {
			int pos = even_pos_ori + j;
			int neg = even_neg_ori + i - j;
			for (int k = 0; k < 11; k++) {
				if (pos) (g[i + 1][j + 1][(k + v) % 11] +=
					  (long long)g[i][j][k] * pos % M) %= M;
				if (neg) (g[i + 1][j][(k + 11 - v) % 11] +=
					 (long long)g[i][j][k] * neg % M) %= M;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= (int)evens.size(); i++) {
		(ans += g[evens.size()][i][0]) %= M;
	}
	std::cout << ans << std::endl;
}