迟到的题解 昨天乱翻的时候感觉这道题挺有意思的
一眼看过去状态压缩乱搜
转移方程大概是 设f[i]表示从0转移到i的遗憾值之和 f[i]=sigma(f[j])+val[i]*dis[i] dis[i]=sigma(dis[j]) 其中j是i的子集,dis[i]表示从0转移到i的方案数之和
妙啊有70分了
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 20 #define mod 998244353 #define ll long long using namespace std; int n,m; ll val[1<<(N+1)],dp[1<<(N+1)],dis[1<<(N+1)]; char s[N+5]; inline ll dfs(int state) { if(state==0) return val[state]; if(dp[state]!=-1) return dp[state]; dp[state]=0; for(int i=state&(state-1);i;i=(i-1)&state) { dp[state]=(dp[state]+dfs(i))%mod; dis[state]=(dis[state]+dis[i])%mod; } dp[state]=(dp[state]+dfs(0))%mod; //因为上面算子集没有算到0 dis[state]=(dis[state]+dis[0])%mod; dp[state]=(dp[state]+val[state]*dis[state]%mod)%mod; return dp[state]; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { scanf("%s",s+1); ll sum=0; for(int j=1;j<=n;j++) if(s[j]=='1') sum+=(1<<(n-j)); cin>>val[sum]; } int max_state=(1<<n)-1; dis[0]=1; memset(dp,-1,sizeof(dp)); dfs(max_state); cout<<dp[max_state]; return 0; }然而正解是组合数
分析上面的过程你会发现：要是能够快速的算出从0到当前状态的方案数就好了
然后又发现和具体的状态没有什么关系 之和0,1的个数有关系
记f[i]表示i个1的方案数 先预处理出来
显然f[i]可以从子集j转移过来 可以用到组合数的思想 即sigma(c(i,j)*f[j])
然后对于每个可能带来歉意的状态 根据一个乘法原理 相当于先把这n个0变为i个1 再把i个1变为n个1
#include<bits/stdc++.h> #define N 25 #define mod 998244353 #define ll long long using namespace std; int n,m; ll ans,c[N+5][N+5],f[N]; char s[N]; void init() { for(int i=0;i<=N;i++) c[i][0]=1,c[i][i]=1; for(int i=1;i<=N;i++) { for(int j=1;j<=i;j++) { c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } } f[1]=1,f[0]=1; for(int i=2;i<=20;i++) for(int j=0;j<i;j++) f[i]=(f[i]+c[i][j]*f[j]%mod)%mod; } int main() { cin>>n>>m; init(); for(int i=1;i<=m;i++) { scanf("%s",s+1); ll cnt=0; for(int j=1;j<=n;j++) if(s[j]=='1') cnt++; ll x; cin>>x; ans=(ans+x*f[cnt]%mod*f[n-cnt]%mod)%mod; } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9913494.html
相关资源：各显卡算力对照表！