[Codeforces]856C - Eleventh Birthday

时间：2021-07-30 05:50:58

题目大意：给出n个数，问有多少种排列把数字接起来是11的倍数。（n<=2000）

做法：一个数后面接一个数等同于乘上10的若干次幂然后加上这个数，10模11等于-1，所以10的若干次幂是-1或1，根据这个把长度奇和偶的分开考虑，他们最后对和的贡献都是可以确定的几段正几段负，f[i][j][k]表示前i个长度为奇/偶的数，j个贡献为负，对和的贡献为k的方案数，最后再排列组合比较容易可以算出答案，复杂度O(11*n^2)。

代码：

#include<cstdio>

#include<cstring>

inline int read()

{

    int x;char c;

    while((c=getchar())<''||c>'');

    for(x=c-'';(c=getchar())>=''&&c<='';)x=x*+c-'';

    return x;

}

#define MN 2000

#define MOD 998244353

int a[MN+],an,b[MN+],bn,C[MN+][MN+],f1[MN+][MN+][],f2[MN+][MN+][],v[],p[MN+];

inline int mod(int x){return x<MOD?x:x-MOD;}

inline int f(int n,int m){return m?1LL*p[n]*C[n+m-][m-]%MOD:n?:;}

int main()

{

    int T,n,i,j,k,x,ans;

    for(p[]=i=;i<=MN;++i)p[i]=1LL*p[i-]*i%MOD;

    for(i=;i<=MN;++i)for(C[i][]=j=;j<=i;++j)C[i][j]=mod(C[i-][j-]+C[i-][j]);

    for(i=;i<;++i)v[i]=i%;

    for(T=read();T--;)

    {

        n=read();an=bn=;

        for(;n--;(j&?a[++an]:b[++bn])=x%)for(k=x=read(),j=;k;k/=)++j;

        for(f1[][][]=,i=;i<=an;++i)for(j=;j<=an/;++j)for(k=;k<;++k)

            f1[i][j][k]=mod((j?f1[i-][j-][v[k+a[i]]]:)+f1[i-][j][v[k+-a[i]]]);

        for(f2[][][]=,i=;i<=bn;++i)for(j=;j<=bn;++j)for(k=;k<;++k)

            f2[i][j][k]=mod((j?f2[i-][j-][v[k+b[i]]]:)+f2[i-][j][v[k+-b[i]]]);

        for(j=;j<;++j)f1[an][an/][j]=1LL*f1[an][an/][j]*p[an/]%MOD*p[an-an/]%MOD;

        for(ans=i=;i<=bn;++i)for(j=;j<;++j)

            ans=(ans+1LL*f1[an][an/][j]*f2[bn][i][v[-j]]%MOD*f(i,(an+)/)%MOD*f(bn-i,an+-(an+)/))%MOD;

        printf("%d\n",ans);

    }

}

相关文章