Codeforces856C 题解

wzf2000
2019年8月8日

Codeforces856C 题解

题意

• 给你 $n$ 个数，询问将其按照一定顺序排列后得到的数能被 $11$ 整除的排列有几种。
• 多组询问,$T \leq 100,n \leq 2000$。

题解

• 首先我们发现 $10 \equiv -1(mod 11)$，所以可以将 $n$ 个数根据长度的奇偶性分为两类。
• 显然长度为偶数的不会影响长度为奇数的贡献。
• 而长度为奇数的从偶数位开始的数的个数必为 $\lfloor \frac{n}{2} \rfloor$ 个，偶数的从偶数位开始的数的个数可以为任意值。
• 所以我们可以得到以下状态：
  • $dp[i][j][k]$ 表示前$i$个长度为奇数的数有 $j$ 个从偶数位开始的对值贡献为 $k$ 的方案数。
  • 转移：$dp[i][j][k]=dp[i-1][j][k-a[i]]+dp[i-1][j-1][k+a[i]]$（在模 $11$ 意义下，注意 $j=0$）
  • 同理。$Dp[i][j][k]$ 表示前 $i$ 个长度为偶数的数有 $j$ 个从偶数位开始的对值贡献为 $k$ 的方案数。
  • 转移：$Dp[i][j][k]=Dp[i-1][j][k-b[i]]+Dp[i-1][j-1][k+b[i]]$（在模 $11$ 意义下，注意 $j=0$）
• 最后合并奇偶即可。

代码

#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;
}

 codeforces dp