幻影彭的彩虹

前情提要

某道题，某人写了，然后交了，然后过了，但跑的很慢。

某人卡了好几次常，都不行。

看了下跑得比较快的代码，其实没啥差别。

输出运行时间，发现没什么差异，所以某人要对程序做个性能分析。

性能分析本质上是运行了一遍程序，然后把占用大量时间的函数抓出来，对这个函数进行优化。

在 Windows 下使用 gprof 对程序进行性能分析

gprof 是 g++ 自带的性能分析工具，简单易用，命令行中 gprof --version 查看是否可用，如果不行，先把 g++ 添加进系统路径里，多半就可以了。

性能分析需要特殊的编译参数，格式为

g++ -pg demo.cpp -o demo

其它参数可以照常添加，但是不能开 O2 等性能优化，这会破坏掉程序结构。

然后运行程序，这一步必不可少。

./demo

不要使用其它IDE编译执行后的gmon.out文件进行性能分析,请在命令行使用以上命令编译运行后进行下面的操作

gprof demo.exe gmon.out > result.txt

这会生成性能数据到 result.txt 中，查看一下就行。

最后一步中，.exe 不能省略

给出一个性能数据的例子,例子中有详细的解释，我就不解释了

~~啥，看不懂英文？那就别学了。~~

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 17.14      0.06     0.06        3    20.00    74.92  NTT(num*, int)
 17.14      0.12     0.06                             _mcount_private
 14.29      0.17     0.05 14680064     0.00     0.00  num::num(int, int, int)
 14.29      0.22     0.05  7602174     0.00     0.00  num::operator*(num const&)
 11.43      0.26     0.04  7077888     0.00     0.00  num::operator-(num const&)
 11.43      0.30     0.04                             __fentry__
  5.71      0.32     0.02  7077888     0.00     0.00  num::operator+=(num const&)
  2.86      0.33     0.01   392448     0.00     0.00  std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<num> >, std::is_move_constructible<num>, std::is_move_assignable<num> >::value, void>::type std::swap<num>(num&, num&)
  2.86      0.34     0.01   262144     0.00     0.00  num::operator*=(num const&)
  2.86      0.35     0.01                             main
  0.00      0.35     0.00  1177344     0.00     0.00  std::remove_reference<num&>::type&& std::move<num&>(num&)
  0.00      0.35     0.00   149817     0.00     0.00  void read<int>(int&)
  0.00      0.35     0.00   149815     0.00     0.00  num::num(int)
  0.00      0.35     0.00   149813     0.00     0.00  printf(char const*, ...)
  0.00      0.35     0.00   149813     0.00     0.00  num::get()
  0.00      0.35     0.00       16     0.00     0.00  quick(int, int, int, int)

 %         the percentage of the total running time of the
time       program used by this function.

cumulative a running sum of the number of seconds accounted
 seconds   for by this function and those listed above it.

 self      the number of seconds accounted for by this
seconds    function alone.  This is the major sort for this
           listing.

calls      the number of times this function was invoked, if
           this function is profiled, else blank.

 self      the average number of milliseconds spent in this
ms/call    function per call, if this function is profiled,
	   else blank.

 total     the average number of milliseconds spent in this
ms/call    function and its descendents per call, if this
	   function is profiled, else blank.

name       the name of the function.  This is the minor sort
           for this listing. The index shows the location of
	   the function in the gprof listing. If the index is
	   in parenthesis it shows where it would appear in
	   the gprof listing if it were to be printed.

Copyright (C) 2012-2018 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification,
are permitted in any medium without royalty provided the copyright
notice and this notice are preserved.

		     Call graph (explanation follows)


granularity: each sample hit covers 4 byte(s) for 2.86% of 0.35 seconds

index % time    self  children    called     name
                                                 <spontaneous>
[1]     71.4    0.01    0.24                 main [1]
                0.06    0.16       3/3           NTT(num*, int) [2]
                0.01    0.00  262144/262144      num::operator*=(num const&) [10]
                0.00    0.00  524286/7602174     num::operator*(num const&) [3]
                0.00    0.00       2/14680064     num::num(int, int, int) [6]
                0.00    0.00  149817/149817      void read<int>(int&) [96]
                0.00    0.00  149815/149815      num::num(int) [97]
                0.00    0.00  149813/149813      num::get() [99]
                0.00    0.00  149813/149813      printf(char const*, ...) [98]
                0.00    0.00      16/16          quick(int, int, int, int) [100]
-----------------------------------------------
                0.06    0.16       3/3           main [1]
[2]     64.2    0.06    0.16       3         NTT(num*, int) [2]
                0.05    0.02 7077888/7602174     num::operator*(num const&) [3]
                0.04    0.02 7077888/7077888     num::operator-(num const&) [4]
                0.02    0.00 7077888/7077888     num::operator+=(num const&) [8]
                0.01    0.00  392448/392448      std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<num> >, std::is_move_constructible<num>, std::is_move_assignable<num> >::value, void>::type std::swap<num>(num&, num&) [9]
-----------------------------------------------
                0.00    0.00  524286/7602174     main [1]
                0.05    0.02 7077888/7602174     NTT(num*, int) [2]
[3]     21.7    0.05    0.03 7602174         num::operator*(num const&) [3]
                0.03    0.00 7602174/14680064     num::num(int, int, int) [6]
-----------------------------------------------
                0.04    0.02 7077888/7077888     NTT(num*, int) [2]
[4]     18.3    0.04    0.02 7077888         num::operator-(num const&) [4]
                0.02    0.00 7077888/14680064     num::num(int, int, int) [6]
-----------------------------------------------
                                                 <spontaneous>
[5]     17.1    0.06    0.00                 _mcount_private [5]
-----------------------------------------------
                0.00    0.00       2/14680064     main [1]
                0.02    0.00 7077888/14680064     num::operator-(num const&) [4]
                0.03    0.00 7602174/14680064     num::operator*(num const&) [3]
[6]     14.3    0.05    0.00 14680064         num::num(int, int, int) [6]
-----------------------------------------------
                                                 <spontaneous>
[7]     11.4    0.04    0.00                 __fentry__ [7]
-----------------------------------------------
                0.02    0.00 7077888/7077888     NTT(num*, int) [2]
[8]      5.7    0.02    0.00 7077888         num::operator+=(num const&) [8]
-----------------------------------------------
                0.01    0.00  392448/392448      NTT(num*, int) [2]
[9]      2.9    0.01    0.00  392448         std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<num> >, std::is_move_constructible<num>, std::is_move_assignable<num> >::value, void>::type std::swap<num>(num&, num&) [9]
                0.00    0.00 1177344/1177344     std::remove_reference<num&>::type&& std::move<num&>(num&) [95]
-----------------------------------------------
                0.01    0.00  262144/262144      main [1]
[10]     2.9    0.01    0.00  262144         num::operator*=(num const&) [10]
-----------------------------------------------
                0.00    0.00 1177344/1177344     std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<num> >, std::is_move_constructible<num>, std::is_move_assignable<num> >::value, void>::type std::swap<num>(num&, num&) [9]
[95]     0.0    0.00    0.00 1177344         std::remove_reference<num&>::type&& std::move<num&>(num&) [95]
-----------------------------------------------
                0.00    0.00  149817/149817      main [1]
[96]     0.0    0.00    0.00  149817         void read<int>(int&) [96]
-----------------------------------------------
                0.00    0.00  149815/149815      main [1]
[97]     0.0    0.00    0.00  149815         num::num(int) [97]
-----------------------------------------------
                0.00    0.00  149813/149813      main [1]
[98]     0.0    0.00    0.00  149813         printf(char const*, ...) [98]
-----------------------------------------------
                0.00    0.00  149813/149813      main [1]
[99]     0.0    0.00    0.00  149813         num::get() [99]
-----------------------------------------------
                0.00    0.00      16/16          main [1]
