ZR#999 清疚 2024-04-20 10:34 85阅读 0赞 ## ## ZR\#999 ### 解法: ### > 一道计数题,看到要求必须 $ m $ 个标号,所有标号至少出现一次的方案。 > 很容易想到可以容斥,但容斥这个东西是一种很神奇的东西,你可以看出来一道题需要容斥,但你就是不知道怎么容斥。 > > > 原题的等价形式为:总方案减去至少不出现一种玩具的方案数。 > > 考虑容斥 , 那么就有 > > > $ \\bigcup ^ \{n\} \_ \{i = 1\} A\_i = \\sum ^ \{n\} \_ \{k = 1\} (-1) ^ \{k-1\} \\sum \_ \{1 \\leq i\_1 < i\_2 \\cdots i\_k \\leq n\} \\mid A\_\{i\_1\} \\cap A\_\{i\_2\} \\cap \\cdots \\cap A \_ \{i\_k\} \\mid $ > > 设 $ f\_i $ 表示状态为 $ i $ 时所有元素都在集合 $ i $ 中的方案数。(不要求包含 $ i $ 中的所有元素)然后用容斥原理算一下即可。 > 但是这个题数据范围比较大,需要用 $ FWT $ (高维前缀和)来维护 。 ### CODE: ### #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1 << 20 const int p = 1e9 + 7; int n,m,k,x,res,ans; int f[N],t[N],cnt[N],flag; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f; } int main() { n = read(),m = read(); flag = (1 << m) - 1; cnt[0] = 1; for(int i = 1 ; i <= n ; i++) { k = read(); res = 0; for(int j = 1 ; j <= k ; j++) { x = read(); res |= 1 << (x - 1); } ++f[res]; } for(int i = 1 ; i <= m ; i++) { for(int j = 1 ; j <= flag ; j++) { if(j & (1 << (i - 1))) f[j] += f[j ^ (1 << (i - 1))]; } } for(int i = 1 ; i <= n ; i++) { cnt[i] = cnt[i - 1] << 1; if(cnt[i] >= p) cnt[i] -= p; } for(int i = 0 ; i <= flag ; i++) { t[i] = t[i >> 1] + i & 1; if(!((m - t[i]) & 1)) ans += cnt[f[i]] - 1; else ans -= cnt[f[i]] - 1; if(ans >= p) ans %= p; else if(ans < 0) ans += p; } printf("%d \n",ans); //system("pause"); return 0; } 转载于:https://www.cnblogs.com/Repulser/p/11488331.html
相关 ZR#997 ZR\997 解法: > 找找规律就出来了,全场最简单的一道题。 CODE: include<iostream> include<cstdi... 怼烎@/ 2024年04月20日 10:34/ 0 赞/ 90 阅读
相关 ZR#999 ZR\999 解法: > 一道计数题,看到要求必须 $ m $ 个标号,所有标号至少出现一次的方案。 > 很容易想到可以容斥,但容斥这个东西是一种很神奇... 清疚/ 2024年04月20日 10:34/ 0 赞/ 86 阅读
相关 ZR#957 ZR\957 解法: > 首先 $ T $ 必须得要是 $ S $ 的子序列,不然不存在好的下标序列,因此一定无解。 > 考虑判断一个串 $ T $ 是... 痛定思痛。/ 2024年04月20日 10:34/ 0 赞/ 88 阅读
相关 ZR#959 ZR\959 解法: > 对于一个询问,设路径 $ (u, v) $ 经过的所有边的 $ gcd $ 为 $ g $,这可以倍增求出。 > 考虑 $ g... Bertha 。/ 2024年04月20日 10:34/ 0 赞/ 91 阅读
相关 ZR#998 ZR\998 解法: > 先把所有物品按照拿走的时间从小到大排序,拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。 ... 柔光的暖阳◎/ 2024年04月20日 10:33/ 0 赞/ 101 阅读
相关 ZR#954 分组 ZR\954 分组 解法: > 设 $ f\[i\]\[a\]\[b\] $ 表示考虑了排序后的前 $ i $ 个人,目前已经有 $ a $ 个组配好了,还... 分手后的思念是犯贱/ 2024年04月20日 10:32/ 0 赞/ 88 阅读
相关 ZR#956 集合 ZR\956 集合 解法: > 维护一个异或操作的懒标记,并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。 > 考虑一个数字 $ x $ 变为... 待我称王封你为后i/ 2024年04月20日 10:31/ 0 赞/ 80 阅读
相关 ZR#712 消灭砖块 题意: > 很多块砖分布在一个 $ m \\times m $ 的矩阵中,他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵... 朱雀/ 2024年04月20日 10:24/ 0 赞/ 76 阅读
相关 ZR#710 雷劈数 题意: > 现在给出两个整数,求出位于两个整数之间的所有的“雷劈数。 解法: > 因为雷劈数特殊的性质,所以在数据范围中的雷劈数实际很少,直... ゝ一纸荒年。/ 2024年04月20日 10:24/ 0 赞/ 96 阅读
相关 ZR#996 ZR\996 解法: > 若删除长度为 $ x $ 的子串后序列中没有相同元素,那么一定有至少一个长度为 $ x+1 $ 的子串,删除它后序列中也没有相同元... 怼烎@/ 2024年04月20日 10:23/ 0 赞/ 84 阅读
还没有评论,来说两句吧...