思路与算法

令f[t][s]为用集合S数字构成t位串的数位和计数，用逐位加数字的背包递推得到f，设G(t)=Σs f[t][s]^2。前后半和相同与奇偶位和相同各有G(n)种，需减交集。把2n位置按前后半和奇偶分成四块，两等式相加减得到对角块数字和分别相等；块长为floor(n/2)和ceil(n/2)，交集为G(floor(n/2))G(ceil(n/2))。

正确性说明

f的转移按最后一位唯一拆分。相同长度两块和相等的方案数对每个和独立相乘，求和即G。四块分类把两条件同时成立严格等价为两对独立和相等，交集乘积成立；容斥给并集2G(n)-交集。

复杂度

滚动DP初始化O(n)，逐长度处理至9t的和并枚举至多10个数字，总O(|S|n²)时间，G计算O(n²)；空间O(n)（和数组长度9n+1），模999983。

易错点

允许前导0；S是集合，输入顺序无关。n奇数时四块不是同长，应分别取下整和上整。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 999983;
int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> d;
    for (char c : s)
        d.push_back(c - '0');
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    vector<int> a(9 * n + 1), b(9 * n + 1), S(n + 1);
    a[0] = 1;
    S[0] = 1;
    for (int k = 1; k <= n; k++) {
        fill(b.begin(), b.end(), 0);
        for (int x = 0; x <= 9 * (k - 1); x++)
            if (a[x])
                for (int z : d) {
                    b[x + z] += a[x];
                    if (b[x + z] >= MOD)
                        b[x + z] -= MOD;
                }
        a.swap(b);
        long long sum = 0;
        for (int x = 0; x <= 9 * k; x++)
            sum = (sum + 1LL * a[x] * a[x]) % MOD;
        S[k] = sum;
    }
    cout << (2LL * S[n] - 1LL * S[n / 2] * S[(n + 1) / 2] % MOD + MOD) % MOD << '\n';
}