zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

其实下面给出的a数组没什么鸟用

列出方程:

E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E)

解方程: E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E) \\\\ E = \sum_{i=0}^{n-1} \frac in + (1 - \frac mn)E \\\\ \frac mnE = \frac {\frac 12n(n-1)}n \\\\ E = \frac {n(n-1)}{2m}

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一段区间检查后能不被吃掉的汉堡满足其他汉堡的能量值都是它的倍数

那我们就求出区间\gcd. 而这个汉堡的能量值必须等于区间gcd,所以它的能量值也是区间最小值。

那我们就再记录区间最小值并且记录数量

那么满足这个复杂度而且最方便的当然是线段树了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

维护两个单调递减栈,当i加进栈,位置x的数弹出的时候,在另一个栈中找到和这个数一样大的数,计算贡献(x-靠右左端点)\times (i-x)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

i对答案会统计\left \lfloor \frac ni \right \rfloor次,但只有出现奇数次才会产生贡献

每次的贡献是i \bigoplus i+1 \bigoplus ... \bigoplus j,那么可以用数列之异或这道题的思路做

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑如何快速找出拥有(与它的前缀相同的)后缀的串。这个东西可以通过把字符串放到Trie里面。 分类两种情况,短串+长串长串+短串。对于短串+长串的情况,先将字符串按len排序,然后顺序将字符串倒着插入trie里面,并在trie中的尾节点记录hash。利用当前串作为查询串来找答案,这样能保证当前串一定是长串,并且找到的所有短串都有和它的前缀相同的后缀,所以再利用hash判断一下就可以确定拼出来的是不是回文串了。另外一个情况同理。 复杂度是O(26\sum len)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

开一个桶f记录每个数出现次数,然后f[i]=\sum_{i|d}f[d]

求出所有i的倍数可能组成的四元组,这时\gcd一定是i,2i,3i,\cdots,然后减去\gcd2i,3i,\cdots的四元组个数。即f[i]={cnt\choose 4}-\sum_{i|d,i\neq d}f[d]

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

枚举当前合法序列放了多少个i(2i>n)的,记数量为x,那么对于i(2i\le n)的数量为m-x

对于答案的贡献为x!\times (m-x)!\times {x \times C(m-x)} \times {C(x,\frac{n}{2}})\times {C({m-x},\frac{n+1}{2}})

(因为第二类数只能放在第一类数前面,所以一共x个空放m-x个数,方案为C({m-x},x)

选出x个第一类数和vm-x个第二类数的方案分别为C(x,\frac{n}{2})C({m-x},\frac{n+1}{2})

然后x个数和m-x个数的排列为x!(m-x)!

所以就得到了这个贡献式子

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

g_i表示交集个数至少为i的方案数

那么g_i = {n\choose i}(2^{2^{n-i}}-1)

先从n中选i个,然后其他可以随便取

那就是有2^{n-i}个集合可以取

然后又可以取至少1个集合

那么答案就是{n\choose i}(2^{2^{n-i}}-1)

f_i表示恰好为i

那么g_k=\sum_{i=k}^n f_i\cdot {i\choose k}

反演f_k=\sum_{i=k}^n g_i\cdot{i\choose k} (-1)^{i-k}

不能直接快速幂,因为指数不能\mod p,要用2^{2^i}=(2^{2^{i-1}})^2倒着枚举算

43/74
Search
search