个人觉得此题确实不错，且各档部分分都值得一写。
40pts：状压爆搜
#include <bits/stdc++.h>#define int long longusing namespace std;const int N=21,MOD=998244353;int n,m,x,ans;int c[1<<N];char s[N];void dfs(int p,int sum){if (!p) {ans+=sum+c[0]; if (ans>=MOD) ans-=MOD; return;}for (register int i=p; i; i=(i-1)&p) if (i!=p) dfs(i,sum+c[p]);dfs(0,sum+c[p]);}signed main(){scanf("%lld%lld",&n,&m);for (register int i=1; i<=m; ++i){scanf("%s",s+1);x=0;for (register int j=n; j>=1; --j) if (s[j]=='1') x+=(1<<(n-j));scanf("%lld",&c[x]);}dfs((1<<n)-1,0);printf("%lld\n",ans); return 0;}
70pts：枚举子集，记忆化
#include <bits/stdc++.h>#define int long longusing namespace std;const int N=21,MOD=998244353;int n,m,x,ans;int c[1<<N],dp[1<<N],sum[1<<N];char s[N];int dfs(int p){if (dp[p]!=-1) return dp[p];dp[p]=0;for (register int i=p; i; i=(i-1)&p)if (i!=p){dp[p]=(dp[p]+dfs(i))%MOD; sum[p]=(sum[p]+sum[i])%MOD;//可以理解为，p的子集i向p连了有向边，sum[p]就是到达p的方案数//所以初始值sum[0]=1，本质就是拓扑排序 }dp[p]=(dp[p]+dfs(0))%MOD;sum[p]=(sum[p]+sum[0])%MOD; dp[p]=(dp[p]+(sum[p]*c[p])%MOD)%MOD;return dp[p];}signed main(){sum[0]=1;scanf("%lld%lld",&n,&m);for (register int i=1; i<=m; ++i){scanf("%s",s+1);x=0;for (register int j=n; j>=1; --j) if (s[j]=='1') x+=(1<<(n-j));scanf("%lld",&c[x]);}memset(dp,-1,sizeof(dp));dp[0]=c[0];printf("%lld\n",dfs((1<<n)-1));return 0;}
100pts：组合数学+递推
#include <bits/stdc++.h>#define int long longusing namespace std;const int N=21,MOD=998244353;int n,m,v,x,ans;int c[N][N],dp[N];char s[N];signed main(){for (register int i=0; i<=20; ++i) c[i][0]=c[i][i]=1;for (register int i=1; i<=20; ++i)for (register int j=1; j<=i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j];//dp[i]：二进制中，填i个1的方案数 dp[0]=1;for (register int i=1; i<=20; ++i)for (register int j=1; j<=i; ++j) dp[i]=(dp[i]+dp[i-j]*c[i][j]%MOD)%MOD; //dp[i]=(dp[i]+dp[i-j]*c[i][j])： 因为一次性可以填多个1，所以假设原来有j个1，这次填了i-j个1，得到i个1//那么，方案数就是：在现在的i个1中选j个位置，构成了原来的j个1，所以方案数是c[i][j]scanf("%lld%lld",&n,&m);for (register int i=1; i<=m; ++i){scanf("%s",s+1);scanf("%lld",&v);x=0;for (register int j=1; j<=n; ++j) if (s[j]=='1') x++;ans=(ans+dp[x]*dp[n-x]%MOD*v%MOD)%MOD; //当前，有x个1，那么，由0个1变成x个1，有dp[x]种方案，由x个1变成n个1有dp[n-x]个方案，//所有共有dp[x]*dp[n-x]个方案，而每个方案的贡献为v，所有贡献和累加 }printf("%lld\n",ans);return 0;}
如果觉得《洛谷 P4996 咕咕咕》对你有帮助，请点赞、收藏，并留下你的观点哦！
