CF 856C Eleventh Birthday

題意

給定 $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;
}