咕咕机app官网_咕咕小哨

咕咕机app官网_咕咕小哨P4996 咕咕咕

大家好,又见面了,我是你们的朋友全栈君。

贡献法+组合数学

讲道理一看到辣么小的\(n\),我就想到了状压dp。

枚举子集?哦,\(O(3^n)\)的复杂度。但是我没有注意到\(n=20\)的时候是过不了的。

接下来我就在想70pts的状压dp要怎么写?

没有清楚定义状态的我连样例2都过不了,只能够手动枚举拿30pts。

所以最简单的月赛也爆炸了


70pts的状压

下面的做法是借鉴luogu题解的,不是抄袭。(你信吗?)

dp[i]表示从全0转移到i状态的所有歉意值之和。

那么会有

\[dp[i]=\sum{dp[j] + qy[j] \times num[j]}, j \in i and j \neq \emptyset\]

其中num[j]表示从全0转移到j的方案数,qy[j]表示当前这个状态的歉意值。

num[j]自然也是可以递推的,可以这么递推:

\[num[j] = \sum{num[k]}, k \in j and k \neq \emptyset\]

用枚举子集的优化技巧就可以做到\(O(3^n)\)的搞出来了。

不给代码,题解里面是有的。

我的错误之处:没有意识到方案数是对答案有影响的。

满分做法

使用贡献法,那么每一个歉意值就会对答案产生贡献了。

产生的贡献是多少?是这个状态在所有方案中出现的次数 乘以 这个方案的歉意值。

还能够发现:其实一个状态只跟它的01个数有关,跟她们的顺序是无关的。

所以设一个\(num[i]\)表示填\(i\)个1的方案数,那么就可以递推出来了。

递推式是这样子的:

\[num[i] = \sum_{j=1}^n{num[i-j] \times C_i^j}\]

那么最后的答案就是该方案0的个数 乘以 该方案1的个数 乘以 这个方案的歉意值。

对了:注意取膜!否则你就只有80pts啦。

代码:

#include<cstdio> #include<cstring> #define ll long long const int maxn = 21, maxN = 1048580; const int MOD = 998244353; ll dp[maxN]; ll qy[maxN]; ll num[maxn]; ll C[maxn][maxn]; int n, m; void init() { for(int i = 0; i <= 20; i++) { C[i][0] = C[i][i] = 1; } for(int i = 1; i <= 20; i++) { for(int j = 1; j < i; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } } int popcount(char *ch) { int len = strlen(ch); int res = 0; for(int i = len - 1; i >= 0; i--) { if(ch[i] == '1') res++; } return res; } int main() { init(); scanf("%d%d", &n, &m); num[0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { num[i] = (num[i] + C[i][i - j] * num[i - j] % MOD) % MOD; } } ll ans = 0; for(int i = 1; i <= m; i++) { char ch[25]; int x; scanf("%s%d", ch, &x); int temp = popcount(ch), len = strlen(ch); ans = (ans + x * num[temp] % MOD * num[len - temp] % MOD) % MOD; } printf("%lld\n", ans); return 0; }

转载于:https://www.cnblogs.com/Garen-Wang/p/9913101.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107210.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux中vi编辑器保存文件命令_linux用vi编辑文件

    linux中vi编辑器保存文件命令_linux用vi编辑文件工具:Linux方法:1、首先进入Linux的命令行界面.在目录下创建一个用于测试的文本文件(touchfilename).这里就新建了一个test12文本文件.当然这个名字是可以随便取得.2、用”vitest12″命令进入vi命令行模式(vifilename).如果要想编辑文本文件.必须要转换到插入模式下,也就是按一下键盘上的”i”就可以了.这样就可以编辑文本,删除文本中的内容.按键盘上…

  • Django用户登录与注册系统[通俗易懂]

    1.1.创建项目和appdjango-adminstartprojectmysite_loginpythonmanage.pystartapplogin1.2.设置时区和语言Django默认使用美国时间和英语,在项目的settings文件中,如下所示:LANGUAGE_CODE=’en-us’TIME_ZONE=’UTC’USE_I18N=TrueUSE_L1…

  • pip换源 -pip更换国内镜像源「建议收藏」

    pip换源 -pip更换国内镜像源「建议收藏」更换pip源到国内镜像2017年02月16日15:06:53阅读数:70784pip国内的一些镜像  阿里云http://mirrors.aliyun.com/pypi/simple/  中国科技大学https://pypi.mirrors.ustc.edu.cn/simple/  豆瓣(douban)http://pypi.douban.com/simple/…

  • 怎么删除服务项

    怎么删除服务项

  • DirectX修复工具使用技巧之二——手动修复C++创建失败的文件

    DirectX修复工具使用技巧之二——手动修复C++创建失败的文件最后更新:2021-2-25随着V4.0正式版的发布,近来有部分用户来咨询如何解决C++文件创建失败的问题。在此我将以解决最常见的C++2015-2019文件创建失败为例,向大家演示一下在线修复的方法,其他C++或文件的方法大同小异。此次操作以Windows7为例,其他系统相应参考即可。首先,如果希望程序能手动在线修复创建失败的失败,请首先确定您使用的V4.0.2版或更高版本,老版本不支持此功能。查看程序版本的方式可以把鼠标放在DirectXRepair.e…

  • python里面requests库(python如何爬取网页数据)

    一、什么是RequestsRequests是⽤Python语⾔编写,基于urllib,采⽤Apache2Licensed开源协议的HTTP库。它⽐urllib更加⽅便,可以节约我们⼤量的⼯作,完全满⾜HTTP测试需求。⼀句话——Python实现的简单易⽤的HTTP库二、安装Requests库进入命令行win+R执行命令:pipinstallrequests…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号