【洛谷11月月赛T3】【P4996】咕咕咕(组合数)
迟到的题解 昨天乱翻的时候感觉这道题挺有意思的
一眼看过去状态压缩乱搜
转移方程大概是 设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