题意

给出一些数，问将这些组合起来形成的新数能被11整除的方案数。

分析

这里要用到关于\(11\)的一个。

判断一个数能否被\(11\)整除只需要奇数位的和减去偶数位上的和被\(11\)整除即可。

证明：对于\(1, 100, 10000 ...\)，模\(11\)后都为\(1\)，而\(10, 1000...\)模\(11\)后为\(10\)，又\(-1\)与\(10\)模\(11\)同余，所以只需要考虑奇偶数位上的和之差即可。

在加入某个数之前，如果前面已经有长度为奇数的数了，那么加入的这个数模\(11\)的和应该取负。实际上我们也不用去处理输入的数，如果前面是偶数长度的数，直接加上取模后的数即可。

进一步分析，对于奇数长度的数，假设有\(cnt\)个，那么一定有\(\left \lfloor \frac{cnt}{2} \right \rfloor\)个数取负号，可以用 \(dp\) 求解仅有奇数长度的数的方案数。

对于偶数长度的数，如果没有奇数长度的数存在，那么方案数要么为 \(n!\) 要么为 \(0\) ， 否则 \(dp\) 求解将偶数长度的数插入到奇数长度的数中的方案数。

最后除了奇数长度的数不存在这种情况，偶数长度的数的正负性都是任意的，所以要枚举所有的可能性。

code

#include
    
     using namespace std;typedef long long ll;const int MAXN = 2e3 + 10;const ll MOD = 998244353;int n;vector
     
       odd, even;ll dp_odd[2][MAXN][11];  // dp_odd[i][j][k]:  前i个奇数长度的数选择了j个负数后余数为k的方案数ll dp_even[2][MAXN][11]; // dp_even[i][j][k]: 前i个偶数长度的数选择了j个负数后余数为k的方案数int isOdd(int x) {    int cnt = 0;    while(x) {        cnt++;        x /= 10;    }    return cnt & 1;}void solve() {    // 对于奇偶数长度的数分开考虑    // 对于奇数长度的数，一定有 size / 2 个数为负数，其余为正数    int negative_odd = odd.size() / 2;    int o = 1;    memset(dp_odd[o], 0, sizeof dp_odd[o]);    dp_odd[1][0][0] = 1;    for(int i = 0; i < odd.size(); i++) {        o ^= 1;        memset(dp_odd[o], 0, sizeof dp_odd[o]);        for(int j = 0; j <= min(i, negative_odd); j++) {            int negative = negative_odd - j; // 还有几个位置可以放负数            int postive = odd.size() - i - negative; // 还有几个位置可以放正数            if(postive > 0) for(int k = 0; k < 11; k++) {                (dp_odd[o][j][(k + odd[i]) % 11] += dp_odd[o ^ 1][j][k] * postive) %= MOD;            }            if(negative > 0) for(int k = 0; k < 11; k++) {                (dp_odd[o][j + 1][((k - odd[i]) % 11 + 11) % 11] += dp_odd[o ^ 1][j][k] * negative) %= MOD;            }        }    }    int e = 1;    memset(dp_even[e], 0, sizeof dp_even[e]);    dp_even[1][0][0] = 1;    // 插入偶数长度的数，只要存在奇数长度的数，那么偶数长度的数正负任意    for(int i = 0; i < even.size(); i++) {        e ^= 1;        memset(dp_even[e], 0, sizeof dp_even[e]);        for(int j = 0; j <= i; j++) {            // 考虑可以放负数的位置：当j=0时，显然只能在奇数个奇数长度的数后面放；j>0时每有一个已经放好的数，又能多提供一个位置            int negative = !odd.size() ? 0 : j + (odd.size() + 1) / 2;            int postive = odd.size() + i + 1 - negative;            if(postive > 0) for(int k = 0; k < 11; k++) {                (dp_even[e][j][(k + even[i]) % 11] += dp_even[e ^ 1][j][k] * postive) %= MOD;            }            if(negative > 0) for(int k = 0; k < 11; k++) {                (dp_even[e][j + 1][((k - even[i]) % 11 + 11) % 11] += dp_even[e ^ 1][j][k] * negative) %= MOD;            }        }    }    ll res = 0;    // 因为偶数长度的数的正负数的个数是不确定的，所以要枚举出所有的可能性    for(int i = 0; i <= even.size(); i++) {        for(int k = 0; k < 11; k++) {            (res += dp_odd[o][negative_odd][k] * dp_even[e][i][(11 - k) % 11]) %= MOD;        }    }    cout << res << endl;}int main() {    ios::sync_with_stdio(0); cin.tie(0);    int T;    cin >> T;    while(T--) {        odd.clear(); even.clear();        cin >> n;        for(int i = 0; i < n; i++) {            int x;            cin >> x;            if(isOdd(x)) odd.push_back(x);            else even.push_back(x);        }        solve();    }    return 0;}