- it
- 洛谷 P4996 咕咕咕
个人觉得此题确实不错，且各档部分分都值得一写。
40pts：状压爆搜
#include <bits/stdc++.h>
#define int long long
using 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 long
using 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
;
}
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 long
using 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
[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
;
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
;
}
printf("%lld\n",ans
);
return 0;
}
