小衣同学的博客

分母需要计算取k次总的方案数，为sum*(sum-1)*...*(sum-k+1)记p(i) i >= 0为取i次后能够取出一对袜子的概率，则最终期望是。总步数的期望可以拆成第1 2 3...n步的贡献，分子需要支持取k次计算每种袜子只取出来1次的方案数。完成目标的期望数=每种未完成的状态的到达概率之和。元老群全月&starsilk&propane。对于第k次抽取袜子后游戏还没结束的概率。可以把每一步拆开来算然后加起来，每个式子都是第i步还没结束的概率。相当于有这个概率会有第i步。

可以用0*1+1*0求得奇数次的方案，用(0+1)*(0+1)求得总的方案，求从n个数中选出奇数个数，使得选出的这些数的和为m(m<=1e6)的方案数。给定长为n(n<=1e5)的序列a，第i个数ai(1<=ai<=10)其实感觉有点子集反演，钦定popcount的位数的意思。这样每合并两个数需要卷积四次，合并10个数需要36次，每种数拆成两个多项式，分别对应奇/偶的情况，注意到ai很小，只有不超过10，答案对998244353取模。计0为偶数个，1为奇数个，a和b两种数合并的时候，少跑了100ms左右。

一个长为m(m<=min(n,40000))的序列b，第j个数bj(1<=bj<=1e9)遇到b的值就给bitset上赋上一位，遇到a中的值就令a的答案等于当前的bitset的值。由于bitset与/或时，两个bitset需要等长，无法控制一个长为n，另一个长为m。如果a的[i,i+m-1]需要和b的[0,m-1]比，就需要满足二者下标差为i。a中[i,i+m-1]和b中[0,m-1]做比较时，就需要到下标i+m-1上找。独立考虑a中的每个值，能大于哪些b中的值，也就是将a和b中的值放到一起排序。

1. [l,mid]=[0,1]，[mid+1,r]=[2,3]，那么右半边f2会加上。2. [l,mid]=[5,6]，[mid+1,r]=[7,8]，那么右半边f7会加上。左边两个下标最小，右边下标最大，也就是l+l=r-1，满足2*l

题目n(n<=250000)个点的树，你需要把1-n这n个数，每个数只能用一次，染色到n个点上，每个点一个颜色，且整棵树不存在u的父亲的颜色是u的颜色的值+1的情况求最后的方案数，答案对998244353取模思路来源xls心得槽，cf的越界检查机制，让我发现之前的分治NTT板子有错题解看见250000和998244353，就大概率是NTT了如果dp[i]表示全图恰好有i个父子对冲突的方案数，求出dp[i]后，容斥一下即为答案如果冲突，我们不妨认为这两

题目给定序列，求序列。其中，边界为。答案对取模。数据范围思路来源https://www.luogu.com.cn/blog/ljc1301/solution-p4721题解思路来源讲的很详细了，自己大概就口嗨一下，做本题大致就是试试板子兼不兼容，memset和memcpy在对vector使用的时候本来以为会很慢，但是还是跑的很优秀先solve(l,mid)，然后考虑本次[l,mid)对[mid,r)的贡献，加到[mid,r)的答案里，然后solve(m...

题目思路来源jyt、tzy题解一道看似多项式求导，实则分治NTT/启发式NTT的题目心得orz我好菜啊惨遭学弟学妹吊打push自己换了个板子，3s的题自己的板子跑了2800ms，学弟的板子900ms代码#include<bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned llconst int N = 1<<18, P = 998244.

题目n(n<=1e5)个点，m(m<=n+41)条边的仙人掌，保证最多42个环，每条边有一个边权w(w<=1e5)，求异或权值最小的生成树，即最终的答案=选中的边权的异或和，令该答案最小，输出答案，及得到该答案的方案数，答案模1e9+7思路来源https://blog.csdn.net/u013534123/article/details/103307091题解仙人掌找环，42个环，把不在环上的边异或起来得到一个值，上述43个数组做一个FWT_xor，最

题目假设有两个等长的串x和y，保证字符只包含‘a’-'f'的小写字母你可以每次选择两个字符，不妨设为'a'和'b'，把两个串中当前所有'a'都改成'b'计编辑距离为二者改成相同的串的最小修改次数，比如x串为abcd，而y串为ddcb，则编辑距离为2第一次可以把a改成b，有x串为bbcd，y串为ddcb第二次可以把b改成d，有x串为ddcd，y串也为ddcd现给出两个串S和T(|T|<=|S|<=125000)，对于S中每个长度为|T|的子串，输出其与T的编辑.

题目在n场1v1中，假设第i场，有ai个星灵单位，和bi个虫族单位。tokitsukaze可以在一场1v1中，任选一种种族进行游戏。如果选择了星灵，那么在这场游戏中，可以选择出兵1到ai个单位。那么同理，如果选择了虫族，那么在这场游戏中，可以选择出兵1到bi个单位。tokitsukaze想知道，恰好选择了0,1,2,3,...,个星灵单位的方案数分别是多少。由于答案很大，所以...

赛中通过B. Fire-Fighting Hero(最短路/多源bfs 签到)题意比较多源bfs的最短路和单源最短路哪个大题解可以对多源建个虚点，跑两次单源最短路#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include...

题目n(n<=5e5)堆石子，第i堆有ai个石子，UinUin和NiuNiu玩Nim游戏，NiuNiu后手，但他可以取出其中的一些堆石子，用这些堆来玩Nim游戏，在NiuNiu必胜的情况下，最大化石子堆数，输出堆数如果NiuNiu必胜不了，输出0思路来源https://blog.csdn.net/m0_37953323/article/details/81780425...

题目题目链接：https://ac.nowcoder.com/acm/contest/373/D定义两个位数相等的二进制串A,B 的相似度SIM(A,B)= 二进制串A⊕B中0的个数如A=00010,B=01000,A⊕B=01010,所以SIM(A,B)=3。给定N 个长度为M的二进制串S1,S2...SN。现在的问题是找出一个额外的长度为M的二进制字符串...

题目链接：https://ac.nowcoder.com/acm/contest/373/F来源：牛客网这冗长的题目我已经叙述不了了思路来源https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40376257题解首先，考虑f(x)，由于一个素因子出现两次及以上莫比乌斯函数值就会为0所以f(...

题目思路来源dls题解先离散化，把a和b搞进一个序列，然后排序去重，把a和b赋为rank值然后遍历这个不重复的序列，两个大于1W就建2e5数列用NTT搞，否则直接暴力既然要在ai和bj值相同，下标i+j==k时求i*j的值，那么就把位置i和j分别放入值的vector里，对相同值的vector进行NTT注意多项式乘法一定会遍历所有的情形，所以就令f(x)的第i位...

板子来源https://www.cnblogs.com/kuangbin/archive/2013/07/24/3210389.html//kuangbin巨神的板子心得写了一个从高位输出大数的方法，WA到不能自已，后来发现是没判ans=0这种情况，才学会了kuangbin巨神的写法。以后大数输出固定一下格式吧，感觉自己太菜了。FFT模板get√ 生成函数什么的以后再刷...