CF856C Eleventh Birthday 做题记录

本题是多组数据。

对于每组数据，给出 $n$ 个数字，求有多少种排列方式，使得排列后的 $n$ 个数字首尾相接形成的数字能被 $11$ 整除。答案对 $998244353$ 取模

$1\le n\le 2000$，$1\le a_i\le 10^9$。

发现一个数能被 $11$ 整除当且仅当它奇数位的和和偶数位的和相等，也就是奇数位的和减去偶数位的和等于 $0$。

那么预处理出每一个数字的奇数位减偶数位的结果 $a_i$，与每一个数字的位数 $len_i$。不难发现，若 $len_i$ 为奇数，那么它插入序列之后它后面的差会取反，$len_i$ 为偶数则可以随便插入而对后面没有影响。所以不妨先让所有 $len_i$ 为奇数的 $a_i$ 确定好位置，再让 $len_i$ 为偶数 $a_i$ 的插入进去。

所以设 $dp_{i,j,k}$ 为前 $i$ 个 $len_i$ 为奇数的 $a_i$，有 $j$ 个 $a_i$ 贡献为负，总和 $\operatorname{mod} 11=k$ 的方案数（不考虑顺序）。那么有转移：

$dp_{i,j,k}=dp_{i-1,j,k-a_i}+dp_{i-1,j-1,k+a_i}$

也就是相当于挑出一些 $len_i$ 为奇数的 $a_i$，让它们贡献为负数，另外一些贡献为正数。由于并没有考虑顺序，所以最后 $len_i$ 为奇数的 $a_i$ 构成总和为 $k$ 的序列个数为 $\lfloor\frac{cnt_1}{2}\rfloor!(cnt_1-\lfloor\frac{cnt_1}{2}\rfloor)!dp_{cnt_1,\lfloor\frac{cnt_1}{2}\rfloor,k}$，其中 $cnt_1$ 为 $len_i$ 为奇数的 $a_i$ 个数。

考虑 $len_i$ 为偶数的 $a_i$ 插入的方案，仿照 $len_i$ 为奇数的 $a_i$ 的思路，设 $pd_{i,j,k}$ 表示前 $i$ 个 $len_i$ 为偶数的 $a_i$，有 $j$ 个 $a_i$ 贡献为负，总和 $\operatorname{mod} 11=k$ 的方案数（不考虑顺序）。那么有转移：

$pd_{i,j,k}=pd_{i-1,j,k-a_i}+pd_{i-1,j-1,k+a_i}$

那么枚举 $len_i$ 为偶数的 $a_i$ 和 $len_i$ 为奇数的 $a_i$ 对总和的贡献即可，答案为：（其中 $cnt_0$ 表示 $len_i$ 为偶数的 $a_i$ 个数，$cnt_1$ 表示 $len_i$ 为奇数的 $a_i$ 个数）

$\sum\limits_{i=0}^{10}\lfloor\frac{cnt_1}{2}\rfloor!\lceil\frac{cnt_1}{2}\rceil!dp_{cnt_1,\lfloor\frac{cnt_1}{2}\rfloor,i}\sum\limits_{j=0}^{cnt_0}j!\binom{j+\lfloor\frac{cnt_1+1}{2}\rfloor-1}{\lfloor\frac{cnt_1+1}{2}\rfloor-1}(cnt_0-j)!\binom{cnt_0-j+\lceil\frac{cnt_1+1}{2}\rceil-1}{\lceil\frac{cnt_1+1}{2}\rceil-1}pd_{cnt_0,j,11-i}$

细节较多，代码如下：

int fra[S*2],C[S*2][S*2];
int n,a[S],b[S];
int cnt0,cnt1,id0[S],id1[S];
int dp[2][S][11],pd[2][S][11];

inline int calc(int n,int m)
{
	if(m==0) return n==0;
	return 1ll*fra[n]*C[n+m-1][m-1]%p;
}

inline void slove()
{
	cin>>n;
	cnt0=cnt1=0;
	for(int i=1;i<=n;i++) a[i]=0;
	for(int i=1;i<=n;i++)
	{
		long long x;
		cin>>x;
		long long tmp=x;
		int tot=0;
		do b[++tot]=tmp%10,tmp/=10;
		while(tmp>0);
		if(tot&1) id1[++cnt1]=i;
		else id0[++cnt0]=i;
		bool odd=true;
		while(tot>0) a[i]=(a[i]+(odd?1:-1)*b[tot--]+11)%11,odd=!odd;
	}
	for(int i=0;i<=1;i++) for(int j=0;j<=n;j++) for(int k=0;k<11;k++) dp[i][j][k]=pd[i][j][k]=0;
	dp[0][0][0]=1;
	for(int i=1;i<=cnt1;i++)
	{
		int u=i&1,v=i-1&1;
		for(int j=0;j<=i;j++) for(int k=0;k<11;k++) dp[u][j][k]=(dp[v][j][(k-a[id1[i]]+11)%11]+(j>0?dp[v][j-1][(k+a[id1[i]])%11]:0))%p;
	}
	pd[0][0][0]=1;
	for(int i=1;i<=cnt0;i++)
	{
		int u=i&1,v=i-1&1;
		for(int j=0;j<=i;j++) for(int k=0;k<11;k++) pd[u][j][k]=(pd[v][j][(k-a[id0[i]]+11)%11]+(j>0?pd[v][j-1][(k+a[id0[i]])%11]:0))%p;
	}
	int ans=0;
	for(int i=0;i<11;i++)
	{
		int ndel=cnt1/2+1,nadd=cnt1-cnt1/2;
		int mul=1ll*fra[cnt1/2]*fra[cnt1-cnt1/2]%p*dp[cnt1&1][cnt1/2][i]%p,sum=0;
		for(int j=0;j<=cnt0;j++) sum=(sum+1ll*calc(j,ndel)*calc(cnt0-j,nadd)%p*pd[cnt0&1][j][(11-i)%11]%p)%p;
		ans=(ans+1ll*mul*sum%p)%p;
	}
	cout<<ans<<endl;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S*2-2;i++) fra[i]=1ll*fra[i-1]*i%p;
	C[0][0]=1;
	for(int i=1;i<=S*2-2;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	int T=1;
	cin>>T;
	while(T-->0)
	{
		slove();
	}
	return 0;
}