【CF908E】New Year and Entity Enumeration

2024-06-11 05:08

本文主要是介绍【CF908E】New Year and Entity Enumeration,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

https://www.cnblogs.com/CQzhangyu/p/8227408.html

http://www.mamicode.com/info-detail-2146477.html

题意:给定M=2m−1M=2m−1,我们称一个集合S是好的,当且仅当它满足:1.∀a∈S,a xor M∈S∀a∈S,a xor M∈S,2.∀a,b∈S,a and b∈S∀a,b∈S,a and b∈S,3.∀a∈S,a≤M∀a∈S,a≤M。

现在给定集合T,求有多少个好的集合S,满足T是S的子集。

m<=1000,|T|<=50。

题解:显然有了与和取反以后,我们还可以实现或和异或。如果给定T以后,我们对T中的数进行运算能得到什么数呢?容易发现如果二进制位a和位b如果在所有数中都是相同的,那么造出来的数也一定满足位a和位b是相同的。所有满足这个条件的数我们都能造出来。

也就是说,我们只需要确定S中哪些位是始终相同的,即把m个物品分到若干个集合的方案数(Bell数),用m2m2的DP很容易求出。

但是由于要求T是S的子集,相当于认为的将某些物品分到了一起,我们可以对每个位置维护一个|T|位二进制状态,如果两个位置的状态是不同的,则这两个位置不是始终相同的,则S中对应位置也不能始终相同。所以我们可以对所有相同的状态,代入Bell数求出方案,再将不同状态的方案数乘到一起即可。

 挖坑 过会来看

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1000000007;
bool ban[1010][1010];
int bel[1010];
int n,m;
ll ans;
ll tag[1010],f[1010][1010],s[1010];
char str[1010];
int main()
{scanf("%d%d",&m,&n);int i,j,siz;for(i=1;i<=n;i++){scanf("%s",str+1);for(j=1;j<=m;j++)    if(str[j]=='1') tag[j]|=1ll<<(i-1);}ans=f[0][0]=1;for(i=1;i<=m;i++)    for(j=1;j<=i;j++)    f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%P,s[i]=(s[i]+f[i][j])%P;for(i=1;i<=m;i++)    if(!bel[i]){siz=0;for(j=i;j<=m;j++)    if(tag[j]==tag[i])  bel[j]=i,siz++;ans=ans*s[siz]%P;}printf("%lld",ans);return 0;
}

 

这篇关于【CF908E】New Year and Entity Enumeration的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1050267

相关文章

java线程深度解析(一)——java new 接口?匿名内部类给你答案

http://blog.csdn.net/daybreak1209/article/details/51305477 一、内部类 1、内部类初识 一般,一个类里主要包含类的方法和属性,但在Java中还提出在类中继续定义类(内部类)的概念。 内部类的定义:类的内部定义类 先来看一个实例 [html]  view plain copy pu

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

List list = new ArrayList();和ArrayList list=new ArrayList();的区别?

List是一个接口,而ArrayList 是一个类。 ArrayList 继承并实现了List。 List list = new ArrayList();这句创建了一个ArrayList的对象后把上溯到了List。此时它是一个List对象了,有些ArrayList有但是List没有的属性和方法,它就不能再用了。而ArrayList list=new ArrayList();创建一对象则保留了A

vue原理分析(六)--研究new Vue()

今天我们来分析使用new Vue() 之前研究时,只是说是在创建一个实例。并没有深入进行研究 在vue的源码中找下Vue的构造函数 function Vue(options) {if (!(this instanceof Vue)) {warn$2('Vue is a constructor and should be called with the `new` keyword');}thi

GTK中创建线程函数g_thread_new和g_thread_create的区别

使用GThread函数,需要引用glib.h头文件。 这两个接口的核心区别就是  g_thread_create 是旧的接口,现在已经不使用了,而g_thread_new是新的接口,建议使用。 g_thread_create: g_thread_create has been deprecated since version 2.32 and should not be used in n

New的VC编译器实现

当我们调用 new 的时候,例如 int *p = new int; 时,编译器到底作了什么工作呢?跟进断点看一看。   (在 vc debug模式下 ) double *p1 = new double ; 00411A6E  push        8    00411A70  call        operator new (4111B8h) 00411A75  add

Python方法:__init__,__new__,__class__的使用详解

转自:https://blog.csdn.net/qq_26442553/article/details/82464682 因为python中所有类默认继承object类。而object类提供了了很多原始的内建属性和方法,所以用户自定义的类在Python中也会继承这些内建属性。可以使用dir()函数可以查看,虽然python提供了很多内建属性但实际开发中常用的不多。而很多系统提供的内建属性实际

linux 环境下使用PHP OpenSSL扩展函数openssl_pkey_new(),返回false的原因

<?php$config = array('private_key_bits' => 2048,);$res = openssl_pkey_new($config); $res返回false的时候,检查发现,是linux系统缺少了openssl的配置,解决方法如下: 直接将php -m 中 Openssl 中的xx.conf 配置移动到对应的目录,然后重启php-fpm 完美解决

【js面试题】说说new操作符具体干了什么?

JavaScript中的new操作符:深入解析与自定义实现 在JavaScript中,new操作符是一个核心概念,用于创建一个实例对象。理解new的工作原理不仅有助于我们更好地掌握JavaScript的面向对象编程,还能让我们在需要时自定义构造函数的行为。本文将从new是什么、其工作流程、存在的必要性、解决的问题以及如何手动实现一个new操作符来深入探讨这一主题。 什么是new操作符? ne