[100]    0.0    0.00    0.00      16         quick(int, int, int, int) [100]
-----------------------------------------------

 This table describes the call tree of the program, and was sorted by
 the total amount of time spent in each function and its children.

 Each entry in this table consists of several lines.  The line with the
 index number at the left hand margin lists the current function.
 The lines above it list the functions that called this function,
 and the lines below it list the functions this one called.
 This line lists:
     index	A unique number given to each element of the table.
		Index numbers are sorted numerically.
		The index number is printed next to every function name so
		it is easier to look up where the function is in the table.

     % time	This is the percentage of the `total' time that was spent
		in this function and its children.  Note that due to
		different viewpoints, functions excluded by options, etc,
		these numbers will NOT add up to 100%.

     self	This is the total amount of time spent in this function.

     children	This is the total amount of time propagated into this
		function by its children.

     called	This is the number of times the function was called.
		If the function called itself recursively, the number
		only includes non-recursive calls, and is followed by
		a `+' and the number of recursive calls.

     name	The name of the current function.  The index number is
		printed after it.  If the function is a member of a
		cycle, the cycle number is printed between the
		function's name and the index number.


 For the function's parents, the fields have the following meanings:

     self	This is the amount of time that was propagated directly
		from the function into this parent.

     children	This is the amount of time that was propagated from
		the function's children into this parent.

     called	This is the number of times this parent called the
		function `/' the total number of times the function
		was called.  Recursive calls to the function are not
		included in the number after the `/'.

     name	This is the name of the parent.  The parent's index
		number is printed after it.  If the parent is a
		member of a cycle, the cycle number is printed between
		the name and the index number.

 If the parents of the function cannot be determined, the word
 `<spontaneous>' is printed in the `name' field, and all the other
 fields are blank.

 For the function's children, the fields have the following meanings:

     self	This is the amount of time that was propagated directly
		from the child into the function.

     children	This is the amount of time that was propagated from the
		child's children to the function.

     called	This is the number of times the function called
		this child `/' the total number of times the child
		was called.  Recursive calls by the child are not
		listed in the number after the `/'.

     name	This is the name of the child.  The child's index
		number is printed after it.  If the child is a
		member of a cycle, the cycle number is printed
		between the name and the index number.

 If there are any cycles (circles) in the call graph, there is an
 entry for the cycle-as-a-whole.  This entry shows who called the
 cycle (as parents) and the members of the cycle (as children.)
 The `+' recursive calls entry shows the number of function calls that
 were internal to the cycle, and the calls entry for each member shows,
 for that member, how many times it was called from other members of
 the cycle.

Copyright (C) 2012-2018 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification,
are permitted in any medium without royalty provided the copyright
notice and this notice are preserved.

Index by function name

   [2] NTT(num*, int)          [6] num::num(int, int, int) [9] std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<num> >, std::is_move_constructible<num>, std::is_move_assignable<num> >::value, void>::type std::swap<num>(num&, num&)
  [96] void read<int>(int&)   [10] num::operator*=(num const&) [7] __fentry__
 [100] quick(int, int, int, int) [4] num::operator-(num const&) [5] _mcount_private
  [98] printf(char const*, ...) [3] num::operator*(num const&) [1] main
  [99] num::get()              [8] num::operator+=(num const&)
  [97] num::num(int)          [95] std::remove_reference<num&>::type&& std::move<num&>(num&)

VTune

一个更厉害的性能分析工具，可以分析 CPU 流水线利用率和高速缓存命中率等进一步性能。

ARC144D

题意略。

观察，发现 $x \& y + x |y = x+y$，原因是每个二进制位，如果出现两次，会计入二次，如果出现一次，会计入一次。猜想 $f(x)$ 的值与每个二进制位相关且对于每个二进制位独立。

考虑证明，对 $x$ 的二进制下 $1$ 的个数 $n$ 做归纳。

对于 $n=0$，$f(0)=f(0)$

对于 $n=1$，$f(2^i) = f(2^i)$

对于 $n=2$，$f(2^i+2^j) + f(0) = f(2^i) +f(2^j)$

考虑证明 $n=k$ 时， $f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)$

设对于 $n=k-1$ 其成立，对于二进制位 1 个数为 k 的 x， $\forall i\in x,f(x)+f(0)=f(x-2^i) + f(2^i)$，易证 $f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)$，且对于所有涉及元素二进制下 1 个数少于 n 的，所有限制满足。

故只需要确定 $f(2^i)$ 和 $f(0)$。其最终限制有两个，其一是，最大值不能超过 $k$，其二是最小值不能小于 0，最大值一定是把所有大于 $f(0)$ 的元素加起来，最小值则是把所有小于 $f(0)$ 的元素加起来。

枚举 $f(0)$ 和小于 $f(0)$ 的元素个数，我们可以将限制分配给对应元素，得到和式： \[ ans=\sum\limits_{f(0)=0}^{k}\sum\limits_{i=0}^{n}\binom{n}{i}\binom{f(0)}{i}\binom{k-f(0)+n-i}{n-i} \] 第一项计算那些小于 $f(0)$，第二项是将至多 $k$ 个冗余值分配给 $i$ 个小于 $f(0)$ 的元素的方案数，每个元素至少分配一个，或者说 $i$ 个正整数变量和为 $f(0)$ 的方案，可以给一个虚拟元素分别大于等于 0 个表示放弃，所以先给虚拟元素一个，变成 $f(0)+1$ 个元素插 $i$ 个板。最后一项是 $n-i$ 个非负整数变量，和不超过 $k-f(0)$ 的方案。先来个虚拟变量，然后先各自加 $1$，然后就是 $k-f(0)+n-i+1$ ，间隔是 $k-f(0)+n-i$ 个，版一共 $n$ 个。

解释完了，考虑计算，二维的，算不了。

考虑后两项的组合意义。

根据组合恒等式中的第五个。

对原式变形有 \[ ans=\sum\limits_{i=0}^{n}\binom{n}{i}\binom{k-f(0)+n-i+1}{n-i+1} \] 然后 $n$ 不大，维护个区间乘积枚举计算就行，记得对计算乘积的元素取模。

组合恒等式

题不是终点，组合恒等式才是重点

对上面那种图的组合恒等式，我们一一证明

式子1

\[ \sum\limits_{k}\binom{r}{m+k}\binom{s}{n-k}=\binom{r+s}{m+n} \]

组合意义证明

第一项是从 $r$ 个选 $m+k$ 个，第二项是从 $s$ 个选 $n-k$ 个，把两个拼在一起，从 $r+s$ 个中选 $n+m$ 个，容易发现和前者一一对应，故恒等。

代数证明

咕咕咕

式子2

\[ \sum\limits_{k}\binom{l}{m+k}\binom{s}{n+k} = \binom{l+s}{l-m+n},l\ge0 \]

组合意义证明

代数证明

咕咕咕

式子3

2022.7.5考试总结

发表于 2022-07-12 更新于 2025-02-16 分类于算法竞赛

T1

某个不太正确的方式

想到了分块，暴力没操过去。

考虑暴力计算出前 $\sqrt P$ 个数的值，期望得到的最大值为 $P-\sqrt P$，剩下来的数一定不多，我的想法是分块探测一下下一个块中是否存在比当前最大值更大的数，探测方式是用个 $\text{hash\_table}$ 记录下每块的每个数的方幂，然后把等式左边乘上逆元后再查找，但是这个做法只有 $60pts$，虽然我本机能跑过。

后面想了一下还看了下代码，这个方式的复杂度是错的，因为探测总次数还是不对头。2022.10.7

正常的考虑方式

发现我们对同一个数的探测次数有点多，考虑能不能对一个数只探测一次。本质上是需要求 $P-1,P-2,\cdots P - \sqrt P$ 这些数在数列中出现的第一个位置。我们的探测实际上是判断了一个幂函数的解是否存在于一个区间。所以直接考虑求解这个幂函数方程 $x^r = a$。

考虑 $BSGS$，但是需要解 $T\times \sqrt{P}$ 次，每次的复杂度为 $O(\sqrt P)$，不如暴力。

考虑平衡复杂度，设暴力处理的长度为 $S$，$BSGS$ 预处理长度为 $B$，那么复杂度为 $T(S+ + B) $

后面那一坨最优应该是 $3e6$ ，压力山大。

发现质数是同一个质数，有没有什么办法可以优化一下。

答案是，处理离散对数。

离散对数有着和正常对数一样优美的换底公式，如果我们对 $x,P-1,P-2\cdots P-\sqrt P$。向 $P$ 的原根 $g$，取对数，那么可以利用换底公式很方便的求解 $x^r = a$，取对数的过程就是 $BSGS$，注意到换底公式的除法变成了模 $P-1$ 意义下的除法，因为 $g^{P-1} = 1$。

所以 $BSGS$ 的总次数变为了 $O(\frac{P}{S})$ 次，预处理只需要一次。这里可以放开玩。

总复杂度变为了 $O(T*(S+\frac{P}{S})+ B + \frac{P}{S}\times\frac{P}{B})$

取 $B = P^{\frac{3}{4}}$，$S=\sqrt P$ 可以取到最优。

我实现的时候写的比较丑，算了每个东西的位置之后，还需要排个序，实际上从大到小倒着做就可以了。

看看佳老师的代码，长进不少。

T2

定义字符串的 border 为一个它的前缀，这个前缀也是它的后缀。

场上是只会 $O(n^2)$ 的，还 TM 暴力打挂了只有 40。

后面了解到可以用 FFT 处理带通配符的字符串匹配问题。

具体的，定义距离函数 $d_i=\sum\limits_{j=1}^{m} s_{i+j-1}t_i(s_{i+j-1}-t_j)^2$

显然，如果距离 $d_i$ 为 $0$，那么 $i$ 开头的字符串就能匹配上。

下标有点问题，所以把 $t$ 反转一下，把式子拆了，就是三遍 FFT 求出来每一个 $d_i$。

我们就知道了哪些结束位置可能可以匹配上。

不是所有能匹配上的位置一定可以对答案贡献，因为如果前面的匹配上了，通配符就没了，所以后面要匹配上，就要求重叠的部分必须是一个 border。

其实 border 在字符串随机的情况下是很少的。我们可以考虑记录下所有的 border，然后 dp，设 dp[i] 表示强制 i 结尾匹配上了，最多能匹配的个数，如果 $j\leq i-m$，就是个前缀 max，如果 $j> i-m$，就只有 border 能转移。

border 有个性质，就是它们的长度构成 $\log n$ 个等差数列，所以我们考虑对每个等差数列做转移。

更具体的，如果 $next[n]>\frac{n}{2}$，那么模板串一定是一个循环，并且最小循环长度为 $n-next[n]$，它的长度大于等于 $r=n\%(n-next[n])$ 的 border 一定构成一个公差为 $d=n-next[n]$ 的等差数列。这样的话，$n$ 每次至少减半，所以至多有 $\log n$ 个等差数列。

考虑证明。如果存在一个长度大于 $r$ 的 border $x$ 长度不能写成 $kd+r$，感性理解下，把原串划分为长度为 $d$ 的小串，把 $x$ 在末尾的部分平移到开头，显然它还有一个更小的循环。

所以我们对于一个点，含 border 的转移就可以分为 $\log n$ 类，对每一类记一个前缀 $\max$ 即可转移，注意每一类需要按照模公差分类。

注意转移细节。

#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=2e5+10;
const double Pi=acos(-1.0);
struct comple{
	double x,y;
	comple operator +(const comple &a){return comple{x+a.x,y+a.y};}
	comple operator -(const comple &a){return comple{x-a.x,y-a.y};}
	comple operator *(const comple &a){return comple{x*a.x-y*a.y,x*a.y+y*a.x};}
	void operator +=(const comple &a){x+=a.x,y+=a.y;}
	void operator -=(const comple &a){x-=a.x,y-=a.y;}
	void operator *=(const comple &a){double tp=x;x=x*a.x-y*a.y,y=tp*a.y+y*a.x;}
};
int i,j,k,n,s,t,m,lim,ans;
int res[N],vala[N],valb[N],sum[N],nxt[N];
int dp[N],border[N][2],pre[32][N][2],from[N];
char ch[N],str[N];
double d[N];
comple a[N],b[N],c[N];
void FFT(comple val[],int type=1){
	for(i=0;i<1<<lim;i++)if(res[i]>i)swap(val[res[i]],val[i]);
	for(i=1;i<=lim;i++){
		for(j=0;j<1<<lim;j+=1<<i){
			comple w={1,0},wn={cos(2*Pi/(1<<i)),type*sin(2*Pi/(1<<i))};
			for(k=0;k<1<<i-1;k++,w*=wn){
				comple y=val[k+j+(1<<i-1)]*w;
				val[k+j+(1<<i-1)]=val[k+j]-y,val[k+j]+=y;
			}
		}
	}
	if(type==-1)for(i=0;i<1<<lim;i++)c[i].x/=(1<<lim);
}
void get_border(int x){
	if(x==0)return ;
	border[++s][0]=nxt[x],border[s][1]=x-nxt[x];
	if(nxt[x]*2>x)get_border(x%(x-nxt[x]));
	else get_border(nxt[x]);
}
void print(int pos,int lst){
	if(dp[pos]==0)return ;
	for(i=1,j=pos-m+1;i<=m&&j<lst;i++,j++){
		if(ch[j]!='?'&&ch[j]!=str[i]){
			printf("Error");
			return ;
		}
		if(j<1)continue;
		ch[j]=str[i];
	}
	print(from[pos],pos-m+1);
}
signed main()
{
 	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	//freopen(".in","w",stdout);
	scanf("%s%s",ch+1,str+1);
	n=strlen(ch+1),m=strlen(str+1);
	nxt[0]=j=-1;
	for(i=1;i<=m;i++){
		while(j!=-1&&str[j+1]!=str[i])j=nxt[j];
		nxt[i]=++j;
	}
	get_border(m);border[s][1]=1;
	while(1<<lim<=n+m)lim++;
	for(i=1;i<1<<lim;i++)res[i]=res[i>>1]>>1|(i&1)<<lim-1;
	for(i=1;i<=n;i++)vala[i]=ch[i]=='?'?0:ch[i]-'a'+1,sum[i]=sum[i-1]+vala[i]*vala[i]*vala[i];
	for(i=1;i<=m;i++)valb[i]=str[i]-'a'+1;
	
	for(i=1;i<=n;i++)a[i]={pow(vala[i],2)};
	for(i=1;i<=m;i++)b[i]={-2*valb[m-i+1]};
	FFT(a),FFT(b);
	for(i=0;i<1<<lim;i++)c[i]+=a[i]*b[i];
	memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
	for(i=1;i<=n;i++)a[i]={vala[i]};
	for(i=1;i<=m;i++)b[i]={pow(valb[m-i+1],2)};
	FFT(a),FFT(b);
	for(i=0;i<1<<lim;i++)c[i]+=a[i]*b[i];
	FFT(c,-1);
	for(i=m;i<=n;i++)
	d[i]=sum[i]-sum[i-m]+c[i+1].x;

	for(i=m;i<=n;i++){
		for(j=1;j<=s;j++){
			if(pre[j][i-m+border[j][0]][0]+1>dp[i]){
				dp[i]=pre[j][i-m+border[j][0]][0]+1;
				from[i]=pre[j][i-m+border[j][0]][1];
			}
		}
		if(abs(d[i])>0.1)dp[i]=0;
		for(j=1;j<=s;j++){
			pre[j][i][0]=dp[i],pre[j][i][1]=i;
			if(pre[j][i-border[j][1]][0]>pre[j][i][0]){

				pre[j][i][0]=pre[j][i-border[j][1]][0];
				pre[j][i][1]=pre[j][i-border[j][1]][1];
			}
		}
		if(dp[i]>dp[ans])ans=i;
	}
	cout<<dp[ans]<<endl;
	print(ans,ans+1);
	for(i=1;i<=n;i++)if(ch[i]=='?')ch[i]='a';
	cout<<ch+1<<endl;
	return 0;
}

Python 一些强调的东西

发表于 2022-07-12 更新于 2025-03-11 分类于技术

pip 和包

网络问题

GFW 会墙掉默认的 pip 源, 所以请使用国内源.

不建议使用代理连接国外源.

使用国内源时一些注意事项:

彻底关闭代理软件(退出软件, 关 System Proxy 没用), 并检查系统代理设置, 确认没有设置代理端口. 由它引起的报错:

SSL 错误(报错大概长下面这样), 国内源不允许代理连接, 用的 TLS 方式, 代理的 SSL 证书通不过验证.

WARNING: Retrying (Retry(total=4, connect=None, read=None, redirect=None, status=None)) after connection broken by 'SSLError(SSLEOFError(8, '[SSL: UNEXPECTED_EOF_WHILE_READING] EOF occurred in violation of protocol (_ssl.c:1000)'))': /simple/proxyscrape/

Proxy 连接错误(报错大概长下面这样). 原因是命令行代理没有配置好, 但是 pip 检测到了系统有代理尝试使用.

WARNING: Retrying (Retry(total=4, connect=None, read=None, redirect=None, status=None)) after connection broken by 'ProxyError('Cannot connect to proxy.', timeout('_ssl.c:1091: The handshake operation timed out'))': /simple/pandas/

清华源同步很慢, 速度不稳定, 建议使用阿里云源, 命令行执行(永久设置):

1 2	pip config set global.index-url https://mirrors.aliyun.com/pypi/simple/ pip config set global.trusted-host mirrors.aliyun.com

检查全局源设置:

1	pip config list

输出应该是:

1 2	global.index-url='https://mirrors.aliyun.com/pypi/simple' install.trusted-host='mirrors.aliyun.com'

虚拟环境

Python 包各种包的有复杂的版本依赖关系, 把所有包装在一起不可取.

建议安装个 anaconda 创建虚拟环境, 然后在虚拟环境里安装包.

anaconda 安装教程.

额外提几个注意:

安装 conda 前, 应该彻底卸载之前安装的 Python, 直接用卸载功能不会删除 pip 相关的包, 正确的卸载方式:
1. 找到并记住安装路径.
2. 用卸载程序(就是安装包)卸载.
3. 彻底删除安装路径.
第一次安装 conda 完成后, 必须在终端执行 conda init 命令使 conda 生效.

局部环境

虚拟环境本质上就是建立了若干个局部环境, 并使用一个全局的管理工具来管理这些局部环境.

所以也可以直接建立局部环境, Python 的标准库有个 venv, 就是用局部环境来做虚拟环境的.

局部环境也可以用安装包安装, 不要勾选添加系统路径, 然后自定义安装路径就能安装 Windows 的 Python 局部环境.

Linux 下安装 Python 局部环境

用局部环境的路径去运行 pip, Python 时, 所有操作都会在这个局部环境里执行, 与全局环境无关.

理论上这个东西在制作傻瓜式软件的时候有一定作用, 但根据我的经验, 虽然可能全国有 1% 的人会 Python, 但全国只有 0.1% 的人能够正确安装小众的 Python 第三方库, 所以还是很有用的.

~~上周见到两个 conda 装了不 init 的胎神.~~

import

name

__name__ 是 Python 的一个内置变量, 用于判断当前文件是否被直接运行.

用 python xxx.py 直接运行, __name__ 为 "main".

用 python -m xxx 间接运行, __name__ 为模块名.

import 包时的执行逻辑

用 import 或者 from 导入模块时, 对应模块代码会被原封不动的全部执行一遍, 执行时, 被 import 的代码中 __name__ 为 模块名.

import 寻找顺序

有一个 sys.path 变量, 里面存着一些路径, 用于寻找模块. 这玩意是个列表, 从前往后依次寻找, 找到就开始导入, 顺序大概这样: 1. 在工作目录下寻找(绝对或相对导入). 2. 在 site-packages 目录下寻找(仅绝对导入).

莫名其妙的 id 不一致问题

有时候, 你手动加了 sys.path 后, 导入时全局变量可能会出现 id 不一致的问题, 讲下原因:

ma 模块假设在 module/ma.py 里.
a.py 代码用 module.ma 导入了 ma 模块的一个全局变量 g.
往 sys.path 里加了 module 这个目录.
module/b.py 代码中用 ma 导入了 ma 模块的全局变量 g.
a.py 和 b.py 里 g 的 id 不一致.

所以别问为啥全局变量修改无效了.

从不同目录下(sys.path值不同)导入同一个文件时, 被导入的模块代码有不同的 id, 所以里面的东西也有两份.

无特殊需求, 只建议项目使用绝对导入.

import 的代码到底执行了几遍

用同一个 sys.path 量导入的模块代码只会执行一遍, 第一次执行后被加进 cache 里了, 第二次 import 时发现 cache 里有就直接用 cache 里的了, 不执行第二次.

PYPI

PYPI 打包发布的时候, 如果文件夹没有 __init__.py 文件, 那么这个文件夹会扔掉打包不进去.

关于 Request 这一类网络请求函数

Requests 库的 POST 相关

requests 的 post 方法有点坑，目前主流数据提交方式都是 json，所以一般用 json 这个可选参数传参，data 传参可能会因为格式问题导致请求失败。
需要显式指定协议，直接写 example.com 会报错。

import requests

requests.post("http://example.com", json={
    "token": "xxx",
    "value": "yyy"
})

Request 爬虫的时代已经过去了, 现在用 selenium 吧.

当然如果直接最简单的 Request 没出问题也不妨试试.

一些有用的命令

发表于 2022-07-12 更新于 2025-02-16 分类于技术

设置 pip 默认下载源

pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple

Hexo-NexT 博客部署

发表于 2022-07-12 更新于 2025-03-10 分类于技术

参考

环境

基础

git
nodejs && npm

开工作目录

npm install hexo-cli -g
hexo init blog
cd blog
npm install
hexo server

工作目录是 blog，记住，这很重要，文件名默认为相对工作目录的名字。

本地预览

工作目录下：

1	hexo g && hexo s

localhost:4000 上看。

开 GitHub Pages 仓库

每个账号只能开一个，仓库名 username.github.io。

配源码分支

创仓库的时候把 main 弄下来，源码（不含 public）放这里，免得被覆盖。

自动部署

工作目录下安自动部署工具。

1	npm install hexo-deployer-git --save

_config.yml 末尾加上（记得照着用户名改动）：

deploy:
  type: git
  repo: https://github.com/username/username.github.io.git
  branch: master
  # message: Site updated: {{ now('YYYY-MM-DD HH:mm:ss') }})

部署：

1	hexo clean && hexo g && hexo d

metadata

搜 _config.yml 相关配置项：

title: 幻影彭的彩虹
subtitle: '记录青春的扇区'
description: ''
keywords: '算法竞赛, 自动化测试, 工程技术, Python'
author: huan-yp
language: zh-CN # 必须改

url: https://huanyp.cn

主题

安主题（next）

工作目录下：

1	git clone https://github.com/next-theme/hexo-theme-next themes/next

写上要用这个主题

_config.yml 里，找到 theme，写上 next

我用 next 主题。

配置菜单。

menu:
  home: / || fa fa-home
  about: /about/ || fa fa-user
  tags: /tags/ || fa fa-tags
  categories: /categories/ || fa fa-th
  archives: /archives/ || fa fa-archive
  # schedule: /schedule/ || fa fa-calendar
  sitemap: /sitemap.xml || fa fa-sitemap
  commonweal: /404/ || fa fa-heartbeat

scheme

在 themes/next/_config.yml 调 scheme，传统的应该选 Gemini。

# Schemes
# scheme: Muse
# scheme: Mist
# scheme: Pisces
scheme: Gemini

dark

应该没有人喜欢 light，所以调成 dark。

在 themes/next/_config.yml 调 darkmode。

1	darkmode: true

背景

一般要加个背景图片什么的

准备 source 图片

图片放到 themes/next/source/image/background.jpg 里。

改 style

找到 themes\next\source\css\_schemes\Gemini\index.styl，加上：

body {
    background:url(/images/background-now.jpg);
    background-repeat: no-repeat;
    background-attachment:fixed; //不重复
    background-size: cover;      //填充
    background-position:50% 50%;
}


// 博客内容透明化
// 文章内容的透明度设置
.content-wrap {
  opacity: 0.7;
}


// 侧边框的透明度设置
.sidebar {
  opacity: 0.7;
}

// 菜单栏的透明度设置
.header-inner {
  background: rgba(255, 255, 255, 0.8);
}

// 搜索框（local-search）的透明度设置
.popup {
  opacity: 0.7;
}

//博客内容透明化

:root {
  --content-bg-color: rgba(255, 255, 255, 0.8);
}

那个 [0, 1] 的参数是透明度，自己估摸着调。

友情链接

1 2	menu: 友情链接: /links/ \|\| fa fa-link

写中文就行。

内联 html

新建 source/links/index.md，写入：

{% raw %}
<div class="post-body">
   <div id="links">
      <style>
         .links-content{
         margin-top:1rem;
         }
         .link-navigation::after {
         content: " ";
         display: block;
         clear: both;
         }
         .card {
         width: 45%;
         font-size: 1rem;
         padding: 10px 20px;
         border-radius: 4px;
         transition-duration: 0.15s;
         margin-bottom: 1rem;
         display:flex;
         }
         .card:nth-child(odd) {
         float: left;
         }
         .card:nth-child(even) {
         float: right;
         }
         .card:hover {
         transform: scale(1.1);
         box-shadow: 0 2px 6px 0 rgba(0, 0, 0, 0.12), 0 0 6px 0 rgba(0, 0, 0, 0.04);
         }
         .card a {
         border:none;
         }
         .card .ava {
         width: 3rem!important;
         height: 3rem!important;
         margin:0!important;
         margin-right: 1em!important;
         border-radius:4px;
         }
         .card .card-header {
         font-style: italic;
         overflow: hidden;
         width: 100%;
         }
         .card .card-header a {
         font-style: normal;
         color: #2bbc8a;
         font-weight: bold;
         text-decoration: none;
         }
         .card .card-header a:hover {
         color: #d480aa;
         text-decoration: none;
         }
         .card .card-header .info {
         font-style:normal;
         color:#a3a3a3;
         font-size:14px;
         min-width: 0;
         overflow: hidden;
         white-space: nowrap;
         }
      </style>
      <div class="links-content">
         <div class="link-navigation">
            <div class="card">
               <img class="ava" src="博客图标" />
               <div class="card-header">
                  <div>
                     <a href="博客链接">博客名字</a>
                  </div>
                  <div class="info">博客简介</div>
               </div>
            </div>
            <div class="card">
               <img class="ava" src="博客图标" />
               <div class="card-header">
                  <div>
                     <a href="博客链接">博客名字</a>
                  </div>
                  <div class="info">博客简介</div>
               </div>
            </div>
         </div>
      </div>
   </div>
</div>
{% endraw %}

要加的时候在这复制 html 就行。

杂项

置顶文章

工作目录下执行：

1 2	npm uninstall --save hexo-generator-index npm install --save hexo-generator-index-pin-top

metadata 部分写：

---
title: Title
top: true
---

即可置顶。

折叠

在 metadata 中加上:

1
2
3

---
description: 文件摘要
---

即可折叠.

插件

搜索插件

工作目录下：

1	npm install hexo-generator-searchdb

主题配置 themes/next/_config.yml 下：

local_search:
  enable: true
  # Show top n results per article, show all results by setting to -1
  top_n_per_article: 2
  # Unescape html strings to the readable one.
  unescape: false
  # Preload the search data when the page loads.
  preload: false

有时候会出现部分文章能搜索，部分文章不能搜索的情况。这一般是因为 search.xml 中有不合法的字符导致 xml 解析失败引起的。浏览器访问一下你的 xml 文件，会有报错提示你在哪里。

数学插件

一般用 Mathjax。

先安装 Pandoc，这个要改系统路径，需要重启终端。

工作目录下执行：

1 2	npm uninstall hexo-renderer-marked npm install hexo-renderer-pandoc

改 themes/next/_config.yml 的 math 配置：

math:
  mathjax:
    enable: true
    # Available values: none | ams | all
    tags: all

每篇文档的 metadata 部分要写启用 Mathjax：

---
title: Hello World
mathjax: true
---

参考资料：Next 官方有关文档。

常用命令

hexo g : 生成
hexo s : 本地部署
hexo d : 远端部署

网络相关

CNAME

hexo d 的时候因为是强制 push 的, github CNAME 文件时会被覆盖, 导致域名解析错误.

解决方式

将 CNAME 放入 ./source，即存在 ./source/CNAME 文件。

SEO

在 google search console 申请抓取的时候，一定要看清楚是不是 https 协议，如果部署在 github 上，可能会强制 https，导致抓取出现重定向错误。如果出现了这个错误，有可能是没用 https 协议。

做题3

发表于 2022-07-12 更新于 2025-02-16 分类于算法竞赛

CF1698F

思路

变过来变过去，还 TM 离谱的操作当然要找不变量，算是半个套路。

reverse 两端相等的区间，可以发现每两个相邻元素构成的无序对不变，然后第一个元素和最后一个元素不改变。

换句话说，$\{(a_i,a_{i+1},i \in [1,n)\}$ 这个集合不随 $a$ 中操作改变。或者说，如果从 $a_i$ 到 $a_{i+1}$ 连边，这张无向图是不变的，同时 $a_1,a_n$ 不改变。这个条件和上个条件之间的转换是解题的关键点之一。

套路又来了，看看样例，集合相同并且首尾相同这个条件貌似挺充分的，所以考虑证明。

对于构造问题，常用的证明方式是数学归纳法。

事实上，如果我们能证明如果第二个数可以成功调整为相同，那么整个数组也可以，因为满足条件的 $a,b$ 如果同时删掉第一个数，仍满足条件。

考虑构造方案，由结论可以知道，如果 $a$ 中必定存在 $(b_1,b_2)$ 无序对，因为 $a_2\neq b_2$，不妨让这对无序对是 $(a_x,a_{x+1}),x\in[2,n)$，如果 $a_x=b_2$，考虑直接将这一对中的 $a_{x+1}$ 和 $a_1$ 子数组 reverse ，完事。如果 $a_{x+1}=b_2$，事情有点麻烦。

if only i could find a pair which...

补上那句话，如果能找到一对可以被翻转的，左端点在 $[1,x]$ ，右端点在 $(x,n]$ 的，那么我们就翻转，改变了 $a_x,a_{x+1}$ 的顺序。

尝试证明一定能找到，即 $\{a_i ,i\in [1,x]\} \bigcap \{a_i.i\in(x,n]\} \neq \emptyset$

反证法，如果找不到，那么可知 $a_i,i$ 与 $a_j,j\in (x,n]$ 除开 $(a_i,a_i+1)$ 这一次相邻外均不相邻，考虑 $b_2$ 即 $a_{x+1}$ 的情况，它与 $b_3$ 相邻，可知 $b_3 \in \{a_i.i\in(x,n]\}$，同理有 $\forall j\ge 2,b_j\in\{a_i.i\in(x,n]\}$

考虑 $a_2$，它显然不存在于 $b$，故矛盾。

回顾

这题比较难的有两个点，一是注意到这个不变量极大可能是充分条件，二是发现 $a_{x+1}=b_2$ 的 case 中一定存在可交换项，搞定了这两个，问题就迎刃而解。关键点在于第二个，找到 $a_{[1,x]},a_{[x+1,n]}$ 交集的关系，并尝试用反证法证明交集不为空是比较困难的。

ABC259G

很有意思的网络流题。

最开始想到二分图相关，因为 $A_{i,j} <0$ 的限制指向性比较明确，然后发现如果二分图的决策正数话会出现不同块之间相互影响，所以考虑决策负数，决策负数不同联通块互不影响，但是无法计算答案，因为最终还是需要确定到底哪些正数被选了。

解法一

题解给出了一个新思路，考虑先只把所有正数选了，然后再来看满足条件的代价。

代价被分为了三类，第一类是顺带选择的负数的代价，如果选了一行或者一列，就会有这一行或列所有负数绝对值之和的代价。

第二类是无法选择正数的代价，如果正数所在的行和列都没被选择，那么就会有这个正数的代价。

第三类是重复选择负数的代价，如果一个负数被行和列同时选择（为了付出更少的第二类和其它第一类代价），那么这个代价是无穷大。

我们需要最小化代价。

0/1 决策问题，考虑套最小割上去，每一行每一列视为一个点。

令与 $s$ 同集合的为选择，与 $t$ 同集合的为不选，选一行或一列的代价为该行或列负数绝对值之和，从个点到 $t$ 连边就行，行列同时选择负数，代价为 inf，woc，怎么连呢？从行连向列，意义为选了行不选列的代价，从列向行连，意义为选了列不选行的代价。所以我们前面的安排有些问题，需要做出调整。

对于行和列，我们让属于 s,t 所在集合对它们有不同意义，下面让属于 s 的行为不选择，属于 t 的列为不选择，我们让 $s$ 向行连边，这条边表示选该行的代价，让列向 $t$ 连边，表示选该列的代价。于是，对于一个点，行列都选的代价当且仅当 $A_{i,j}<0$ 时为 inf，此时从列向行连边，表示都选的代价，行列都不选的代价当且仅当 $A_{i,j}\ge0$ 时为 $A_{i,j}$，此时从行向列连边。

注意，我们的割中如果出现了行列都不选，那么对应的行和列与 $s,t$ 的边一定没有断开，所以必须断开行到列的边。如果出现了行和列都选的不合法情况，我们发现，断掉的行能到 $t$，从 $s$ 一定能到断掉的列。如果不满足，那么这个割就不是最小割，不会被我们考虑。所以我们需要从列到行连边，保证不会给负数打上两个标记。

这种思路和某类 dp 的思路很类似，相当值得学习，其实在原问题的求解中，并没有什么条件来保证不会给一个负数打上两个标记，但是我们在通过最小割求解时，限定了决策的范围和最优性，获得了额外的信息，也就能帮助我们排除掉难处理但是不可能的情况，本质上，这种排除还和我们先假定所有正数都选上的前提有关系，这种解法相当精妙。

解法二

从直觉上来看，应该不会选择和为负数的行或者列。考虑一个最终方案，它的答案会是 $\sum 选择的行+\sum 选择的列 -\sum 行列交叉处的正数$。考虑从这里面剔除和为负数的列或行，发现最终值一定变大。

所以删掉和为负数的行和列。

考虑先把剩下的行和列全选了，然后解决冲突。

解决冲突的方式有三种，一种时不选行，一种是不选列，另一种是硬吃同时选的代价。

这样的建图就很简洁了，从 $s$ 向行，列向 $t$ 连边，对于交点，正数连其值的边，负数连 inf 边。很容易发现一个合法解和一个割一一对应，over。

Sum up

最小割解决实际问题的核心，在于用一个割，或者可能成为最小割的割，来代表一个实际的决策方案，最小割的容量，代表代价，每个点在哪个割集分别代表什么含义并不重要，重要的是割掉每条边的意义，和决策方案与最小割的对应关系。

其实这道题还给我们一个启发，就是在考虑0/1决策问题时，可以先考虑钦定一个决策，再来调整使得它合理或者变优，这可能会使得问题变得简单，也许算是一个套路。

本质上，最小割表达了一种最优的解决决策冲突的方案，我们在 0/1 决策问题钦定决策的过程中，制造了一些冲突，用一个图的割来表达解决着些冲突的方案。

做题2

发表于 2022-07-12 更新于 2025-02-16 分类于算法竞赛

20220305

ABC242F(二项式反演的进一步理解)

题意：

给定一个 $n*m$ 的矩阵，需要放 $a$ 个白块 $b$ 个黑块，让它们互不侵犯，$n,m\leq 50$。

最开始看到这道题以为又要挑战 $\text{npc}$ 了，仔细一看互不侵犯的定义，是不能放在同一行或同一列。

思考：

很有意思的容斥题，考虑枚举白色占了多大的地盘，设 $f[i][j]$ 表示允许白色占用了 $i$ 行 $j$ 列的方案数，然后组合数容斥。我们可以设 $g[i][j]$ 为白色恰好占用 $i$ 行 $j$ 列的方案数，考虑列出二项式反演的式子。思考 $f,g$ 的关系，这是一类高维容斥问题。

结论如下： \[ g[i][j] = f[i][j] - \sum\limits_{x\leq i,y\leq j,x+y \neq i+j } \tbinom{i}{x} \times \tbinom{j}{y} \times g[x][y] \] 理解这个式子不难，就是减去恰好被占用的部分，注意容斥系数。

我们考虑能不能不用 $g$ 参与这个式子。

回想线性的二项式反演问题，我们有式子： \[ f(n) = \sum\limits_{i=n}^{m} \tbinom{i}{n} \times g(i) \Leftrightarrow g(n) = \sum\limits_{i=n}^{m} (-1)^{n-i}\times\tbinom{i}{n} \times f(i) \] 其中 $f(n)$ 表示钦定满足 $n$ 个条件的方案数。$g(n)$ 表示恰好满足 $n$ 的条件的方案数。

左边很好理解，就是钦定 $n$ 个条件满足的方案数就是从满足 $i$ 个条件的方案中选出 $n$ 个钦定满足。

右边可以稍微变换一下以便理解 \[ g(n) = f(n) - \sum\limits_{i=n+1}^{m} \tbinom{i}{n} g(i) \] 就是钦定 $i$ 个的情况减去恰好有大于 $i$ 个的情况乘上一个组合数，这和上面那个二维的很类似。

给出高位二项式反演公式： \[ g(n_1,n_2,⋯,n_m)=∑\limits_{k_i = 0}^{n_i} ∏\limits_{i=1}^{m}\tbinom{n_i}{k_i}f(k_1,k_2,⋯,k_m) \]

\[ \ \ \ \ \ \ \ \ \ \ \ \Updownarrow \]

\[ f(n_1,n_2,⋯,n_m)=∑\limits_{k_i=0}^{n_i}∏\limits_{i=1}^{m}(−1)^{n_i−k_i}\tbinom{n_i}{k_i} g(k_1,k_2,⋯,k_m) \]

第一个二维式子和第二个一维式子很类似，所以考虑推出 $f,g$ 的关系。 \[ f(n,m) = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{m} g(i,j) \times \tbinom{n}{i} \times \tbinom{m}{j} \] 组合解释是钦定 $n$ 行 $m$ 列可以被占用的方案数就是先从其中选出 $i$ 行 $j$ 列。然后计算恰好这么多被占用的方案数。因为行和列是有标号的。

直接代公式有 \[ g(n,m) = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{m} (-1)^{n-i+m-j} \tbinom{n}{i}\times \tbinom{m}{j}\times f(i,j) \] 结束。

ABC242H(初步理解 min-max 容斥)

题意：

给定 $m$ 条线段，一个长度为 $n$ 的数轴，每次随机选一条把数轴上对应位置涂黑，问全部涂黑的期望选择次数。

思考：

记 $E(i)$ 表示第 $i$ 个格子被涂黑的期望时间。记 $E(S)$ 表示集合 $S$ 全部被涂黑的期望时间，也就是所有格子中被涂黑时间的最大值，$E'(S)$ 表示集合 $S$ 中任意一个被涂黑的期望时间，即最小值。

显然 $E(S) \neq \max\limits_{i\in S} (E(i))$，因为期望只有线性性，$max,min$ 是非线性操作。

但是我们发现一件事 $\max(S) = \sum\limits_{T \subseteq S} (-1)^{|T| - 1} \min(T)$，即 $\text{min-max}$ 容斥的公式在期望意义下也成立。

而对这道题来说，计算一个集合的最小值是容易的，只需要计算出有多少个包含任意一个元素的线段就行了。

我们设 $dp[i][j][k][0/1]$ 表示考虑到第 $i$ 个位置，上一个位置为 $j$，已经包含 $k$ 条线段的方案数，集合大小为奇数或偶数的方案数，转移可以预处理 $[l,r]$ 会新增多少线段，做到 $O(1)$，事实上最后一维可以省掉，直接带系数转移就行。

20220309

haltoj128

思考：

欧拉图计数相关问题。关于无向欧拉图有一个结论，欧拉子图的个数为 $2^{m-n+c}$ 个，也就是其生成森林中非树边组成的集合个数，公式中 $c$ 代表连通块个数。

理解比较容易，考虑构造方案，任意一个非树边集合会唯一对应一种合法方案，选一条非树边则将它覆盖的树边状态反转（选变为不选，不选变为选），可以得到唯一合法方案。

这个选非树边集合的方式给这道题目带来了启发。然而这种类似异或的方式并不便于统计 $|S|^2$ 这种东西。我们考虑它的组合意义。发现其组合意义为每对边在同一子图便贡献两次，一条边在某一子图贡献一次。

一条边的情况是简单的，考虑两条边。

两条非树边是可以任选的，这一部分答案为 $k * (k-1) * 2^{k-2}$，因为已经钦定这两边要选，其它的任意选。

一条非树边和一条树边的贡献可以分两种情况，分别是树边是否受到非树边影响。不受影响答案为 $(k-cover[v]) * 2^{k-2}$，$cover[v]$ 影响这条树边的非树边条数，$k-2$ 因为钦定了选择的非树边要选，并且影响这条树边的边有一个的选择情况是不能任意，因为要让树边被选择。

如果受到非树边影响，那么答案也为 $cover[v] * 2^{k-2}$，但如果 $cover[v] = 1$，那么答案为 $2^{k-1}$。理解方式类似。

两条树边的情况，考虑影响这两条树边的边集，我们断言如果边集完全相同，那么答案为 $2^{k-1}$，否则答案为 $2^{k-2}$，边集完全相同的情况不难理解，如果不完全相同，我们在每条边特有的部分钦定一个来控制该边，所以答案为 $2^{k-2}$。如果是包含关系，先钦定里面的，再钦定外面的即可。

如果要选择树边，记得不要考虑 $cover[v] = 0$ 的边。计算 $cover$ 可以树上前缀和，对于两条非树边，需要统计边集相同的个数，这个可以异或哈希，取 $2^{63}$ 为上界，做双哈希，错误概率在本题数据规模下小于 $10^{-9}$。

haltoj132(分治NTT的思路)

思考：

假设不考虑 $'>'$，即令 $'>'$ 为无限制，那么序列会被 $'>'$ 划分为若干段，记每一段的长度为 $a$，那么答案为 \[ \dfrac{n!}{\prod a_i !} \] 我们考虑容斥，枚举一个子集表示那些位置上的 $'>'$ 强制为 $'<'$，也就是不合法的情况，然后就可以用总数减去这些不合法情况得到答案。

上面的那个 $n!$ 在做转移的时候很麻烦，先不管。

设 $dp[i]$ 表示对前 $i$ 个符号做容斥，考虑到第 $i$ 个符号后的数字的结果。

注意到这里 $dp[i] \times (i+1)!$ 也就是前缀 $s_i$ 的答案。

顺便设 $f_i$ 表示前 $i$ 个符号中 $'>'$ 的个数。

显然有 $dp[0] = 1$

我们得到以下式子： \[ dp[i] = (-1)^{f_i}\times \dfrac{1}{(i+1)!} +\sum\limits_{s_j = '>',j\in[1,i]} dp[j-1] \times (-1)^{f_{i}-f_{j}} \times\dfrac{1}{(i-j+1)}! \] 考虑如何理解这个式子。

我们枚举上一个不受限制的位置 $j$，然后乘上对应的容斥系数和计算转移系数，最后加上全部受限制的情况。

因为要优化，所以把式子小小的变一下： \[ dp[i] = (-1)^{f_i}\times \dfrac{1}{(i+1)!} +\sum\limits_{s_{j+1} = '>',j\in[0,i-1]} dp[j] \times (-1)^{f_{i}-f_{j+1}} \times\dfrac{1}{(i-j)}! \] 传说中的分治 $NTT$ 可以解决这一类 $dp$ 的优化问题，它的核心思路大概是这样的：

分治 $NTT$ 解决形如这样的问题：

假设要求的函数为 $f$，有另一个函数 $g$。

满足 $f(i) = \sum\limits_{j\ < i} f(j) \times g(i-j)$。

类似于 $\text{CDQ}$ 一样，考虑左边对右边的贡献即可，容易发现这是一个好做的卷积形式。

对于这道题来说，$-1$ 的次幂可以被拆到两边，剩下的事情有手就行。

收获

容斥原理可以解决这样一类问题，有一个全集 $S$，$|S|$ 好求，现在有若干属性 $p_i$，构成集合 $T$，需要求满足属性集合 $T$ 的元素个数。并且可以很容易求出这样一种情况的答案：限定某些属性不满足，其它属性不做要求。

20220320

HaltOJ 7

思考：

想一下小学的时候做过的奥数题，一个圆里画 $n$ 条线最多分成几部分，答案是 $n*(n+1)/2 + 1$。再考虑下平行线和多点共线的情况，发现答案只和每个交点的情况和交点个数有关。手玩一下可以发现，在逐个加入直线的情况下，部分的个数增量为此条直线和其它所有直线交点个数 $x$，再加上 $1$，注意，相同交点只算一个。

证明可以参考平面欧拉定理，此处不做赘述。

所以我们模拟这个过程，每次加入一条直线判断新增了多少交点，具体可以先暴力枚举直线，求出所有交点之后带上 $eps$ 去重。然后发现 $y$ 只和 $x$ 有关，所以只用计算一个。然后我们发现如果按照斜率为第一关键字，截距为第二关键字排序加入线段，那么 $x$ 是一个相当优美的形式 $\dfrac{j-b}{a-i}$，$a,b$ 表示当前线段的斜率和截距，$i,j$ 表示枚举的线段的斜率和截距，$i,j$ 的取值都连续，所以这个式子中，分母会取遍 $[1,i]$，分子会取遍 $[-b,B-j-1]$，正负数分开考虑，现在问题变成了问 $\dfrac{[1,x]}{[1,y]}$ 中有多少个不同的数，$A^2$ 预处理，$O(1)$ 回答即可，约定每个数在最简分数被统计。

可以莫比乌斯反演优化，这个可以很方便的转化成 $[gcd(x,y)=1]$ 的形式并整除分块计算，可以 $n\sqrt n$，但没必要。

HaltOJ8

思考

这道题出出来就展现出对直接 $dp$ 的恶意，无论那种合并方法都无法解决这个问题。我们不妨另辟蹊径，考虑字符串的另一种生成方式——插入。

具体的，我们将不同的花视为不同字符，那么我们需要生成一个字符串，相邻字符不同，每个字符个数指定。

我们发现当前的插入方式仅仅受到当前相同字符位置个数的限制，所以设 $f_i$ 表示考虑到现在，有 $i$ 个字符相同位置的方案数。

转移可以枚举当前字符划分为多少段，其中有多少段插入相同字符位置，具体每一段放几个可以通过插板法计算方案。这样的转移看上去是 $O{(10^{5}})^3$,但是如果我们将字符按个数排序后并按照 $3,1,2,4$ 的顺序插入，因为保证了有两个只有 $200$，所以复杂度为 $O(1+200^2 + 200^3 + 10^5)$ 的复杂度，最后一次转移强制要求了段数和插入相同字符位置的数量，第三次则是因为第二次转移后有效位置仅有 $200$ 个。

听说可以做到 $O(200^2 + 10^5)$ ，但显然我不会。

20220322

ARC137D

题意

给定一个序列 $a$，反复做前缀异或操作，问若干次操作后 $a_n$ 的值，询问所有 $[1,k]$ 的答案。

思考

考场上一直在考虑分析单纯的 $01$ 系数，而忽略了系数之间的内在其它联系，事实上，对于反复执行的可加前缀操作，设距离为 $d$，操作次数为 $k$，那么贡献应该为从 $(0,0)$ 走到 $(d,k-1)$ 的方案数。证明比较简单，将原点的贡献转移拆分到横坐标即可。

更严谨的证明可以使用归纳法，记贡献函数为 $f(x,y)$，$f(n,k) = f(n-1,k)+f(n,k-1)$，那么考虑其组合意义，第一项代表了前 $n-1$ 项的和，第二项则是自己在上面的步骤中的累计。

那个 $-1$ 很讨厌，先不管。

用组合数的形式表示答案，即为 $\tbinom{n+k}{n}$,对其应用卢卡斯定理求出 $\bmod2$ 的结果，发现当且仅当 $n\&k = 0$ 时有值，那么对于一个固定的 $n$ ，有值的 $k$ 一定可以描述为一个 $s$ 在二进制意义下的子集。

然后对其做一次 $\text{FMT}$ 变换即可得到结果。

注意处理被忽略的 $-1$

20220323

CF1657D

思路

先做乘法转换，这个没啥说的。然后我考虑的是根号分治，先把不在凸包上的扔掉，对于代价大于 $B$ 的，枚举选的个数，然后尺取法搞定，对于代价小于 $B$ 的，直接计算。场上过了，赛后被叉。实际上，对于这种整除的题目，我们都可以考虑枚举倍数约数，然后可以直接计算代价为 $[1,C]$ 的最大权值，然后直接在上面二分就行。

CF1647E

思路

不难发现充要条件是每个点向 $1$ 的边为最小值。然后考虑 $dp$，直接对点 $dp$ 不太好做，我们发现它是有关大小的，所以考虑按照向 $1$ 的边权值从小到大 $dp$，每次枚举一段连续的区间，以及填的值转移，转移是一个前缀和乘上一个组合数再乘上一个幂次。

CF1647F

思路：

看上去就非常暴力，对每个限制建点，两种状态，限制和树上的点的状态推出关系连边，然后暴力确定每个限制的状态看是否冲突即可。实际上这就是模拟了 $\text{2-SAT}$。

考虑这个东西为什么和 $\text{2-SAT}$ 的正常做法一样的，正常做法是找强连通分量，拓扑排序后对每个点选拓扑序大那个值。和我们的暴力模拟过程没啥区别。

HaltOJ126(2-SAT 的简单理解)

思考：

有一些比较奇怪的限制，然后每个人在每个点就两种状态，要想起一个东西叫 $\text{2-SAT}$，我们令 $statu[i][j]$ 表示 $i$ 子树内是否有 $j$，那么很容易构造出标准的 $\text{2-SAT}$ 限制，然后我们考虑约束，分类讨论一下。以 $\text{2-SAT}$ 的形式来说，对于 $x$ 的每个儿子 $v$，两个点都不能同时在 $v$ 中。同时，如果 $lca(x,r) \neq x$ ，那么两个人都必须在 $x$ 子树内。如果 $lca(x,r) = x$，那么 $a,b$ 只能有一个在子树外，就是一个为假那么另一个为真，除此以外，如果 $x \neq r$，那么 $a,b$ 不能在 $x$ 向 $r$ 的儿子里。

然后跑一个标准的 $\text{2-SAT}$。

$\text{Tarjan}$ 跑出来的 $\text{SCC}$ 编号是反拓扑序。

$\text{2-SAT}$ 的一些限制：强制 $u$ 为真，那么把假连向真，反之亦然。其它情况下注意逆否命题也要连边

$\text{2-SAT}$ 图的一些性质：$u \rightarrow v \Rightarrow \overline{v} \rightarrow \overline{u}$

$\text{2-SAT}$ 合法性：同一变量的两个状态不在同一 $\text{SCC}$ 内是存在方案的充要条件，必要性显然，充分性用构造法证明。

$\text{2-SAT}$ 方案构造：依次考虑每个变量，选择 $\text{SCC}$ 编号较小那个值，那么同一变量不会直接冲突，假设先前的点 $v$ 推出了 $\overline{u}$，并且 $\overline{u} \rightarrow u$，因为刚刚提到的性质，一定有 $u\rightarrow \overline{v}$，我们一定会选拓扑序较大的 $\overline{v}$，因此选择不会冲突。

20220325

CF1656D

题意：

您有一个 $n$，您需要找一个 $k \in[2,\infty)$，使得 $n$ 可以被表示为 $k$ 个模 $k$ 意义下不同的数，多解可以输出任意一个。
多测 $T\leq 10^5,n\leq10^{18}$

思考：

因为要找的 $k$ 个数模 $k$ 意义下不同，我们又知道任意一个数 $a$ 都可以表示为 $a=b \times k +r$，所以不妨先把模 $k$ 的余数和，也就是上式中的 $r$ 提取出来，我们得到了一个新的式子。下面设 $n$ 为 $k$ 个数的和。 \[ n = c\times k + \dfrac{k\times(k+1)}{2} \] 其中 $c$ 表示这 $k$ 个数对应 $b$ 的和。分母让人很不爽，所以乘过去。至于为什么是 $(k+1)\times k$，是为了让 $c$ 可以取到 $[0,\infty)$ \[ 2n = (2c+k+1)\times k \] $2n$ 的两个因子奇偶性不同，所以如果我们的 $n$ 为奇数就可以直接令 $k=2$，否则我们每次令 $k$ 取 $2,4,8,\cdots$,直到 $\dfrac{2n}{k}$ 为奇数为止，这个时候记 $res = \dfrac{2n}{k}$，如果 $res$ 较大，则取对应的 $k$，否则取 $k=res$。

注意特判掉一些边界情况，比如 $2$ 的次幂，$2$ 的次幂，还有 $2$ 的次幂。

参考代码

#include<bits/stdc++.h>
#define INF 1000000000
#define int long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type>void cmin(_type &a,_type b){a=min(a,b);}
template<typename _type>void cmax(_type &a,_type b){a=max(a,b);}
int i,j,k,n,s,t,m;
signed main()
{
	read(t);
	while(t--){
		read(n);int ans=-1;
		for(i=2;i<1ll<<62;i*=2){
			int res=2*n/i;
			if(res%2){
				if(res>i){
					ans=i;
					break;	
				}
				else{
					ans=res;
					break;
				}
			}
		}
		if(ans==1)puts("-1");
		else printf("%lld\n",ans);
	} 
	return 0;
}

CF1656E

题意

您有一棵 $n$ 个点的无向无根树，您需要为每个点安排一个权值 $a_i\in[-10^5,10^5]$，使得删掉任意一个点之后剩下连通块的权值和相同，注意安排的权值不能为 $0$。
多测 $T\leq 10^4,\sum n \leq 10^5$

思考

诈骗题。我们考虑指定一个根，就让它是 $1$，然后随便删一个点 $u$，那么 $u$ 的所有儿子的子树都必须有同一个值，我们可以尝试安排每一棵子树的权值和，这是可以做到的，因为可以让根控制这个值。不妨安排每颗子树的权值和为 $1$，那么我们再安排整个树的权值和为 $2$，就可以让删掉每个点 $u$ 后剩下的连通块权值和相同。$u$ 的所有儿子子树的权值和都为 $1$，而除开 $u$ 的子树后的那个连通块的权值和就是整棵树的权值和 $2$，减去 $u$ 子树的权值和，就是 $1$，也和 $u$ 所有儿子的子树的权值和相同。

但是有一个问题，如果一个点 $u$ 只有一个儿子，那么 $u$ 的权值会被安排为 $0$，是不合法的，所以我们需要更改一下安排的方式，对于一个点，设它子树的权值和为 $x$，并且它所有儿子的子树的权值和均为 $y$，而且整棵树的权值和为 $x+y$。这是合法的必要条件，因为我们需要让 $a_i \neq0$，所以安排根的权值为 $0$，其它点按深度模 $2$，的值安排 $-1$ 和 $1$ 即可。

代码

#include<bits/stdc++.h>
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type>void cmin(_type &a,_type b){a=min(a,b);}
template<typename _type>void cmax(_type &a,_type b){a=max(a,b);}
const int N=1e6+10;
int i,j,k,n,s,t,m;
vector<int> e[N];
int val[N],fa[N],dep[N],deg[N],tar[N];
void dfs(int u){
	if(u==s)tar[u]=val[u]=0;
	else tar[u]=val[u]=dep[u]%2?1:-1;
	for(int v:e[u]){
		if(fa[u]==v)continue;
		dep[v]=dep[u]+1,fa[v]=u;dfs(v);val[u]-=tar[v];
	}
}
signed main()
{
	read(t);
	while(t--){
		read(n);dep[1]=1;s=1;
		for(i=1;i<=n;i++)e[i].clear(),val[i]=0,tar[i]=deg[i]=0,fa[i]=0;
		for(i=1;i<n;i++){
			int x,y;read(x),read(y);
			e[x].push_back(y),e[y].push_back(x);
			deg[x]++,deg[y]++;
		}
		for(i=1;i<=n;i++)if(deg[i]>deg[s])s=i;
		dfs(s);
		for(i=1;i<=n;i++)printf("%d ",val[i]);
		puts("");
		
	} 
	return 0;
}

CF1656F

题意

您有 $n$ 个点，每个点有一个权值 $a_i$，定义一张有权无向完全图 $K(t)$ 为每个点 $i$ 向 $j$ 连一条权值为 $a_i\times a_j+(a_i+a_j)\times t$ 的无向边后所构成的图，定义 $f(t)$ 为 $K(t)$ 最小生成树的权值和。您需要对所有的实数 $t$ 求出 $f(t)$ 的最大值并输出它，如果最大值不收敛，那么输出 INF。
多测，$T\leq 10^4,\sum n\leq 2\times 10^5,-10^6\leq a_i\leq 10^6$

思考

~~场上差那么一点点就 15Ton 了~~

一个瓶颈在排序的线性做法。

记 $d_i$ 表示点 $i$ 的度数。

判断 $\text{INF}$ 是简单的，只需要看能不能凑出 $\sum a_i\times d_i$ 分别为正和负或者 $0$ 就行，如果凑不出来，令 $t$ 为正无穷或者负无穷，然后它就不收敛了。

现在已知有解。

考虑固定一个 $t$ 后怎么快速求 $\text{MST}$。做个恒等变形，权值为 $(a_i+t)\times (a_j+t)-t^2$，把 $t^2$ 给扔掉。

结论是排序后按正负性断开，$a_1$ 向所有 $a_i$ 大于 $0$ 的连边， $a_n$ 向所有 $a_i$ 小于 $0$ 的连边，$0$ 无所谓。

证明可以考虑 Prime 算法的过程，最开始一定是 $a_1$ 到 $a_n$。然后后面不会取到正负性相同的，并且一个点一定是连向 $a_1$ 或者 $a_n$。

如果处理一个前缀和，知道正负交界的位置之后可以快速算，从小到大枚举 $t$，然后双指针维护交界处。

可以证明 $t$ 一定取到每个 $-a_i$。如果夹在两坨中间，那么由于具体选哪些边是固定的，根据 $\sum a_i\times d_i$ 正负性调整即可。

不会取到 $[a_1,a_n]$ 外面去，因为我们已经判了无解，所以取到边界外面时 $\sum a_i\times d_i$ 的正负性会导致向里面调整更优。

20220329

HaltOJ129(Powerful Number 筛)

思考:

打个表发现 $f$ 是积性函数。

然后 $f(p^c)$ 是好求的，考虑亚线性筛法。

我也不知道为啥会想到 PN 筛，总之这种东西各种筛法都可以尝试一下。

PN 筛和其它亚线性筛法一样，是用来求一些积性函数的前缀和的，它的关键在于构造一个好求的前缀和的 $g$，满足 $g(p)=f(p)$，然后构造一个 $h$ ，满足 $f=h * g$，乘法为迪利克雷卷积。

这里我们构造 $g(x)=1$

积性函数有个性质，$f(1)=1$，所以展开下 $f$，发现 $f(p)=1=h(1) * g(p)+h(p) * g(1)$，然后 $h(p)=0$，由于 $h$ 也是个积性函数（迪利克雷卷积的性质），所以 $h$ 只会在 PN 处有取值，PN 的定义为每个质因子次数都大于等于 $2$ 的数。

可以证明所有比 $n$ 小的 PN 个数是 $O(\sqrt n)$ 的。

可以预处理 $\sqrt n$ 以内的所有质数，然后枚举指数得到每个 PN，这个 $dfs$ 的过程中可以记录一下对应的 $h$，$h$ 的转移是好做的，因为只需要求 $h(p^c)$。

这里不难发现 $h(p^c)=f(p^c)-f(p^{c-1})$。

原因是 $g$ 实际上是 $1$，而 $f / 1 = f * \mu$

20220331

20220330考试T2

思考

限制不好弄，考虑转化限制，不难发现，如果建图，并依次加入有向边，那么任意一个时刻，都需要满足当前图及其补图都是一个传递闭包，即，如果能间接 $a\rightarrow b$ ，那么 $a,b$ 有边。这样的图不是很多，是 $n!$ 个的，只需要考虑图之间的转移就行。

这样的图和一个 $n$ 的排列一一对应，构造方案为如果 $a,b$ 为逆序对，那么加入一条边 $(a,b)$。加入一条边时，只需要枚举相邻的逆序对并交换，转移可以康托展开得到交换后的编号。限制也比较好做，转移的时候看看强制在前面的边在不在里面就行。

复杂度为 $O(n!\times n \times (n+m))$，常数较小，可以过。

20220402

20220401考试T1

思考

对于这种翻转的博弈问题，其实都可以做一个转化：不要翻转颜色，而是在每个翻转的地方再放一个棋子，这样不会改变游戏的胜负性，因为如果原处没有棋子，那么等效，如果有棋子，那么有两个，在 $SG$ 的意义下，这是可以抵消的。如果以组合方式理解，那么因为放了之后如果有人操作了，那么另一个人把它的操作复制一遍即可，由于两个人都是最优操作，所以可以抵消。

有了这个转化，每个棋子都变成了一个独立的游戏，该局面的 $SG$ 值就不难计算了，按照定义计算出每个位置的 $SG$ 值然后异或查表即可。

20220401考试T3

思考

场上写了个 $O(n^3)$ 卡常卡过去了，实际上 $O(n^2)$ 的有点难想，它是把构造表达式的过程视作了一个添加左右括号的过程，总之非常神仙。

有个对于区间 $dp$ 的常数优化思路，可以改变一下枚举顺序，让数组访问尽量连续，以便最大程度利用好 $L1$，可以节省大量内存操作时间。

咕一篇常数优化文章。

做题1

发表于 2022-07-12 更新于 2025-02-16 分类于算法竞赛

2022.2.7

CF1634E

题意：

给定一些数组，长度都为偶数，需要将每个数组的元素划分到两个可重集合里，要求两个集合相同，问方案或输出无解，$n,m=10^5$。

思考：

考虑每个数组单独划分，不太行，所以不能一个数组一个数组的考虑，显然有解的必要条件是每个数字个数为偶数。所以一个数字一个数字的考虑，其实也不太行，因为这和刚刚那种方法是本质上一样的。

注意到也保证每个数组长度为偶数~~（这不是废话吗）~~，都是偶数，不由得让我们想到欧拉回路，所以尝试建图，每个不同的数和数组视为一个点，由数组向数连边，数组内存在一个数，就由数组向这个数连一条边，现在需要给图定向为一张欧拉图，我们将数组向数连的边是为将这个数分到第一个集合，反之则为第二个，构造欧拉图即可。

实现上的问题：

存边用 set 存，不然 TLE 没商量。

图不一定联通，所以一定要多起点。

20220209

22020208考试 T1

题意：

定义矩阵 $Mat_n$

$n = 0$ 时，为一个 $1$
$n > 0$ 时，左上角为 $0$ 矩阵，其余部分为三个 $Mat_{n-1}$。

在一个平面上画出两个 $Mat_n$，左下角分别为 $(0,0),(x,y)$，求都为 $1$ 的位置有多少个。

思考：

考虑旋转矩阵转化为位运算计数问题，转化为求整数对 $(i,j)$ 满足 (i&j) == 0 and ((i+x)&(j-y)) == 0

考场上看到要高精就润了，没有认真思考。

实际上可以考虑类似数位dp 的算法，也不难。

22020208考试 T2(后缀自动机复习)

题意：

给定一个字符串 $s$ ，$q$ 次询问 $l,r$，表示所有 $[l,r]$ 开头的子串中本质不同的子串个数。

$n,q = 2 \times 10^5$

思考1：

考虑后缀自动机求本质不同子串个数的方式，发现它可以在线完成。

所以反着建后缀自动机。

对于 $r=n$ 的部分分，显然先离线，可以建后缀自动机时统计下每一个结尾的答案，输出即可。

如果 $r \neq n$，那么不妨仍然考虑在后缀自动机上如何统计答案。

后缀自动机本质上维护的是 $endpos$ 集合，对于一个询问，如果一个 $endpos$ 集合中包含一个位置 $x\in[l,r]$，那么这个 $endpos$ 集合所代表的子串应该被计入贡献。

后缀自动机上每个子串仅在一个 $endpos$ 集合中出现，所以可以求出至少有一个元素被包含的集合，并直接加和。

考虑对于每个询问该如何统计答案，限制一共有两个 $l,r$，并不好做，然而我们发现后缀自动机是在线构建的，所以如果将询问离线，那么限制就只剩下一个 $r$ 了。我们在构建后缀自动机的同时只需要记录每个 $endpos$ 集合最小的元素 $val$，查询时查询所有满足 $val \leq r$ 的集合的子串数量和即可。考虑维护一个数组 $c$，$c[i]$ 表示 $val = i$ 的 $endpos$ 集合子串个数和，用 $BIT$ 查前缀和，现在只剩下修改了。

考虑 $endpos$ 树的性质，发现修改操作是把一段到根的路径赋值，同时还有修改父亲等操作，于是考虑动态树，我们不难发现一段实链上的集合，$val$ 都是相同的，所以在每个节点维护一下 $val,sum$ 值即可，注意 $push\_down$ 操作时需要把赋值也 $push\_down$ 下去。

这样做未免显得有些麻烦，我们考虑最终构建的后缀自动机，倒序激活 $endpos$ 中每一个点，这样就不需要 $Link$ 和 $Cut$ 操作，只需要写 $access$ 就行。

实际上未必需要用后缀树来实现，通过激活点的方式，树已经时静态的了，这本质上还是一个区间染色问题，我们完全可以直接重链剖分，在每条重链上开个栈维护断点，记录下前缀和。

复杂度都是 $O(nlog_n^2)$，个人认为类似动态树的方法会好写一些。

思考2：

考虑使用后缀数组，回想后缀数组统计不同子串个数的方式，实际上就是排序后减掉相邻两个的 $lcp$，于是对原串后缀排序，然后离线询问莫队，拿个 set 维护当前所有串的排名集合，再来个 $ST$ 表计算 $lcp$，插入和删除都很好写，复杂度 $O(n\sqrt n \ log_n)$，难以通过本题。

考虑优化，有一个技巧，这种需要查前驱后继的东西，实际上可以用链表搞，加入相对困难一些，因为我们不知道到底应该放在哪里，但删除就很容易了，双向链表上直接删就完事了，所以可以回滚莫队，非常无脑，时间复杂度 $O(n\sqrt n)$。

稍加卡常即可通过，$ST$ 表查询常数相对较大，卡常应考虑尽量减少查询次数。

20220210

20220208考试T3

恶心的题意

思考

发现由于编号连续，所以最后经过的一定是一段连续区间。想到可以枚举右端点，二分左端点。

一个区域到另一个区域的路径可以分为区域到中转站和中转站到中转站两部分，区域到中转站的情况可以只计算到左右两边最近的中转站，所以容易计算。

我们按照右端点顺序激活中转站，问题就是要最小化左端点。

两个中转站只能通过同一条线连接，把最低点也看成中转站，所以可以认为从一个中转站到另一个的代价为两者所在区域编号的较小值。

中转站到中转站的距离可以 Floyd 暴力，我们就已经计算出了每对中转站点相互抵达的代价，所以二分都不需要了，我们可以直接用这个代价计算出最终答案。

实现细节

Floyd 的时候，因为加入的中转站并不是按下标顺序，所以需要整个跑一遍。

20220211

20220211 测试 T1

题意

思考

这道题算是考场上想出来的，考场上摸了一会儿鱼，发现有个地方假了的时候只剩 $5min$ 了，所以紧急修复成了$50pts$，实际上不管直接交有 $80pts$。

先把最上面那些没有的行删掉。

考虑每一行的可能性，只有穿过和不穿过两种，穿过又可以分为去的时候穿过和回的时候穿过。

来的时候穿过，回的时候一定不会穿过，因为一定不优，于是三进制枚举穿过状态，大的路径框架已经被构建出来了，现在要考虑经过那些没有穿过的点。

被穿过的行不用管，现在就剩没穿过的行，每一行可以从左到右，也可以从右到左，如果两边都有经过，还可以两面包夹，算出每一行的结果，然后加上去就行。

这样可以拿到 $80pts$，因为它处理不了这种情况。

3 7
#.....#
.#####.
.#####.

它会穿过第一行和第二行，到第三行后穿过或者是走到底再回来，实际上在穿过第一行走到第二行的时候就应该上去拿掉右上角。

所以把大的路径画出来后，记录每一个边缘位置是否到达过，还要自下而上 $dp$ 一遍求出经过所有未经过的点的最小代价。

提供一种思路，设 $dp[i][j][k]$ 表示到第 $i$ 行，左右最前面的可以已经经过的点为 $j,k$ 的最小代价，转移的时候看 $j,k$ 是否大于 $i$ 或者 $i$ 的两端是否已经经过，如果可行，就选经过一行三种方案的最小值，如果不行，因为一定有一边已经经过，所以只考虑另一边是否补全和从经过的点走一遍再回来的情况，补全的方案有两种，从上面和从下面，直接转移即可。

时间复杂度 $O(n^3 * 3^n)$，实际上剪枝后跑的飞快，$10ms$ 就跑完了。

20220212

20220212测试T2

题意

思考:

考虑直接 $dp$ 转移，设 $dp[i][j][k][0/1]$ 表示考虑前 $i$ 个数，正色子已经用了 $j$ 个，反色子已经用了 $k$ 个，是否已经赢了的方案数，直接转移是 $O(n^4 * t)$ 的，可以拿到 $20pts$ 的好成绩。

考虑优化，转移式子是：

for(int i1=0;i1<=n;i1++)
for(int i2=0;i2<=m;i2++)
for(int j1=0;j1<=i1;j1++)
for(int j2=0;j2<=i2;j2++)
{
    if(i<=t&&i1-j1>i2-j2)
    Inc(dp[i][i1][i2][1],1ll*dp[i-1][j1][j2][0]*C[n-j1][i1-j1]%mod*C[m-j2][i2-j2]%mod);
    else 
    Inc(dp[i][i1][i2][0],1ll*dp[i-1][j1][j2][0]*C[n-j1][i1-j1]%mod*C[m-j2][i2-j2]%mod);
    
    Inc(dp[i][i1][i2][1],1ll*dp[i-1][j1][j2][1]*C[n-j1][i1-j1]%mod*C[m-j2][i2-j2]%mod);
}

转移目标

dp[i][i1][i2][1]

前面一部分

1ll*dp[i-1][j1][j2][0]*C[n-j1][i1-j1]

和后面一部分

C[m-j2][i2-j2]

只有前一部分依赖 $j1$，考虑能不能预处理前一部分的转移，然后优化一个 $n$

显然是可以的，手推一下式子可以得到一个新的转移。

for(int j1=0;j1<=n;j1++)
for(int i2=0;i2<=m;i2++)
{
	sum[j1][i2]=1ll*dp[i-1][j1][0][1]*C[m][i2]%mod;
	sum2[j1][i2][0]=1ll*dp[i-1][j1][0][0]*C[m][i2]%mod;
	for(int j2=1;j2<=i2;j2++)
	{
		if(dp[i-1][j1][j2][1])
        Inc(sum[j1][i2],1ll*dp[i-1][j1][j2][1]*C[m-j2][i2-j2]%mod);
		sum2[j1][i2][j2]=sum2[j1][i2][j2-1];
		if(dp[i-1][j1][j2][0])
        Inc(sum2[j1][i2][j2],1ll*dp[i-1][j1][j2][0]*C[m-j2][i2-j2]%mod);
	}
}
for(int i1=0;i1<=n;i1++)
for(int i2=0;i2<=m;i2++)
for(int j1=0;j1<=i1;j1++)
{
	int val=C[n-j1][i1-j1];
	Inc(dp[i][i1][i2][1],1ll*val*sum[j1][i2]%mod);
	if(i<=t)
	{
		int pos=i2+j1-i1,val1=pos<0?0:sum2[j1][i2][pos],val2;
		val2=sum2[j1][i2][i2];Dec(val2,val1);
		if(i<t)Inc(dp[i][i1][i2][0],1ll*val*val1%mod);
		Inc(dp[i][i1][i2][1],1ll*val*val2%mod);
	}
}

优化到了 $O(n^3*t)$，记此时的常数 $k = 1$，它需要约 $15s$ 通过数据规模最大的测试点。

这份代码可以拿到 $50pts$ 的好成绩，感觉上已经不太能优化复杂度了，我们考虑卡常。

第一步，发现 $n=6$ 的时候只需要转移 $dp[6][n][m][1]$

第二步，发现 $n=1$ 的时候被转移的只有 $dp[0][0][0][0]$

常数变为 $k = \dfrac{2}{3}$

此时可以拿到 $70pts$ 的好成绩。

继续考虑卡常。

发现其实在 $i>=t$ 时转移 $dp[i][i1][i2][0]$ 没有意义，直接剪掉。常数没有变化。

发现 $dp[i][i1][i2][1]$ 实际上可以由 $dp[i][i1][i2][0]$ 直接得到，所以只转移 $dp[i][i1][i2][0]$ ，记作 $dp[i][i1][i2]$，常数变为 $k = \dfrac{1}{3}$

if(i<=t)
{
    for(int j1=0;j1<=n;j1++)
        for(int i2=i==6?m:0;i2<=m;i2++)
        {
            sum[j1][i2][0]=1ll*dp[i-1][j1][0]*C[m][i2]%mod;
            int *p=&sum[j1][i2][1];
            for(int j2=1;j2<=i2;j2++)
            {
                *p=sum[j1][i2][j2-1];
                Inc(*p++,1ll*dp[i-1][j1][j2]*C[m-j2][i2-j2]%mod);
            }
        }
    for(int i1=i==6?n:0;i1<=n;i1++)
        for(int j1=0;j1<=i1;j1++)
            for(int i2=i==6?m:max(0,i1-j1);i2<=m;i2++)
                Inc(dp[i][i1][i2],1ll*C[n-j1][i1-j1]*sum[j1][i2][i2+j1-i1]%mod);
}
else
{
    for(int i2=i==6?m:0;i2<=m;i2++)
    {
        for(int j1=0;j1<=n;j1++)
            sum[j1][i2][0]=1ll*dp[i-1][j1][0]*C[m][i2]%mod;
        for(int j2=1;j2<=i2;j2++)
            for(int j1=0;j1<=n;j1++)
                Inc(sum[j1][i2][0],1ll*dp[i-1][j1][j2]*C[m-j2][i2-j2]%mod);
    }
    for(int i1=i==6?n:0;i1<=n;i1++)
        for(int i2=i==6?m:0;i2<=m;i2++)
            for(int j1=0;j1<=i1;j1++)
                Inc(dp[i][i1][i2],1ll*sum[j1][i2][0]*C[n-j1][i1-j1]%mod);
}

此时的成绩还是 $70pts$，但我们可以观察一下代码，在 $i>t$ 后的转移实际上没有任何意义，可以直接计算，优化这一部分，可以拿到 $90pts$ 的好成绩。

for(i=2;i<=min(t,5);i++)
{
    for(int j1=0;j1<=n;j1++)
        for(int i2=0;i2<=m;i2++)
        {
            sum[j1][i2][0]=1ll*dp[i-1][j1][0]%mod*C[m][i2]%mod;
            int *p=&sum[j1][i2][1];
            for(int j2=1;j2<=i2;j2++)
            {
                if(dp[i-1][j1][j2]>=mod)dp[i-1][j1][j2]%=mod;
                *p=sum[j1][i2][j2-1];
                Inc(*p++,1ll*dp[i-1][j1][j2]*C[m-j2][i2-j2]%mod);
            }
        }
    for(int i1=0;i1<=n;i1++)
        for(int j1=0;j1<=i1;j1++)
            for(int i2=max(0,i1-j1);i2<=m;i2++)
            {
                dp[i][i1][i2]+=1ll*C[n-j1][i1-j1]*sum[j1][i2][i2+j1-i1];
                if(dp[i][i1][i2]>=8e18)dp[i][i1][i2]%=mod;
            }
}
if(t==6)
{
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            Inc(dp[6][n][m],(n-i<=m-j)*dp[5][i][j]%mod);

    printf("%lld\n",((quick(6,n+m)-dp[6][n][m]%mod)+mod)%mod);
}
else
{
    int all=0;
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            Inc(all,1ll*dp[t][i][j]%mod*quick(6-t,n+m-i-j)%mod);

    printf("%d\n",((quick(6,n+m)-all)+mod)%mod);
}

最后的 $10pts$ 可能需要一些卡常技巧。

我们发现实际上复杂度的瓶颈在数组寻址和取模，考虑优化其中之一，被寻址的数组经过循环变量的调整已经相当连续了，我们考虑优化取模。

用 long long 存 $dp$，每 $8$ 次加法取一次模，可以通过本题。

一个很常见的，在取模运算较多时的优化技巧。

20220211 测试T3

题意

思考：

这道题暴力思路无非就二进制枚举和容斥。正解的做法很神仙。

在这种 $\text{NP}$ 问题中，我们完全可以考虑将枚举的部分减少，这道题的思路是对稀疏图删点变为森林，然后二进制枚举一些删掉的点的状况再进行树形 $dp$，着实是一个很有启发性的思路。

20220212

CF1637F

思考:

对于这种条件为最小值的覆盖问题，我们不妨考虑最大的那个点是如何被覆盖的，首先有一个结论是只会在叶子有基站，证明简单，略去。然后考虑最大的那个点是如何被覆盖的，把它看作根，一定来源于它不同儿子的两个叶子，所以我们考虑其它点的时候一定可以认为这个根上的值为 $\text{INF}$ ，理由不多说了。所以每个点 $u$ 的包含的叶子至少有一个最大值为 $h_u$，贪心即可，最后决策最大值的点应该放在哪里，同样的贪心。

实现较为简单，没什么说的。

20220225

haltoj116

思考：

考虑团和独立集的性质，我在考场上就想到了答案一定不多，极大概率无需取模这一特性，于是用类似分治的方式得到了 $60pts$，如果我们找出了一个合法解，那么其它合法解的构造也是简单的，考虑合法解的性质，不妨设团的大小为 $s$ ，那么因为独立集只能向团连边，所以独立集中的点最大度数为 $s$，而这样又导致了团中的点最小度数增加，所以我们不难发现团中的点一定是度数最大的那一段前缀。

对于度数相同的点，看似无法下手，但是我们知道边的构成是团内加上团和独立集之间，团内的边数我们是知道的，而如果记录一下团中点的总度数，我们可以很轻松的推出独立集间是否有边，我们设团内点的总度数为 $p$,团的大小为 $i$，团内边数为，那么其他点之间的边数就为 $(2*m-2*p+i*(i-1))/2$，所以我们考虑满足 $2m + i * (i-1) = 2p$ 这个条件的选择有什么性质，因为这是成立的必要条件，考虑证明这也是充分条件。如果团内边数不足 $i*(i-1)$，那么我们发现 $p$ 这边会减小。考虑如果独立集内边数有边，那么 $p$ 这边一样相对减少，所以这也是充分条件。

这道题结束了。

haltoj117:

思考：

考虑在原序列中是前缀 $max$ 的点，它们在新划分的序列中一定也是前缀 $max$，如果新增了前缀 $max$，那么我们可以很轻松的改变划分情况去除这个前缀 $max$，所以如果原序列中前缀 $max$ 的数量为偶数，就一定可以。如果为奇数，我们不妨考虑只有一个序列有新增的前缀 $max$ 的情况。我们考虑从原序列中抽出一个新序列出来，设两个序列的权值之差为 $k$，如果抽了一个原先的前缀 $max$，那么 $k$ 减少 $2$，如果新增了一个前缀 $max$，$k$ 减少量为 $1$，所以我们将原先是前缀 $max$ 的数的权值视为 $2$，其余的视为 $1$，问题就是是要选一个上升子序列，使得权值和为前缀 $max$ 的个数，这个问题就相当简单了。

20220228

ABC215H(子集容斥的另一种思路)

考虑霍尔定律，枚举不满足条件的子集 $mask$，可以用 $\text{FMT-DP}$ 计算出必须由 $mask$ 供给的白菜数量，考虑减少一个子集中的白菜使得不满足条件，就可以计算出最少需要吃多少个。问题变成了统计答案，我们发现对于一个 $mask$ 直接组合数计算然后相加会算重，又因为答案不是全集所以并不能简单容斥。而暴力计算强制每种白菜都选一个的复杂度是 $O(3^n)$ 的，我们仍然考虑应用 $\text{FMT-DP}$ 计算答案。事实上，这种组合数问题都可以考虑这种方式。

设 $f_{mask}$ 表示所选白菜集合被 $mask$ 包含的方案数，设 $f'_{mask}$ 表示所选白菜种类集合恰好为 $mask$ 的方案数，列有等式。 \[ f'_{mask} = f_{mask} - \sum\limits_{x \sub mask} f'_{mask} \] 令 $f[i][mask]$ 表示当前子集为 $mask$ ，低 $i$ 位不一定存在，但高位都严格符合要求的方案总数，列有

for(i=n-1;i>=0;i--)
    for(int mask=0;mask<1<<n;mask++){
        f[i][mask]=f[i+1][mask];
        if(1<<i&mask)f[i][mask]-=f[i+1][mask^(1<<i)],f[i][mask]%=mod;	
	}

从 $i+1$ 推到 $i$ 的过程中，因为高位已经强制存在了，所以我们减去的就是 $f[i][mask]$ 中所有不存在第 $i$ 位，但高位符合要求的情况。

最后计算出来的 $f[0]$ 就是上述的 $f$。

然后这道题就好做了。

20220301

考试 T1(SAM的进一步理解)

题意：

给定一颗字符在点上的 $\text{Trie}$，求 $\text{Trie}$ 代表的所有字符串本质不同子串个数，顺便询问钦定字符大小关系后第 $k$ 小的子串，保证 $\text{Trie}$ 上字符随机且答案长度和不超过 $800KB$。

思考：

考场上想到可以类似 $\text{SAM}$ 一样乱搞，然后就写了 $\text{dfs}$ 构建 $\text{SAM}$，$lst$ 指针被置为它父亲插入后的 $p$，这个做法在数据随机的情况下是没有问题的，但是如果出现构造数据，它会没掉。

首先是如果拉一条 $a$ 链，链上每个点再挂一个 $b$，然后 $dfs$ 回跳的时候重置 $q$ 的来边到 $np$ 时时间复杂度是 $O(n^2)$ 的。

我所理解的 $\text{SAM}$ 时间复杂度正确性基于两个东西，一个是 $p$ 的深度变化情况，这证明了第一次构建边的时候时间正确。在 $dfs$ 构建 $SAM$ 的时候，大量回溯操作会导致 $p$ 深度的异常变化，这样就不对了。第二个是重置 $q$ 的来边的循环，这个可以分析 $p$ 的 $fa$ 所代表最短字符串长度来理解，每次重置 $q$ 的来边，我们都认为是找到了一个更短的 $np$ 所代表的字符串，不妨看成一个指针在插入的字符串上移动，它只会向右。重置完 $p$ 的来边再插入下个点的过程中，我们至少会跳到 $np$ 处（只针对单个串），然后重设的 $p'$ 的 $fa$ 的最短长度一定可以从 $np$ 那里继承过来，所以指针只会右移。$dfs$ 加入时同样导致了这个指针在 $\text{Trie}$ 上乱跳，复杂度就没有了保证。

然后是正确性相关的问题，这种 $\text{SAM}$ 写法会导致无效的空节点建立，比如说插入的时候就碰到了满足 $a[lst].ch[c]$ 存在的情况，这样新建出来的点实际上是无效的，在绝大部分题目中这个无效点是不影响答案的，但是少部分写法会导致爆炸。

接下来讨论下 $\text{BFS}$ 建树的正确性。由于是按深度加点，所以 $a[lst].ch[c]$ 一定是不存在的，因此绝不会导致无效节点的建立，时间复杂度证明不会，省略。

时间复杂度我并不会证明 emmmm.

ABC241H

思考：

生成函数套路题。

20220302

ARC136E

思考：

显然偶数链是很好走的，所以考虑从偶数边怎么到另一个节点，显然偶数只能选一个，我们先考虑不选偶数的情况。

定义 $f[x]$ 为 $x$ 的最小质因数，$x$ 能走到 $y$ 的充要条件是 $y>x,x+f[x]\leq y-f[y]$，如果 $(x,y) = 1$，那么显然，因为 $x$ 第一步至少走 $f[x]$，到 $y$ 的最后一步至少走 $f[y]$。如果 $(x,y) \neq 1$，设 $x = p \times f[x]$，则 $y$ 至少为 $(p+2)\times f[x]$，故结论仍然成立。

由此可以 $x$ 走不到 $y(y>x)$ 的充要条件为 $x+f[x]>y-f[y]$，将每个点视为 $(x-f[x],x+f[x]])$ ，题目就是要求出一些区间的集合，使得所有区间有公共点，要求权值最大，不妨枚举公共点，然后差分计算即可。

考虑下偶数，实际上做法类似。

20220303

AGC027E&&haltoj119

思考：

观察不变量是这种变换题的思考方向之一，我们设 $a$ 的权值为 $1$ ，$b$ 的权值为 $2$，总能发现权值和对 $3$ 取模的结果不变。

先考虑一个字符串在什么情况下可以变成另一个字符串，权值相同显然是必要条件，其次，源串 $s$ 不能是交替串 $abababa$ 这类，这有点困难，不妨先考虑变成一个字母的情况。

充要条件为权值相同且不交替，证明考虑归纳法。

现在考虑目标为一个字符串的情况。我们先贪心的匹配，用最少的字母构造出目标串，然后考虑调整剩下的部分使得它满足条件。如果特判掉交替串，我们发现只要权值相同且源串的一个前缀能和目标串贪心匹配上，那么一定可以变成目标串，于是考虑 $dp[i]$ 表示考虑到前 $i$ 的源串字母，能贪心的对应上多少不同串，显然这样的贪心对应是不重不漏的，转移分为匹配 $i+1$ 和不匹配 $i+1$ 两种，预处理一个类似 $nxt$ 的东西可以做到线性。

20220304

CF917D&&haltoj122(初探二项式反演)

思考：

考场上已经观察出原题需要求一张完全图有多少棵最小生成树与给定树至少有 $n-k-1$ 条边相同。$prufer$ 序列有一个结论，$n$ 个点 $k$ 个连通块的图构成有标号无根树的方案总数为 \[ n^{k-2}\times\prod_{i=1}^{k} sz[i] \] 显然我不会证明。场上看到 $n$ 仅为 $50$ 就想乱搞，误打误撞弄了一个容斥 $dp$ 出来，实际上正解差不多就是这个。我们考虑钦定选了 $k$ 条边一定存在的方案总数 $f(k)$，由二项式反演的套路可以得知恰好 $k$ 条边存在的方案数 $g(k)$ 满足 \[ g(k) = \sum_{i=k}^{n-1}(-1)^{i-k}\times C(i,k) \times f(i) \] 其中 $C(i,j)$ 表示组合数。

显然我仍然不会证明，但是可以感性理解下，首先 $f(k)$ 满足以下式子 \[ f(k) = \sum_{i=k}^{n-1}C(i,k) \times g(i) \] 这个很好理解，枚举实际上选了多少条边，钦定 $k$ 条边的方案数就是从实际选的边中钦定一些出来。注意这个钦定和至少有区别，不是简单的后缀和，因为实际选一条边的方案可以被多种钦定的情况包含。

我不会证明二项式反演的式子，所以我们从容斥的角度来考虑 $g(k)$，第一项为钦定 $k$ 条边，然后减去被多考虑了的存在 $k+1$ 条边的情况，依此类推。组合数的存在则是因为 $f(i)$ 会被额外考虑 $C(i,k)$ 次。

$f$ 肯定比 $g$ 好算，我们现在需要计算的是选 $k$ 条边，然后得到的联通块组成不同有标号无根生成树的方案数。注意到生成树计数公式中 $n^{k-2}$ 与怎么选边完全无关，所以只需要记录一下 $\prod sz_i$，这个就可以 $dp[i][j][k]$ 表示考虑以 $i$ 为根的子树，选了 $j$ 条边，$i$ 所在连通块大小为 $k$ 的方案数。优化的话，可以考虑 $\prod sz_i$ 的组合意义。于是就是需要在每个连通块内选一个代表元，于是状态第三维简化为是否选了代表元，复杂度 $O(n^2)$。

写法优美的常用函数

发表于 2022-07-12 更新于 2025-02-16 分类于算法竞赛

写法优美的常用函数

收录一些优美的常用函数写法。

分解质因数

有人根本不会用 do while 和 vector。

vector<int> v(0);
for(int i=2;i*i<=n;i++)if(n%i==0){
    v.push_back(i);
    do n/=i; while(n%i==0);
}

SCC

缩点。

int dfs(int u){
	int low=dfn[u]=++df;st[++top]=u;
	for(auto v:e[u]){
		if(!dfn[v])cmin(low,dfs(v));
		else if(!scc[v])cmin(low,dfn[v]);
	}
	if(low==dfn[u]){
		++cnt;int v;
		do val[cnt]+=a[v=st[top--]],scc[v]=cnt; while(v!=u);
	}
	return low;
}

最短路 Dijskstra

如果 $dis\times n\le 8\times 10^{18}$，完全可以它们压成一个数。

priority_queue<LL,vector<LL>,greater<LL>> q;
void dij(int s,int t){
	memset(vis,0,sizeof(vis));
	memset(dis,1,sizeof(dis));
	while(!q.empty())q.pop();
	dis[s]=0;q.push(s);
	while(!q.empty()){
		int u=q.top()%M;q.pop();
		if(vis[u])continue;vis[u]=1;
		if(vis[t])return ;
		for(int i=head[u];~i;i=a[i].next){
			int v=a[i].v,w=a[i].w;
			if(dis[u]+w>=dis[v])continue;
			dis[v]=dis[u]+w;q.push(dis[v]*M+v);
		}
	}
}

前情提要

在 Windows 下使用 gprof 对程序进行性能分析

VTune

ARC144D

组合恒等式

式子1

组合意义证明

代数证明

式子2

组合意义证明

代数证明

式子3

T1

某个不太正确的方式

正常的考虑方式

T2

pip 和包

网络问题

虚拟环境

局部环境

import

name

import 包时的执行逻辑

import 寻找顺序

莫名其妙的 id 不一致问题

import 的代码到底执行了几遍

PYPI

关于 Request 这一类网络请求函数

Requests 库的 POST 相关

设置 pip 默认下载源

环境

基础

开工作目录

本地预览

开 GitHub Pages 仓库

配源码分支

自动部署

metadata

主题

安主题（next）

写上要用这个主题

next

menu

scheme

dark

背景

准备 source 图片

改 style

友情链接

menu 加 link

内联 html

杂项

置顶文章

折叠

插件

搜索插件

数学插件

常用命令

网络相关

CNAME

SEO

CF1698F

思路

回顾

ABC259G

解法一

解法二

Sum up

20220305

ABC242F(二项式反演的进一步理解)

题意：

思考：

ABC242H(初步理解 min-max 容斥)

题意：

思考：

20220309

haltoj128

思考：

haltoj132(分治NTT的思路)

思考：