标签 - FFT|NTT

? 解题记录 ? ? FFT|NTT ? ? 树链剖分 ? ? 虚树 ? ? 组合数 ?    2019-03-18 12:09:49    1156    0    3
题目描述 给你一棵n个点的树,每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是:把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来,求:有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
? 解题记录 ? ? LOJ ? ? FFT|NTT ? ? 动态规划 ?    2019-03-16 07:59:01    632    0    0
传送门 题解: 考虑怎么做这道题。 首先发现性质: 改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
? 解题记录 ? ? LOJ ? ? 树链剖分 ? ? FFT|NTT ? ? 动态规划 ?    2019-03-14 11:31:06    738    0    0
题目链接:传送门 题解:不难发现,我们有一个优秀的N2N^2的dpdp做法,记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个,当前根选没选。 我们要知道分治NTTNTT的复杂度:对于kk个总度数∑deg=k\sum deg=k的多项式来说,计算它们乘积的复杂度可以做到:O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此,我们采用重链剖分,先转移所有轻链。 不难发现, g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
? 解题记录 ? ? LOJ ? ? 生成函数 ? ? 期望概率 ? ? FFT|NTT ?    2018-12-09 16:21:41    436    0    0
题目地址:"噔" 题目给定的条件不太好求。 发现原题死了人之后概率的分母会变,十分不可做。 然后就有一步神转化了,我们将原题改为打死人之后这个人并不出局,而是被打上标记。如果开枪射中打标记的人,那么这一枪无效,重新射击。 这样我们发现,分母一定了,容易了许多。 整理一下,发现我们没有办法确切算出1" role="presentation" style="position: relative;">111在最后一个死的概率,但是我们可以确切算出至少有k" role="presentation" style="position: relative;">kkk个人死在1"
? 解题记录 ? ? UOJ ? ? 生成函数 ? ? FFT|NTT ? ? 牛顿迭代 ?    2018-11-25 15:19:16    618    0    0
(题目背景)是没有的。 你有一个01" role="presentation" style="position: relative;">010101序列,初始时序列为空。你可以对序列进行两种操作: 在序列末端插入一个0" role="presentation" style="position: relative;">000。 在序列中删去一个子序列,并在序列末端插入一个1" role="presentation" style="position: relative;">111。这里对子序列的选取有一定限制,设子序列中包含x" role="presentation"
? 解题记录 ? ? BZOJ ? ? FFT|NTT ?    2018-09-20 14:56:12    909    0    0
DescriptionByteasar 组建了一支舰队!他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图,其中有些位置是“ .”,表示这一格是海水,可以通过;有些位置是“#”,表示这一格是礁石,不可以通过;有些位置是“o”,表 示这一格目前有一艘舰,且舰离开这一格之后,这一格将变为“.”。这些“o” 表示Byteasar 的舰队,他们每天 可以往上下左右中的一个方向移动一格,但不能有任何一艘舰驶出地图。特别地,Byteasar 对阵形有所研究,所 以他不希望在航行的过程中改变阵形,即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以 航行无限长的时间,每当一艘
? 解题记录 ? ? BZOJ ? ? FFT|NTT ? ? 构造 ?    2018-09-19 08:03:56    651    0    0
【题目描述】兔子们在玩两个串的游戏。给定两个字符串S和T,兔子们想知道T在S中出现了几次,分别在哪些位置出现。注意T中可能有“?”字符,这个字符可以匹配任何字符。 【输入】两行两个字符串,分别代表S和T 【输出】第一行一个正整数k,表示T在S中出现了几次 接下来k行正整数,分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出,S下标从0开始。 【输入样例】bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab a?aba?abba 【输出样例】
? 解题记录 ? ? 杂OJ ? ? 容斥 ? ? 组合数 ? ? 生成函数 ? ? FFT|NTT ?    2018-08-15 09:58:01    937    0    0
【题目描述】 求n个点的有向图的强连通图的个数对998244353取模后得结果(无重边,无自环) 定义强连通图为本身为强连通分量的图 【输入格式】 输入一个n表示点数 【输出格式】 输出题目要求的答案 【样例输入】 2 【样例输出】 1 【提示】 对于30%的数据,n<=1000 对于100%的数据,n<=100000 30分的做法详见:网上一篇很好的博客 这个东西是个卷积形式,很容易想到生成函数。 我们来回顾一下两个式子: f(n)=g(n)+∑k=0n(n−1k−1)f(k)g(n−k) f(n)=g(n)+\sum^{n}_
? 解题记录 ? ? HDU ? ? cdq分治 ? ? FFT|NTT ?    2018-07-27 10:33:39    675    0    0
Problem Description Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.Suppose the shell necklace is a sequence of shells (not a chain end to end
? 解题记录 ? ? 洛谷 ? ? 点分治 ? ? FFT|NTT ?    2018-07-24 18:45:25    519    0    0
Problem description.You are given a tree. If we select 2 distinct nodes uniformly at random, what's the probability that the distance between these 2 nodes is a prime number? InputThe first line contains a number N: the number of nodes in this tree. The following N-1 lines contain pairs a[i] and b[i