洛谷4996 咕咕咕

fstqwq骗人去写状压DP,摔)

Posted by yjjr's blog on November 6, 2018

标签:组合数

题目

题目传送门

题目描述

小 F 是一个能鸽善鹉的同学,他经常把事情拖到最后一天才去做,导致他的某些日子总是非常匆忙。

比如,时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单:

  1. 看 iG 夺冠;
  2. 补月赛题的锅。

小 F 虽然经常咕咕咕,但他完成任务也是很厉害的,他一次性可以完成剩余任务的任一非空子集。比如,他现在可以选择以下几种中的一种:

  1. 看 iG 夺冠;
  2. 补月赛题的锅;
  3. 一边看 iG 夺冠的直播,一边补锅。

当然,比赛实在是太精彩了,所以小 F 就去看比赛了。

不过,当金雨从天而降、IG 举起奖杯之时,小 F 突然心生愧疚——锅还没补呢!于是,小 F 的内心产生了一点歉意。

这时小 F 注意到,自己总是在某些情况下会产生歉意。每当他要检查自己的任务表来决定下一项任务的时候,如果当前他干了某些事情,但是没干另一些事情,那么他就会产生一定量的歉意——比如,无论他今天看没看比赛,只要没有补完月赛的锅,他都会在选择任务的时候产生 点歉意。小 F 完成所有任务后,他这一天的歉意值等于他每次选择任务时的歉意之和。

过高的歉意值让小 F 感到不安。现在,小 F 告诉你他还有 项任务,并告诉你在 种情况中的一种 的情况下,小 F 会产生 点歉意。请你帮忙计算一下,小 F 在那一天所有可能的完成所有任务方式的歉意值之和是多少。

由于答案可能很大,你只需要输出答案对 取模即可。

输入输出格式

输入格式

输入一行两个整数 ,表示有 项任务,在 种情况中下小 F 会产生歉意值。

输入接下来 行,每行有一个长度为 和一个歉意值 表示第 项任务此时没做 / 已经做了。

详情请参考样例和样例解释。

输出格式

输出一行一个整数,表示小 F 在那一天所有可能的完成任务方式的歉意值之和对 取模的结果。

输入输出样例

输入样例#1

2 2
00 1
10 1

输出样例#1

4

输入样例#2

3 4
000 16
001 9
110 4
111 1

输出样例#2

260

说明

样例 1 解释:

串中第一个数字表示小 F 看没看比赛,第二个数字表示小 F 补没补锅。

我们用 表示小 F 什么都没干, 表示小 F 看了比赛, 表示小 F 补了锅,那么所有会产生愧疚的方式如下:


那么所有可能的选择如下:



所以答案是

数据范围

保证出现的 互不相同。

对于所有数据,有 ,

Case
1
2
3
4
5
6
7
8
9
10

分析

n=20大概会误导人去写状压DP吧,然而我太弱了并不会去写状压

题意:给出m个二进制数,每个数对应一个权值,求从一个二进制数a转换到b的方案的代价(转换中每个数出现的次数乘上各自权值)

考虑方案计数可以累乘,所以可以分别考虑这m个数产生的代价

opt[i]为填入i个1的方案数

先预处理递推求出组合数,和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 998244353
ll 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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr