本题是多组数据。
对于每组数据,给出 个数字,求有多少种排列方式,使得排列后的 个数字首尾相接形成的数字能被 整除。答案对 取模
,。
发现一个数能被 整除当且仅当它奇数位的和和偶数位的和相等,也就是奇数位的和减去偶数位的和等于 。
那么预处理出每一个数字的奇数位减偶数位的结果 ,与每一个数字的位数 。不难发现,若 为奇数,那么它插入序列之后它后面的差会取反, 为偶数则可以随便插入而对后面没有影响。所以不妨先让所有 为奇数的 确定好位置,再让 为偶数 的插入进去。
所以设 为前 个 为奇数的 ,有 个 贡献为负,总和 的方案数(不考虑顺序)。那么有转移:
也就是相当于挑出一些 为奇数的 ,让它们贡献为负数,另外一些贡献为正数。由于并没有考虑顺序,所以最后 为奇数的 构成总和为 的序列个数为 ,其中 为 为奇数的 个数。
考虑 为偶数的 插入的方案,仿照 为奇数的 的思路,设 表示前 个 为偶数的 ,有 个 贡献为负,总和 的方案数(不考虑顺序)。那么有转移:
那么枚举 为偶数的 和 为奇数的 对总和的贡献即可,答案为:(其中 表示 为偶数的 个数, 表示 为奇数的 个数)
细节较多,代码如下:
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;
}