Fork me on GitHub

Codeforces856C

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$的方案数。
    • 转移:
    • (在模11意义下,注意$j=0$)
    • 同理。$Dp[i][j][k]$表示前$i$个长度为偶数的数有$j$个从偶数位开始的对值贡献为$k$的方案数。
    • 转移:
    • (在模11意义下,注意$j=0$)
  • 最后合并奇偶即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces856C

文章作者:wzf2000

发布时间:2017年12月25日 - 12:12

最后更新:2017年12月26日 - 05:12

原始链接:https://wzf2000.github.io/2017/12/25/Codeforces856C/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。