[Codeforces856C][DP]Eleventh Birthday

翻译

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

题解

把位数是奇数和是偶数的数分开考虑
如果有i个奇数的数
显然有$floor(\frac{i}{2})$个数的贡献必须取负
偶数的数不管怎么插入奇数的数里面 奇数的数的贡献都不会改变
可以直接dp
$f[i][j][k]$表示第$i$个奇数 有$j$个贡献取负 当前模11等于$k$
$g[i][j][k]$表示第$i$个偶数 有$j$个贡献取负 当前模11等于$k$
直接转移
考虑如何合并
枚举贡献取负的偶数的数个数i
由于我们dp的时候顺序是固定的，我们还要取他的全排列
插板法乱搞就行了

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; const LL mod=998244353; inline int read() {
     int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} LL pow_mod(LL a,LL b) {
     LL ret=1;while(b){
     if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret; } LL f[2][1100][15];//前i个数 有j个贡献相反 mod 11=k LL g[2][2100][15]; //前i个数 有j个贡献相反 mod 11=k int n; int b1[2100],b2[2100],l1,l2; bool ok(int u) {
     int ret=0;while(u)ret++,u/=10;return ret&1; } int S(int u) {
     int s1=0,s2=0,gg=0;while(u){
     gg++;if(gg&1)s1+=u%10;else s2+=u%10;u/=10;}return s1-s2; } int nw1,nw2; void ad(LL &x,LL y){
     x+=y;if(x>mod)x-=mod;} LL inv[2100],pre[2100]; LL C(int n,int m){
     return pre[n]*inv[m]%mod*inv[n-m]%mod;} LL calc(int n,int m)//n个数 插入m个位置  {
     if(!m)return n?0:1;return pre[n]*C(n+m-1,m-1)%mod; } int main() {
     pre[0]=1;for(int i=1;i<=2000;i++)pre[i]=pre[i-1]*i%mod;inv[2000]=pow_mod(pre[2000],mod-2);for(int i=1999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;int T=read();while(T--){
     n=read();l1=l2=0;for(int i=1;i<=n;i++){
     int x=read();if(ok(x))b1[++l1]=(S(x)%11+11)%11;else b2[++l2]=(S(x)%11+11)%11;}memset(f,0,sizeof(f));memset(g,0,sizeof(g));f[0][0][0]=g[0][0][0]=1;nw1=0;for(int i=1;i<=l1;i++){
     nw1^=1;memset(f[nw1],0,sizeof(f[nw1]));for(int j=0;j<=l1/2;j++)for(int k=0;k<=10;k++){
     if(j!=0)ad(f[nw1][j][k],f[nw1^1][j-1][(k+b1[i])%11]);//这个负贡献ad(f[nw1][j][k],f[nw1^1][j][(k-b1[i]+11)%11]);//这个正贡献 }}nw2=0;for(int i=1;i<=l2;i++){
     nw2^=1;memset(g[nw2],0,sizeof(g[nw2]));for(int j=0;j<=l2;j++)for(int k=0;k<=10;k++){
     if(j!=0)ad(g[nw2][j][k],g[nw2^1][j-1][(k+b2[i])%11]);//这个负贡献ad(g[nw2][j][k],g[nw2^1][j][(k-b2[i]+11)%11]);//这个正贡献 }}LL ans=0;for(int k=0;k<=10;k++)for(int i=0;i<=l2;i++)//有i个偶数位的取了正贡献ad(ans,f[nw1][l1/2][k]*pre[l1/2]%mod*pre[l1-l1/2]%mod*g[nw2][i][(11-k)%11]%mod*calc(i,(l1+1)/2)%mod*calc(l2-i,l1+1-(l1+1)/2)%mod);printf("%lld\n",ans);}return 0; }