CF856C Eleventh Birthday 做题记录

本题是多组数据。

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

1n20001\le n\le 20001ai1091\le a_i\le 10^9

发现一个数能被 1111 整除当且仅当它奇数位的和和偶数位的和相等,也就是奇数位的和减去偶数位的和等于 00

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

所以设 dpi,j,kdp_{i,j,k} 为前 iilenilen_i 为奇数的 aia_i,有 jjaia_i 贡献为负,总和 mod11=k\operatorname{mod} 11=k 的方案数(不考虑顺序)。那么有转移:

dpi,j,k=dpi1,j,kai+dpi1,j1,k+aidp_{i,j,k}=dp_{i-1,j,k-a_i}+dp_{i-1,j-1,k+a_i}

也就是相当于挑出一些 lenilen_i 为奇数的 aia_i,让它们贡献为负数,另外一些贡献为正数。由于并没有考虑顺序,所以最后 lenilen_i 为奇数的 aia_i 构成总和为 kk 的序列个数为 cnt12!(cnt1cnt12)!dpcnt1,cnt12,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},其中 cnt1cnt_1lenilen_i 为奇数的 aia_i 个数。

考虑 lenilen_i 为偶数的 aia_i 插入的方案,仿照 lenilen_i 为奇数的 aia_i 的思路,设 pdi,j,kpd_{i,j,k} 表示前 iilenilen_i 为偶数的 aia_i,有 jjaia_i 贡献为负,总和 mod11=k\operatorname{mod} 11=k 的方案数(不考虑顺序)。那么有转移:

pdi,j,k=pdi1,j,kai+pdi1,j1,k+aipd_{i,j,k}=pd_{i-1,j,k-a_i}+pd_{i-1,j-1,k+a_i}

那么枚举 lenilen_i 为偶数的 aia_ilenilen_i 为奇数的 aia_i 对总和的贡献即可,答案为:(其中 cnt0cnt_0 表示 lenilen_i 为偶数的 aia_i 个数,cnt1cnt_1 表示 lenilen_i 为奇数的 aia_i 个数)

i=010cnt12!cnt12!dpcnt1,cnt12,ij=0cnt0j!(j+cnt1+121cnt1+121)(cnt0j)!(cnt0j+cnt1+121cnt1+121)pdcnt0,j,11i\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;
}