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 |
|