4.10模拟赛T2
T2（矩阵快速幂）:
Luogu点我！
BZOJ点我！
T2:
数据范围就是矩阵快速幂不解释。
这题与P4159 [SCOI2009]迷路很类似，就是多了限制条件，也少了一些条件。
少了是边的权值变得只有1这一种权值。
多了不能 A->B->A 这种的走法。
如果没有限制走法，那么就是裸矩阵快速幂，只要将每个点看做矩阵上的元素，进行矩阵幂运算即可。
$ ft[i][j] = \sum{k=1}^{n} f{t-1}[i][k] \times f{t-1}[k][j] $也就是裸的矩阵乘法。
但是限制了一条边走过之后不能立马走回来。
那只要将矩阵中的点换成边即可:
$f_i[i][j]$ 表示从 第i条边的起点 走到 第j条边的终点的方案数。那就可以解决这个问题了。
upd:
问：为什么第65行的地方需要建立一条虚边？答：因为否则最终统计答案的时候不能确定从哪一条边的起点到终点的方案数了。Code:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 ...
BZOJ：2721: [Violet 5]樱花
数论好题
2721: [Violet 5]樱花
简化版:求方程 $ \dfrac{1}{X}+\dfrac{1}{Y}= \dfrac{1}{N!}$ 的正整数解的组数，其中 $ N≤10^6 $ 。
解的组数，应模$1e9+7$。
Input:
Output:
Sample Input:$1439$
Sample Output:$102426508$
HINT:
题解：STEP1:尝试化简该式子？
可以注意到 $X>N!$
那么可以设 $X = (N!+a)$
代入原式得:
$\dfrac{1}{N!+a}+\dfrac{1}{Y}= \dfrac{1}{N!}$
通分:
$Y×N!+N!\times(N!+a)=Y×(N!+a)$
化简:
$(N!)^2+aN!=aY$
$Y=\dfrac{(N!)^2}{a}+N!$
$a|(N!)^2$ 时$Y$为整数。
任意一个能整除$(N!)^2$的$a$可以确定一个$Y$从而确定$X$也就是该 $ \dfrac{1}{X}+\dfrac{1}{Y}= \dfrac{1}{N!}$方程的一组解。
$∴$ 答案就是$(N!)^2$的 ...
P3197 [HNOI2008]越狱
水一篇数论题解
题目P3197 [HNOI2008]越狱题目描述监狱有连续编号为 $1…N$ 的 $N$ 个房间，每个房间关押一个犯人，有 $M$ 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
输入输出格式输入格式：
输入两个整数 $M,N$
输出格式：
可能越狱的状态数，模 $100003$ 取余
输入输出样例输入样例#1：
12 3
输出样例#1：
16
思路开始做这题是顺推，不太好想。
尝试反推。
可能发生越狱状态 = 全部状态-不可能发生越狱状态于是问题变得清晰起来。
全部状态就是: $M^N$ (乘法原理)
而不可能发生越狱的状态就是: $M*(M-1) ^ {N-1}$(乘法原理)
取余后相减也许为负数所以对答案加上模数后再取模一次。$(((ksm(m,n)-(m*ksm(m-1,n-1)))%MOD+MOD)%MOD)$
使用快速幂计算幂次即可。
Code12345678910111213141516171819202122232425262728293031323334#include<cstdio& ...
3.20模拟赛(T3)&set容器的使用
set 是 STL 中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。set，顾名思义是“集合”的意思，在 set 中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差(set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用 multiset。
这题考了STL的使用——set。
T3 踮脚顾盼梨园
set 的常用操作12345678910111213141516171819202122232425262728293031323334353637383940//头文件 #include<set>//定义 set<int> S;//定义一个set set<int>::iterator it//定义一个迭代器//插入 S.inster(2);//插入元素2 ...
叁月拾日
今天是周日（怎么又是在学校里的周日啊！）周六的时候出乎意外。。妈妈居然来绍兴看我了？！好像是因为哥哥来绍兴有事所以顺道来看一下我。但是那会儿我到外面去吃晚饭去了，他们没见到我，就放了两箱牛奶（目前4箱）就去办事了。早饭吃了拌面（某师傅）午饭吃的黄焖鸡面晚饭吃的兰州拉面一日三餐都是面也是没谁了！下午的时候自己去打了一会儿篮球，然后去操场走了一会儿，学校是真的空啊。。现在21:24马上又回寝室了。但是今天似乎忘记了吃药。。明天可不能忘了吃药。
题解 P3382 【【模板】三分法】(粒子群优化)
粒子群优化（Particle Swarm Optimization,PSO），又称微粒群算法
其重要的迭代用的公式是这条:$v_i=v_i×w+c×rand()×(pbest_i+gbest- 2×x_i)$其中：
$v_i$是速度
$w$是惯性因子((0,1)的实数)，和学习因子相反，就是该粒子原来的速度的 参考权重 。比如我的这个程序里取的是0.5，而据说从大到小衰减会更好。因为大的时候会重视每个个体的价值，可以更全面的寻找可行解，而越趋于0就越注重社会的价值就是所有粒子中的最优解。
$C$是学习因子也就是权重一般取$2$。
我们可以通过这个速度向量来更新位置。
$ b[a].x += b[a].v; $
原理PSO算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是D维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi= （xi1, xi2, …, xiD），它经历过的最好位置（有最好的适应值）记为Pi= （pi1, pi2, ...
题解 P1429 【平面最近点对（加强版）】
随机旋转，按横坐标排序后枚举每个点与其后面5个点的距离取最小值更新答案(算法导论里有提到这个算法)
我这里随机旋转了两次（你想要转几次都行）记得初始化数据不然排序后的后面几个数据会凑巧有几个点在（0,0）旁可能会把答案更新成与（0,0）之间的距离。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#include<cstdlib>#include<ctime>#define INF 9999999999.0using namespace std;struct node{ double x,y;}a[2000010];int n;double ans=INF; ...