标签：组合数
题目
题目传送门
题目描述
小 F 是一个能鸽善鹉的同学，他经常把事情拖到最后一天才去做，导致他的某些日子总是非常匆忙。
比如，时间回溯到了 年 11 月 3 日。小 F 望着自己的任务清单：
看 iG 夺冠；补月赛题的锅。
小 F 虽然经常咕咕咕，但他完成任务也是很厉害的，他一次性可以完成剩余任务的任一非空子集。比如，他现在可以选择以下几种中的一种：
看 iG 夺冠；补月赛题的锅；一边看 iG 夺冠的直播，一边补锅。
当然，比赛实在是太精彩了，所以小 F 就去看比赛了。
不过，当金雨从天而降、IG 举起奖杯之时，小 F 突然心生愧疚——锅还没补呢！于是，小 F 的内心产生了一点歉意。
这时小 F 注意到，自己总是在某些情况下会产生歉意。每当他要检查自己的任务表来决定下一项任务的时候，如果当前他干了某些事情，但是没干另一些事情，那么他就会产生一定量的歉意——比如，无论他今天看没看比赛，只要没有补完月赛的锅，他都会在选择任务的时候产生 1 1 1 点歉意。小 F 完成所有任务后，他这一天的歉意值等于他每次选择任务时的歉意之和。
过高的歉意值让小 F 感到不安。现在，小 F 告诉你他还有 n n n 项任务，并告诉你在 m m m 种情况中的一种 s t a t e i \mathrm{state}_i statei 的情况下，小 F 会产生 a i a_i ai 点歉意。请你帮忙计算一下，小 F 在那一天所有可能的完成所有任务方式的歉意值之和是多少。
由于答案可能很大，你只需要输出答案对 998244353 998244353 998244353 取模即可。
输入输出格式
输入格式
输入一行两个整数 n , m n, m n,m，表示有 n n n 项任务，在 m m m 种情况中下小 F 会产生歉意值。
输入接下来 m m m 行，每行有一个长度为 n n n 的 0 − 1 0-1 0−1 串 s t a t e i \mathrm{state}_i statei 和一个歉意值 a i a_i ai， s t a t e i , j \mathrm{state}_{i, j} statei,j 为 0 / 1 0/1 0/1 表示第 j j j 项任务此时没做 / 已经做了。
详情请参考样例和样例解释。
输出格式
输出一行一个整数，表示小 F 在那一天所有可能的完成任务方式的歉意值之和对 998244353 998244353 998244353 取模的结果。
输入输出样例
输入样例#1
2 200 110 1
输出样例#1
4
输入样例#2
3 4000 16001 9110 4111 1
输出样例#2
260
说明
样例 1 解释：
0 − 1 0-1 0−1 串中第一个数字表示小 F 看没看比赛，第二个数字表示小 F 补没补锅。
我们用 ∅ \varnothing ∅ 表示小 F 什么都没干， A A A 表示小 F 看了比赛， B B B 表示小 F 补了锅，那么所有会产生愧疚的方式如下：
∅ : 1 \varnothing: 1 ∅:1
{ A } : 1 \{A\}:1 {A}:1
那么所有可能的选择如下：
∅ → { A } → { A , B } : 2 \varnothing\rightarrow\{A\}\rightarrow\{A,B\}:2 ∅→{A}→{A,B}:2
∅ → { B } → { A , B } : 1 \varnothing\rightarrow\{B\}\rightarrow\{A,B\}:1 ∅→{B}→{A,B}:1
∅ → { A , B } : 1 \varnothing\rightarrow\{A,B\}:1 ∅→{A,B}:1
所以答案是 2 + 1 + 1 = 4 2 + 1 + 1 = 4 2+1+1=4。
数据范围
保证出现的 s t a t e i \mathrm{state}_i statei 互不相同。
对于所有数据，有 1 ≤ n ≤ 20 1 \leq n \leq 20 1≤n≤20, 1 ≤ m ≤ min ( 2 n , 1 0 5 ) , 1 ≤ a i ≤ 1 0 5 1 \leq m \leq \min(2 ^ n, 10 ^ 5), 1 \leq a_i \leq 10 ^ 5 1≤m≤min(2n,105),1≤ai≤105。
分析
n=20大概会误导人去写状压DP吧，然而我太弱了并不会去写状压
题意：给出m个二进制数，每个数对应一个权值，求从一个二进制数a转换到b的方案的代价（转换中每个数出现的次数乘上各自权值）
考虑方案计数可以累乘，所以可以分别考虑这m个数产生的代价
opt[i]为填入i个1的方案数
o p t [ i ] = ∑ j = 1 i o p t [ i − j ] × C i j opt[i]=\sum_{j=1}^i opt[i-j]\times C_{i}^j opt[i]=∑j=1iopt[i−j]×Cij
先预处理递推求出组合数，和opt数组
之后在线计算答案
code
#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ll long long#define mem(x,num) memset(x,num,sizeof x)#define reg(x) for(int i=last[x];i;i=e[i].next)using namespace std;inline ll read(){ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}//**********head by yjjr**********#define mod 998244353ll opt[26],c[26][26],ans,a,num;int n,m,flag;int main(){c[0][0]=1;rep(i,1,20)c[i][0]=1;rep(i,1,20)rep(j,1,i)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;opt[0]=1;rep(i,1,20)rep(j,1,i)opt[i]=(opt[i]+opt[i-j]*c[i][j])%mod;char ch;n=read(),m=read();rep(i,1,m){num=0;flag=0;while(flag<n){while((ch=getchar())<'0'||ch>'1');if(ch=='1')++num;++flag;}a=read();ans=(ans+1ll*a*opt[num]%mod*opt[n-num]%mod)%mod;}cout<<ans<<endl;return 0;}
如果觉得《洛谷4996 咕咕咕》对你有帮助，请点赞、收藏，并留下你的观点哦！
