题目描述
小 F 是一个能鸽善鹉的同学,他经常把事情拖到最后一天才去做,导致他的某些日子总是非常匆忙。
比如,时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单:
- 看 iG 夺冠;
- 补月赛题的锅。
小 F 虽然经常咕咕咕,但他完成任务也是很厉害的,他一次性可以完成剩余任务的任一非空子集。比如,他现在可以选择以下几种中的一种:
- 看 iG 夺冠;
- 补月赛题的锅;
- 一边看 iG 夺冠的直播,一边补锅。
当然,比赛实在是太精彩了,所以小 F 就去看比赛了。
不过,当金雨从天而降、IG 举起奖杯之时,小 F 突然心生愧疚——锅还没补呢!于是,小 F 的内心产生了一点歉意。
这时小 F 注意到,自己总是在某些情况下会产生歉意。每当他要检查自己的任务表来决定下一项任务的时候,如果当前他干了某些事情,但是没干另一些事情,那么他就会产生一定量的歉意——比如,无论他今天看没看比赛,只要没有补完月赛的锅,他都会在选择任务的时候产生 11 点歉意。小 F 完成所有任务后,他这一天的歉意值等于他每次选择任务时的歉意之和。
过高的歉意值让小 F 感到不安。现在,小 F 告诉你他还有 n 项任务,并告诉你在 m 种情况中的一种的情况下,小 F 会产生 ai 点歉意。请你帮忙计算一下,小 F 在那一天所有可能的完成所有任务方式的歉意值之和是多少。
由于答案可能很大,你只需要输出答案对 998244353 取模即可。
输入输出格式
输入格式:
输入一行两个整数 n, m,表示有 n 项任务,在 m 种情况中下小 F 会产生歉意值。
输入接下来 m 行,每行有一个长度为 n 的 0-1 串 和一个歉意值 ai,ai 为 0/1 表示第 j 项任务此时没做 / 已经做了。
详情请参考样例和样例解释。
输出格式:
输出一行一个整数,表示小 F 在那一天所有可能的完成任务方式的歉意值之和对 998244353 取模的结果。
思路:
一开始写的时候,把时间复杂度的(2^20*2^20)算成了(2^21)成功T飞
没T的那几个点也忘了取模……
其实这道题只用组合数就好
一个状态的贡献在于经过他有几种方案到达最终态
所以我们可以发现,这是一个组合数问题
比如说我们一共有5个任务,当前完成了3个任务
那么转移到完成3个任务的情况有
从00000转移到任选3个完成
从有1个转移到有3个
从有2个转移到有3个
我们发现,由于我并不用确定到底选的是哪个
只用考虑选了几个
所以选i个的情况总数就是
(原谅我直接搬了luogu的图)
然后对于每种有贡献的情况分别考虑即可
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define p 998244353
#define rii register int i
#define rij register int j
#define int long long
using namespace std;
int zhs[][],n,m,opt[],ans,c[][];
void ycl()
{
c[][]=;
for(rii=;i<=;i++)
{
c[i][]=;
for(rij=;j<=;j++)
{
c[i][j]=c[i-][j-]+c[i-][j];
c[i][j]%=p;
}
}
opt[]=;
for(rii=;i<=;i++)
{
for(rij=;j<=i;j++)
{
opt[i]+=c[i][j]*opt[i-j];
opt[i]%=p;
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
ycl();
for(rii=;i<=m;i++)
{
char ch=getchar();
int zt=,val;
while(!isdigit(ch))
{
ch=getchar();
}
while(isdigit(ch))
{
zt+=ch-'';
ch=getchar();
}
scanf("%lld",&val);
ans+=(((val*opt[zt])%p)*opt[n-zt])%p;
ans%=p;
}
cout<<ans;
}