本文主要是介绍codeforces 856C Eleventh Birthday，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意为：给你n个数字，求将它们拼接起来能被11整除的排列有多少种。
首先有这样一个算是结论的东西，由于我们在一个旧数字后面添加一个新数字，就相当于给原数字*10的新数字长度次方+新数字，推一下就可以得到10的奇数次方%11为-1，偶数则为1，那么我们就可以将新数字的长度分为奇数和偶数分别有cnt1，cnt2个进行分类讨论。
那么我们可以用dp1[i][j][k]表示考虑到前i个长度为奇数的数字，在奇数位填了j个，取模之后的答案为k的方案数，dp2[i][j][k]表示考虑到前i个长度为偶数的数字，在奇数位填了j个，取模之后的答案为k的方案数。为什么要特别将奇数位特别拿出来计算，因为在奇数位置的数字，贡献与偶数位置的数字是相反的。
通过简单背包的转移，我们可以得到dp1[i][j][k]=dp1[(i-1][j][((k-a[i])%11+11)%11]+dp[i-1][j-1][(k+a[i])%11]的状态转移方程，分别代表不放到奇数位和放到奇数位，对于dp2同理可得。
但是这样得到的dp1是按顺序放的，放在奇数位的数字和放在偶数位的数字排列不同还会得到不同的答案，由于最终答案肯定选了全部cnt1个数字，其中肯定有cnt1/2个填在了奇数位，那么我们对于每一个dp1[cnt1][cnt1/2][i] 都给它乘上（cnt1/2）的阶乘在乘上（cnt1-cnt1/2）的阶乘即得到了所有奇数位数字可能的情况。
在求解最后答案的时候，只要和取模为11，dp2可以选择任何多的数字放在奇数位，因为不影响其他的奇偶性，所以我们就可以枚举在偶数长度的数字在奇数位放多了j个，只算dp1的数字和为k,那么初步可以得到ans+=(dp1[cnt1][cnt1/2][k]*dp[cnt2][j][11-k]的求解方案的方法。
但是在枚举的时候，与dp1同理，由于放在奇数位置的偶数长度的数字有j个，而且不同排列方法并不影响结果，所以还有j的阶乘种不同排列方法，而且这j个数字插在不同的地方，答案也不一样，因为dp1中共有(cnt1+1)/2)可以给奇数位插入的方式，要将j个数字插入，由插板法可以得到在之前基础上还有c[(cnt1+1)/2+j-1][j-1]中不同的排列方式，将数字插入到偶数位同理，我们将这个过程定义为getans(n,m)表示总共有n个要插入的数字，m个位置，那么我们最后计算答案的方式就是ans+=(dp1[cnt1][cnt1/2][k]*dp[cnt2][j][11-k]*getans(i,(cnt1+1)/2))*getans(cnt2-i,cnt1+1-(cnt1+1)/2)。
特别的，存在一种情况会没有奇数位的数字，这样的话我们就没有机会将偶数位的数字插入到奇数位了，所以在getans(n,m)的时候要特判m是否为0，如果为0的话，如果n不等于0，那么这种情况显然是不合法的，答案为0，如果n也等于0，即为0个数字插入到0个位置，那么这种情况下答案为1，就是什么也不做。
下附AC代码。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 2005
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n;
int cnt1,cnt2;
ll fac[maxn],a[maxn],b[maxn];
ll c[maxn][maxn],dp1[2][maxn][11],dp2[2][maxn][11];
int lowbit(int now)
{return (now&(-now));
}
int getlen(int now)
{int res=0;while(now){res++;now/=10;}return res;
}
ll getans(ll x,ll y)
{if(y!=0) return (fac[x]*c[x+y-1][y-1])%mod;else if(x) return 0;return 1;
}
int main()
{fac[0]=1;for(int i=1;i<=2000;i++)fac[i]=(fac[i-1]*i)%mod;c[0][0]=1;for(int i=1;i<=2000;i++){c[i][0]=c[i][i]=1;for(int j=1;j<2000;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}int _;scanf("%d",&_);while(_--){memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2));memset(a,0,sizeof(a));memset(b,0,sizeof(b));cnt1=cnt2=0;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);int len=getlen(x);if(len&1) a[++cnt1]=x%11;else b[++cnt2]=x%11;}dp1[0][0][0]=dp2[0][0][0]=1;for(int i=1;i<=cnt1;i++){memset(dp1[i&1],0,sizeof(dp1[i&1]));for(int j=0;j<=cnt1/2;j++){for(int k=0;k<=10;k++){dp1[i&1][j][k]=dp1[(i&1)^1][j][((k-a[i])%11+11)%11];if(j!=0) dp1[i&1][j][k]+=dp1[(i&1)^1][j-1][(k+a[i])%11];if(dp1[i&1][j][k]>=mod) dp1[i&1][j][k]-=mod;}}}for(int i=1;i<=cnt2;i++){memset(dp2[i&1],0,sizeof(dp2[i&1]));for(int j=0;j<=cnt2;j++){for(int k=0;k<=10;k++){dp2[i&1][j][k]=dp2[(i&1)^1][j][(k-b[i]+11)%11];if(j!=0) dp2[i&1][j][k]+=dp2[(i&1)^1][j-1][(k+b[i])%11];if(dp2[i&1][j][k]>=mod) dp2[i&1][j][k]-=mod;}}}for(int k=0;k<=10;k++){dp1[cnt1&1][cnt1/2][k]=(dp1[cnt1&1][cnt1/2][k]*fac[cnt1/2]%mod*fac[cnt1-cnt1/2])%mod;}ll ans=0;for(int i=0;i<=cnt2;i++){for(int j=0;j<=10;j++){ll temp=(dp1[cnt1&1][cnt1/2][j]*dp2[cnt2&1][i][(11-j)%11])%mod;temp=(temp*getans(i,(cnt1+1)/2))%mod;temp=(temp*getans(cnt2-i,cnt1+1-(cnt1+1)/2))%mod;ans=(ans+temp)%mod;}}printf("%I64d\n",ans);}
}
这篇关于codeforces 856C Eleventh Birthday的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
