Codeforces856C 题解

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define mod 998244353
#define N 2009
#define add(x,y) (x=((x)+(y)>=mod)?((x)+(y)-mod):((x)+(y)))
using namespace std;
int n,a[N],b[N],c[N],dp[N][N][11],Dp[N][N][11],n1,n2;
int p[N],inv[N];
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return x*s;
}
int C(int n,int m)
{
    return (ll)p[n]*inv[m]%mod*inv[n-m]%mod;
}
int get(int m,int n)
{
    if (m==0) return n?0:1;
    return (ll)p[n]*C(n+m-1,n)%mod;
}
int main()
{
    int T=read();
    p[0]=1;
    for (int i=1;i<N;i++) p[i]=(ll)p[i-1]*i%mod;
    inv[0]=inv[1]=1;
    for (int i=2;i<N;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    for (int i=2;i<N;i++) inv[i]=(ll)inv[i]*inv[i-1]%mod;
    while (T--)
    {
        n=read(),n1=n2=0;
        for (int i=1;i<=n;i++)
        {
            a[i]=read();
            int len=0,now=a[i];
            while (now)
            {
                now/=10;
                len++;
            }
            if (len&1) b[++n1]=a[i]%11;
            else c[++n2]=a[i]%11;
        }
        for (int i=0;i<=n;i++)
            for (int j=0;j<11;j++) dp[0][i][j]=Dp[0][i][j]=0;
        dp[0][0][0]=1;
        for (int i=1;i<=n1;i++)
        {
            for (int j=0;j<=i;j++)
                for (int k=0;k<11;k++)
                {
                    dp[i][j][k]=0;
                    add(dp[i][j][k],dp[i-1][j][(k-b[i]+11)%11]);
                    if (j) add(dp[i][j][k],dp[i-1][j-1][(k+b[i])%11]);
                }
        }
        Dp[0][0][0]=1;
        for (int i=1;i<=n2;i++)
        {
            for (int j=0;j<=i;j++)
                for (int k=0;k<11;k++)
                {
                    Dp[i][j][k]=0;
                    add(Dp[i][j][k],Dp[i-1][j][(k-c[i]+11)%11]);
                    if (j) add(Dp[i][j][k],Dp[i-1][j-1][(k+c[i])%11]);
                }
        }
        int Ans=0;
        for (int i=0;i<=n2;i++)
            for (int k=0;k<11;k++)
                add(Ans,(ll)dp[n1][n1/2][k]*p[n1/2]%mod*p[n1-n1/2]%mod*Dp[n2][i][(11-k)%11]%mod*get(n1+1-(n1+1)/2,n2-i)%mod*get((n1+1)/2,i)%mod);
        printf("%d\n",Ans);
    }
    return 0;
}