Deep_Dark_FAntasy♂

题解

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 未归档(176) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15)

/ 注册

全部文章 / 题解（共12篇）

brz的函数

推公式题。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e4+7; ll ans[maxn], mu_fac_sum[maxn]; bool vis[maxn]...

数论莫比乌斯函数贡献

2020-11-08

2 560

brz的序列

#include<bits/stdc++.h> using namespace std; const int N = 1e6+7; int a[N]; struct node{ double x, y; }p[N],s[N]; int n; bool cmp(node a, no...

2020-11-07

4 629

牛牛的方程式

ax+by=c有解结论的推广gcd(a,b)|c别忘了特判a=b=0的时候，c=0，c/=0情况代码： #include<bits/stdc++.h> using namespace std; #define int long long signed main() { int t...

裴蜀定理

2020-10-20

6 609

神奇的迷宫

思路：这道题首先是求关于路径的情况，我们需要直到用题目中已知所有的WL，为了求出最终的期望，我们应该求出每一个L的概率Pl,这是对某个路径长度的全部情况在树上求解，显然是用点分治处理。用母函数的角度来考虑f(x)=a0x^0+a1x^1+a2x^2+...+an-1x^n-1，a是概率以u为当前根结...

概率点分治

2020-10-13

8 621

烙印

思路：先复习一下三角形全等条件，SSS,SAS,AAS,ASA分析题目，可以分为一下几个情况1.3条边2.3个角3.1个边2个角4.一个角2个边1只有1种，2有无穷种，3有AAS和ASA都只有一种，4有SAS和SSA两种，特判一下SSA的情况就行。然后再考虑一下构不成三角形的情况。 #include...

水题

2020-10-10

5 515

集合操作

思路：很容易知道所有的情况共有2^n个，然后我们思考不可能存在的情况有多少种。我们知道每次都可以从前m+1个种取一个。当我们左边减少0个，那么右边m+1到n中任意数字减少都不行，因此答案有2^(n-m-1)-1种(真子集都是不存在的情况，-1是因为自己一个不去)当我们左边m+1个中减少1个，那么答案...

组合数学

2020-09-26

2 543

Mu函数

思路：看到K这么大，我们知道这种题一般要先从找规律的角度尝试一下。f(x)=x+Mu(x)，那么跟据Mu(x)，我们知道如果x的Mu(x)为0，不管经过多少次迭代，其结果都是0如果Mu(x)不为0呢，通过对Mu(x)打表我们可以大胆猜测，在k很大的时候，要么x通过迭代到了Mu(x)=0的点，会产生-...

找规律

2020-09-26

3 736

数树

思路：可以从度的角度来考虑来考虑相连如果是两个D>1的结点相连，我们知道这一定是两颗树合并了，那么树++，如果其中一个D=1，那就是一个点和并到了一颗树上，树的个数不变，如果两个D=0的点相连，树的个数++接下来考虑断开如果是两个D>1的结点断开，我们知道肯定是1棵树变成了2颗树。如果其...

2020-09-26

5 456

【高斯消元】To xor or not to xor(最长异或子序列)

题目描述：就是给你n个数然后从中选择一些出来异或，求异或可得到的最大值解题思路：跟据题目可以假设答案ans=d1d2d3d4...(di代表ans的二进制位0/1)(这里不是乘法哦)，从高位一直枚举到低位，检验是否可行。但如果直接检验的话，复杂度是O(2^n)，显然超时。所以可以从高位枚举到低位，同...

贪心高斯消元最大异或子序列

2020-06-25

0 821

Subsequence(尺取法枚举区间)

尺取法裸题,给一串数列和一个S，求数列中的某个大于S的子数列长度最小。介绍一下尺取法：尺取法也叫 two pointer ，顾名思义，像尺子一样，一块一块的截取。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧。用尺取法来优化，可以使复杂度...

2020-05-24

1 617