設要取的物品集合為$S$，$E=n(m-1)+(n-1)m$，$x_T$為覆蓋了$T$中至少一個元素的$1\times2$數量

$$\begin{aligned}\sum\limits_{i=1}^\infty i[恰好i次]&=\sum\limits_{i=1}^\infty[\geq i次]\\&=\sum\limits_{i=0}^\infty[i次后未成功]\\&=\sum\limits_{i=0}^\infty\sum\limits_{\substack{T\subseteq S\\T\ne\varnothing}}(-1)^{|T|+1}\left(1-\frac{x_T}E\right)^i\\&=E\sum\limits_{\substack{T\subseteq S\\T\ne\varnothing}}(-1)^{|T|+1}\frac1{x_T}\end{aligned}$$

所以要對每個$1\leq k\leq E$計數有多少個大小為奇數/偶數的集合$T$滿足$x_T=k$

考慮按列-行做輪廓線DP，設$f_{i,j,k,0/1}$表示當前DP到第$i$個格子，當前輪廓線上“=*且在$T$中”的狀態為$j$，$x_T=k$，$|T|\equiv0/1\pmod2$的$T$的數量

時間復雜度$O(n^2m^22^n)$

#include<stdio.h> #include<string.h> typedef long long ll; const int mod=998244353; int mul(int a,int b){return(ll)a*b%mod;} void inc(int&a,int b){(a+=b)>=mod?a-=mod:0;} int de(int a,int b){return(a-=b)<0?a+mod:a;} int pow(int a,int b){int s=1;while(b){if(b&1)s=mul(s,a);a=mul(a,a);b>>=1;}return s; } char s[10][110]; int n,m,E; int inv[1210],f[64][1210][2],g[64][1210][2]; int is(int x,int k){return k>=0?x>>k&1:0; } int main(){int i,j,k,l,u,v,res;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%s",s[i]+1);E=n*(m-1)+(n-1)*m;inv[1]=1;for(i=2;i<=E;i++)inv[i]=mul(mod/i,mod-inv[mod%i]);f[0][0][0]=1;for(j=1;j<=m;j++){for(i=1;i<=n;i++){memset(g,0,sizeof(g));for(k=0;k<1<<n;k++){for(l=0;l<=E;l++){if(!(f[k][l][0]|f[k][l][1]))continue;u=k&~(1<<(i-1));v=l+is(k,i-1)+is(k,i-2);inc(g[u][v][0],f[k][l][0]);inc(g[u][v][1],f[k][l][1]);if(s[i][j]=='*'){u=k|(1<<(i-1));v=l+(i>1)+(j>1);inc(g[u][v][0],f[k][l][1]);inc(g[u][v][1],f[k][l][0]);}}}memcpy(f,g,sizeof(g));}}res=0;for(i=1;i<=E;i++){u=v=0;for(j=0;j<1<<n;j++){inc(u,f[j][i][1]);inc(v,f[j][i][0]);}inc(res,mul(inv[i],de(u,v)));}printf("%d",mul(res,E)); }

轉載于:https://www.cnblogs.com/jefflyy/p/10433422.html

總結

以上是生活随笔為你收集整理的[UOJ422]小Z的礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。