本文移植自个人的原博客（原文）

题目链接

题目描述

题解

根据小学数论知识可知如果该数可被$11$整除，要求其奇数位和与偶数位和在模$11$下同余，那么我们只需要记录通过背包DP出奇数位的和与偶数位的和为$0$时的方案数即可，但是该题中拼到一起的条件对于该数首位是奇数还是偶数是约束的，那么不妨设有$X$个数长度为奇数，$N−X$个数长度为偶数，考虑以下两种情况：

在当前数后拼入奇数长度的数时，下一个拼入的数的首位奇偶性将与该数相异。
在当前数后拼入偶数长度的数时，下一个拼入的数的首位奇偶性将与该数相同。

为了简便运算，可以设奇数长度的数每一个数奇数位与偶数位的差为$f_i$，偶数长度的数每一个数奇数位与偶数位的差为$g_i$，那么根据以上两种情况，可知最后拼出的数字的奇偶位差值，一定由$(X+1)/2$个$+f$和$X/2$个$−f$组成，而对于$N−X$个$g$值，其对最后数字的贡献首位奇偶性性任意（即正负号任意）。（需要注意的是，当$X=0$时，此时所有$N$个数的贡献均为正数，又因此这$N$个数的顺序任意，所以答案为$N!$或$0$，该情况特判掉即可）

对于以上约束，可以在背包时多开一维表示当前加入了几个正的贡献，并且对于$f$与$g$分别进行DP：

$dp[i][j][k]$表示在$f$的前$i$中取了$j$个正的，达到背包容量为$k$时的总方案数。
$w[i][j][k]$表示在$g$的前$i$中取了$j$个正的，达到背包容量为$k$时的总方案数。

则dp的最终状态应为$dp[X][(X+1)/2][k]$，对应的$w$的合法状态为$w[N−X][j][11−k]$，累加计算即可，需要注意的是，对于方程的第二维，其加入的顺序可以是任意的，所以要乘以相应的排列。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+1;
const int mod = 998244353;
int T,n,t[2],k[N],f[N],q[N];
ll fac[N],dp[2][3001][11],w[2][3001][11];
int main()
{
//    freopen("c.in","r",stdin);
    fac[0]=1;
    for(int i=1;i<N;++i)fac[i]=(fac[i-1]*i)%mod;
    scanf("%d",&T);
    while(T--)
    {
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1,x;i<=n;++i)
        {
            scanf("%d",&x);
            int tmp=0;
            t[0]=t[1]=0;
            while(x)
            {
                ++tmp;
                t[tmp&1]+=x%10;
                x/=10;
            }
            f[i]=(t[1]-t[0]+1100)%11;
            k[i]=tmp&1;
        }
        q[0]=0;
        for(int i=1;i<=n;++i)
        if(k[i])q[++q[0]]=i;
        if(q[0]==0)
        {
            int tot=0;
            for(int i=1;i<=n;++i)
            tot=(tot+f[i])%11;
            if(tot==0)cout<<fac[n]<<endl;
            else    cout<<0<<endl;
            continue;
        }
        dp[0][0][0]=1;
        for(int i=1;i<=q[0];++i)
        {
            memset(dp[i&1],0,sizeof(dp[i&1]));
            int x=q[i];
            for(int t1=0;t1<=i;++t1)
            for(int k=0;k<11;++k)
            {
                if(t1!=0)(dp[i&1][t1][k]+=dp[(i-1)&1][t1-1][(k-f[x]+11)%11]*t1)%=mod;
                if(t1!=i)(dp[i&1][t1][k]+=dp[(i-1)&1][t1][(k+f[x]+11)%11]*(i-t1))%=mod;
            }
        }
        int x=0,y=1;
        w[0][0][0]=1;
        int K=(q[0]+1)/2;
        int kk=q[0]-K+1;
        int tmp=0;
        for(int i=1;i<=n;++i)
        if(!k[i])
        {
            tmp++;
            swap(x,y);
            memset(w[x],0,sizeof(w[x]));
            for(int t1=0;t1<=tmp;++t1)
            for(int k=0;k<11;++k)
            {
                if(t1!=0)(w[x][t1][k]+=w[y][t1-1][(k-f[i]+11)%11]*(kk+(t1-1)))%=mod;
                if(t1!=tmp)(w[x][t1][k]+=w[y][t1][(k+f[i]+11)%11]*(K+(tmp-t1-1)))%=mod;
            }
        }
        ll ans=0;
        for(int i=0;i<=n-q[0];++i)
        for(int j=0;j<11;++j)
        {
            (ans+=dp[q[0]&1][K][(11-j)%11]*w[x][i][j])%=mod;
        }
        cout<<ans<<endl;
    }
}
/*
1
3
1 1 11
*/

Codeforces856C Eleventh Birthday

题目链接

题目描述

题解