发表于 | 更新于

Link

打表大法吼

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
const int P=19940417,inv2=9970209,inv6=3323403;
using std::swap;
using std::min;
ll mul(ll a,ll b){return a*b%P;}
ll SumE(ll a,ll d,ll n){return mul(mul((a+(a+mul(d,n-1))%P)%P,n),inv2);}
ll SumS(ll n){return mul(mul(n,mul(n+1,2*n+1)),inv6);}
ll SumS(int i,int j){return ((SumS(j)-SumS(i-1))%P+P)%P;}
ll f(int n)
{
	ll res=0;
	for(int i=1,last;i<=n;i=last+1)
	{
		last=n/(n/i);
		(res+=SumE(n%last,n/i,last-i+1))%=P;
	}
	return res;
}
ll g(int n,int m)
{
	ll res=mul(mul(n,m),m);
	for(int i=1,last;i<=m;i=last+1)
	{
		last=min(n/(n/i),m/(m/i));
		res+=mul(mul(n/i,m/i),SumS(i,last));res%=P;
		res-=mul(mul(n,m/i),SumE(i,1,last-i+1));((res%=P)+=P)%=P;
		res-=mul(mul(m,n/i),SumE(i,1,last-i+1));((res%=P)+=P)%=P;
	}
	return res;
}
int main()
{
	int n,m;get(n),get(m);
	if(n<m) swap(n,m);
	int Ans=((f(n)*f(m)%P-g(n,m))%P+P)%P;
	put(Ans),putchar('\n');
	return 0;
}

发表于 | 更新于

S1(n,k)=(n−1)S1(n−1,k)+S1(n−1,k−1)S_1(n,k)=(n-1)S_1(n-1,k)+S_1(n-1,k-1) S2(n,k)=kS2(n−1,k)+S2(n−1,k−1)S_2(n,k)=kS_2(n-1,k)+S_2(n-1,k-1) B(n)=∑i=0nS2(n,i)=∑i=0n−1Cn−1iBiB(n)=\sum\limits_{i=0}^nS_2(n,i)=\sum\limits_{i=0}^{n-1}C_{n-1}^iB_i

发表于 | 更新于

Link

Solution

从一个集合中取元素，每个元素可以取无限次，问乘积模mm为xx的序列有多少个 看一眼排列似乎是指数生成函数，然而那样就似乎会相当麻烦 注意到每种元素可以取无限次，于是序列的每个位置的元素选取都是独立不受影响的，就可以看成从nn个集合各取一个元素的方案数了，然后就可以套普通生成函数了 下一步需要把答案构造成函数某个项的系数，也就是说项的次数与xx有关，系数为方案数。但是xx的转移是乘积取模的形式，这个不好。为了去掉乘，就把方程取个log\log，哦不对是取个 。然后就好了。 在IDFT之后，在计算结果的时候把ii模一个ϕ(m)=m−1\phi(m)=m-1。快速幂做完就行了。

Tips

各路大神似乎都把 当成了00，但是根据定义 ，强迫症患者表示不爽。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int P=1004535809,LP=21,G=3,MAXM=8000+11,LEN=MAXM<<2;//LEN=MAXM<<1... 2M需要两倍空间
using std::swap;
using std::reverse;

template <class T> T Pow(T base,int index)
{
	T res;res.I();//res默认设置单位I，在其他地方会出问题
	for(;index;base*=base,index>>=1)
		if(index&1) res*=base;
	return res;
}
namespace _NTT_
{
	const int modu=P;
	struct ModInt
	{
		ll num;
		ModInt(ll x=0):num(x%modu){}
		void I(){num=1;}
		ModInt operator +(ModInt b){return ModInt(num+b.num);}
		ModInt operator -(ModInt b){return ModInt((num-b.num)%modu+modu);}
		ModInt operator *(ModInt b){return ModInt(num*b.num);}
		ModInt operator *(ll b){return ModInt(num*b);}
		ModInt &operator =(ll x){return num=x%modu,*this;}
		template <class T> ModInt &operator +=(T b){return *this=*this+b;}
		template <class T> ModInt &operator -=(T b){return *this=*this-b;}
		template <class T> ModInt &operator *=(T b){return *this=*this*b;}
	};
	struct Wing
	{
		ModInt wn[LP+1];
		Wing()
		{
			ModInt g=G;
			for(int i=0;i<=LP;++i)
				wn[i]=Pow(g,(P-1)/(1<<i));
		}
		ModInt &operator [](int x){return wn[x];}
	}wn;
	void Trans(ModInt a[],int n)
	{
		for(int i=1,j=n>>1;i<n-1;++i)
		{
			if(i<j) swap(a[i],a[j]);
			int k=n>>1;
			while(j>=k)
			{
				j-=k;
				k>>=1;
			}
			j+=k;
		}
		for(int d=2,index=1;d<=n;d<<=1,index++)//d<n..
		{
			for(int i=0;i<n;i+=d)
			{
				ModInt w=1;
				for(int j=i;j<i+(d>>1);++j)
				{
					ModInt u=a[j],t=w*a[j+(d>>1)];
					a[j]=u+t,a[j+(d>>1)]=u-t;
					w*=wn[index];
				}
			}
		}
	}
	void DFT(ModInt a[],int n)
	{
		Trans(a,n);
	}
	void IDFT(ModInt a[],int n)
	{
		Trans(a,n);
		reverse(a+1,a+n);
		ModInt inv=Pow(ModInt(n),P-2);
		for(int i=0;i<n;++i)
			a[i]*=inv;
	}
}
int m;
struct Polynom
{
	int a[LEN],n;
	Polynom()
	{
		memset(a,0,sizeof(a));
		n=0;
	}
	void I(){a[0]=n=1;}
	int &operator [](int x){return a[x];} 
	Polynom &operator *=(Polynom&);
};
Polynom operator *(Polynom &a,Polynom &b)
{
	using namespace _NTT_;
	static ModInt A[LEN],B[LEN];static Polynom c;
	int n;
	for(n=1,c.n=a.n+b.n-1;n<c.n;n<<=1);//n>>=1..
	for(int i=0;i<n;++i)
	{
		A[i]=i<a.n?a[i]:0;
		B[i]=i<b.n?b[i]:0;//a[i]!!!
		c[i]=0;
	}
	DFT(A,n),DFT(B,n);
	for(int i=0;i<n;++i)
		A[i]*=B[i];
	IDFT(A,n);
	for(int i=0;i<n;++i)
		(c[i%(m-1)]+=A[i].num)%=P;
	c.n=m+1;
	return c;
}
Polynom &Polynom::operator *=(Polynom &a){return *this=*this*a;}

int Div(int x,int p[])
{
	int pc=0,m=(int)sqrt(x+0.5)+1;
	for(int i=2;i<=m;++i)
	{
		if(x%i==0)
		{
			do x/=i;
			while(x%i==0);
			p[++pc]=i;
		}
	}
	if(!x) p[++pc]=x;
	return pc;
}
int sub[MAXM];
int Pow(ll base,int index,int P)
{
	ll res;
	for(res=1;index;index>>=1,(base*=base)%=P)
		if(index&1) (res*=base)%=P;
	return res;
}
int prim_root(int p)
{
	int ph=p-1,dc=Div(ph,sub);
	for(int g=2;g<P;++g)
	{
		bool check=1;
		for(int i=1;i<=dc && check;++i)
			if(Pow(g,ph/sub[i],p)==1)
				check=0;
		if(check)
			return g;
	}
	return -1;
}
int ind[MAXM];
void AllInd(int p)
{
	ll w=1,g=prim_root(p);
	for(int i=0;i<=p-1;++i)
	{
		ind[w]=i;
		(w*=g)%=p;
	}
}
int main()
{
	static int s[MAXM];
	static Polynom a,f;
	int n,x,sc;
	get(n),get(m),get(x),get(sc);
	AllInd(m);
	for(int i=1;i<=sc;++i) 
	{
		get(s[i]);
		if(!s[i]) continue;
		a[ind[s[i]]]++;
	}
	a.n=m+1;
	f=Pow(a,n);
	int Ans=f[ind[x]];
	put(Ans),putchar('\n');
	return 0;
}
/* AC Record(Bugs)

*/

发表于 | 更新于

感觉原根很玄妙啊

阶

定义

满足 的最小xx称为aa关于pp的阶，记为δp(a)\delta_p(a)，简写为δ(a)\delta (a)

性质

  2. δ(ak)=δ(a)gcd(δ(a),k)\delta(a^k)=\dfrac {\delta(a)}{\gcd(\delta(a),k)}
  3. gcd(δ(a),δ(b))==1⇔δ(ab)==δ(a)δ(b)\gcd(\delta(a),\delta(b))==1\Leftrightarrow \delta(ab)==\delta(a)\delta(b)

求法

根据性质11，δ(x)∣ϕ(x)\delta(x)|\phi(x)，所以只要求出phi(x)phi(x)，依次枚举其因数判断

原根

定义

δP(g)==ϕ(P)\delta_P(g)==\phi(P)，则gg是PP的原根

性质

  1. 奇 质 数 时，才存在原根

求法

将ϕ(P)\phi(P)质因数分解存储在p[]p[]中 然后从22开始枚举判断，如果对于∀pi∈p[]\forall p_i\in p[]，有 ，则xx是PP的原根(一开始分子直接写了PP,但是因为数据弱一直水过了？？)

指标

定义

如果gcd(b,P)==1\gcd(b,P)==1，那存在a,0≤a<ϕ(P)a,0\le a < \phi(P)，满足 ，称aa为bb关于PP的指标，记 ，简记

性质

求法

求出原根gg，然后BSGS。

发表于 | 更新于

Link

Solution

的xx的个数 P=∑i=1cpikiP=\sum\limits_{i=1}^{c}p_i^{k^i}，根据 转化为cc个 的解的积

Case #1 b∣pkb|p^k

则 设x=λpt,gcd(λ,p)==1x=\lambda p^{t},\gcd(\lambda,p)==1 可以知道at≥kat\ge k t≥⌈ka⌉t\ge \lceil \dfrac ka\rceil 所以解数为pk−⌈ka⌉p^{k-\lceil \frac ka\rceil}

Case #2

设b=λpt,gcd(λ,p)==1b=\lambda p^{t},\gcd(\lambda,p)==1

如果 ，假设存在解x0x_0，pp的次数为ss (ps)a=psa=pt(p^s)^a=p^{sa}=p^t，与 矛盾，所以必定无解 当a∣ta|t时，方程可以化为 令x′=xpta,b′=λ,p′=pk−tx'=\dfrac x{p^{\frac ta}},b'=\lambda,p'=p^{k-t} 则x′∈[0,pk−ta)x'\in [0,p^{k-\frac ta}) 但是在新的方程中，x′∈[0,pk−t)x'\in[0,p^{k-t})，所以对新方程求出答案之后需要×pt−ta\times p^{t-\frac ta}

对这个方程取 现在需要把指标项代换，需要保证 与xx一一对应，取p′p'的原根作为底数即可，而p′p'一定存在原根。 令 现在转化为求方程 的解数

对于 的解数 Ax+Cy=gcd(A,C)Ax+Cy=\gcd(A,C) 还原到原方程的解就是X=Bgcd(A,C)xX=\dfrac B{\gcd(A,C)}x，设第一个非负XX为X0X_0 则X=X0+kCgcd(A,C)X=X_0+\dfrac {kC}{\gcd(A,C)} 所以在 意义下有gcd(A,C)\gcd(A,C)个解 这么显然的东西我居然还想了这么久 就好了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}

using std::pair;
using std::make_pair;

const int SQRT=1e6;

struct Hash
{
	static const int SIZE=SQRT,P=99929;
	struct Node
	{
		int key,val;
		Node *pre;
		Node(int key,int val,Node *pre):key(key),val(val),pre(pre){}
	}*POOL,*ME,*id[P];
	Hash()
	{
		POOL=ME=(Node*)malloc(SIZE*sizeof(Node));
		memset(id,0,sizeof(id));
	}
	void Reset()
	{
		memset(id,0,sizeof(id));
		ME=POOL;
	}
	Node *FindKey(int key)
	{
		for(Node *p=id[key%P];p;p=p->pre)
			if(p->key==key) return p;
		return 0;
	}
	int &operator [](int x)
	{
		Node *re=FindKey(x);
		if(re)
			return re->val;
		else
		{
			int ha=x%P;
			return (id[ha]=new(ME++) Node(x,-1,id[ha]))->val;
		}
	}
	int Find(int x)
	{
		Node *re=FindKey(x);
		return re?re->val:-1;
	}
};
int pow(int base,int index)
{
	int res;
	for(res=1;index;index>>=1,base*=base)
		if(index&1) res*=base;
	return res;
}
int pow(int base,int index,int P)
{
	int res;
	for(res=1;index;index>>=1,base=(ll)base*base%P)
		if(index&1) res=(ll)res*base%P;
	return res;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int Div(int x,pair<int,int> *p)
{
	int m=(int)sqrt(x+0.5)+1,c=0;
	for(int i=2;i<=m;++i)
		if(x%i==0)
		{
			int t=0;
			do ++t,x/=i;
			while(x%i==0);
			p[++c]=make_pair(i,t);
		}
	if(x!=1)
		p[++c]=make_pair(x,1);
	return c;
}
int BSGS(int a,int b,int P)//a^x equiv b mod P
{
	static Hash S;
	int modu=P;
	a%=P,b%=P;
	ll t=1;int dep=0;
	for(int d=gcd(a,P);d!=1;d=gcd(a,P))
	{
		if(b%d) return -1;
		++dep;
		b/=d,P/=d,(t*=a/d)%=modu;
	}
	S.Reset();
	int m=(int)sqrt(P+0.5)+1;
	ll baj=b;
	for(int j=0;j<=m;++j)
	{
		S[baj]=j;
		(baj*=a)%=modu;
	}
	int asp=pow(a,m,modu);
	ll aspi=asp;
	for(int i=1,j;i<=m;++i)
	{
		if((j=S.Find(aspi))!=-1)
			return i*m-j+dep;
		(aspi*=asp)%=modu;
	}
	return -1;
}
int phi(int x)
{
	static pair<int,int> sub[SQRT];
	int dc=Div(x,sub);
	int res=x;
	for(int i=1;i<=dc;++i)
		(res/=sub[i].first)*=(sub[i].first-1);
	return res;
}
int ind(int a,int b,int P){	return BSGS(a,b,P);}
int prim_root(int P)
{
	static pair<int,int> sub[SQRT];
	int ph=phi(P),dc=Div(ph,sub);
	for(int g=2;g<P;++g)
	{
		bool check=1;
		for(int i=1;i<=dc && check;++i)
			if(pow(g,ph/sub[i].first,P)==1)
				check=0;
		if(check)
			return g;
	}
	return -1;
}
int Calc(int a,int b,int p,int k)
{
	int pk=pow(p,k);
	//a%=pk????
	b%=pk;
	if(b)
	{
		int b1=b,t=0;
		while(b1%p==0) ++t,b1/=p;
		if(t%a!=0) return 0;
		int p1=pow(p,k-t),
			ph=phi(p1),
			ind_b=ind(prim_root(p1),b1,p1);
		int d=gcd(a,ph);
		return ind_b%d?0:d*pow(p,t-t/a);
	}
	else
		return pow(p,k-(k/a+(k%a?1:0)));
}
void Work()
{
	static pair<int,int> sub[SQRT];
	int A,B,K,P;
	get(A),get(B);get(K);P=K*2+1;
	int Ans=1,dc=Div(P,sub);
	for(int i=1;i<=dc;++i)
	{
		int res=Calc(A,B,sub[i].first,sub[i].second);
		Ans*=res;
		//put(res),putchar('\n');
	}
	put(Ans),putchar('\n');
}
int main()
{
	//freopen("input","r",stdin);
	int T;get(T);
	while(T--)
		Work();
	return 0;
}
/* AC Record(Bugs)

*/

发表于 | 更新于

f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2) 定义生成函数为G(x)G(x) G(x)=f1x+f2x2+f3x3+...+fnxn+...G(x)=f_1x+f_2x^2+f_3x^3+...+f_nx^n+... G(x)−f1x−f2x2G(x)-f_1x-f_2x^2 =(f1+f2)x3+(f2+f3)x4+...+(fn−2+fn−1)xn+...=x2G(x)+xG(x)−xf1x=(f_1+f_2)x^3+(f_2+f_3)x^4+...+(f_{n-2}+f_{n-1})x^n+...=x^2G(x)+xG(x)-xf_1x G(x)−x=x2G(x)+xG(x)G(x)-x=x^2G(x)+xG(x) (1−x−x2)G(x)=x(1-x-x^2)G(x)=x G(x)=x1−x−x2=−(x+1−52)(x+1+52)G(x)=\dfrac x{1-x-x^2=-(x+\dfrac{1-\sqrt 5}2)(x+\dfrac{1+\sqrt5}2)} =ax+1−52−bx+1+52=\dfrac a{x+\dfrac{1-\sqrt 5}2}-\dfrac b{x+\dfrac{1+\sqrt5}2} 解得a=5−510,b=5+510a=\dfrac {\sqrt5-5}{10},b=\dfrac {\sqrt5+5}{10} G(x)=5−510x+1−52−5+510x+1+52G(x)=\dfrac {\dfrac {\sqrt5-5}{10}}{x+\dfrac{1-\sqrt 5}2}-\dfrac {\dfrac {\sqrt5+5}{10}}{x+\dfrac{1+\sqrt5}2} =15(11−1+52x−11−1−52x)=\dfrac 1{\sqrt 5}(\dfrac 1{1-\dfrac{1+\sqrt 5}2x}-\dfrac 1{1-\dfrac {1-\sqrt 5}2x}) 根据等比数列求和公式 a+aq+aq2+..+aqn−1=a(1−qn)1−qa+aq+aq^2+..+aq^{n-1}=\dfrac {a(1-q^n)}{1-q} 当−1<q<1-1 < q < 1时 limn→∞qn=0\lim\limits_{n\rightarrow \infty}q^n=0 所以1+x+x2+x3+...=11−x1+x+x^2+x^3+...=\dfrac 1{1-x} 设α=1+52,β=1−52\alpha=\dfrac {1+\sqrt 5}2,\beta=\dfrac {1-\sqrt 5}2 则上式 =15(11−αx−11−βx)=\dfrac 1{\sqrt 5}(\dfrac 1{1-\alpha x}-\dfrac 1{1-\beta x}) 下一步用到的公式的前提条件是∣x∣<1|x|< 1。so?

发表于 | 更新于

Problem

要求维护一棵树，在资磁LCT所有操作的同时，进行对子树的修改和查询操作。

Solution

Tarjan提出的解决方案是

黄志翱大神在论文中写的是

看过两篇论文的zky大神说这两者不是完全相同的

所以还是叫它 吧(虽然我确实更喜欢 这个名字)

可以看作是 的一种改进，解决了 不能触及子树的弱点，据说复杂度也是O(nlogn)O(n\log n)，只是常数巨大。

在 上， 维护实链，虚边只能通过虚子树的父指针连接。

在 上，在维护实链的同时想办法维护子树，就可以达到目的了。

维护子树，显然可以在每个节点上记录一个平衡树存储所有的虚子树的根，在 中切换实边对应在平衡树中的插入删除。然而这样会比较麻烦，因为每个节点同时存在两份数据，修改任意一个必须手动地让另一个同步。

翱犇在论文中给出了一种更巧妙的做法(来源于杜教?)，记录四个子节点0,1,2,3，前两个还是维护链，后两个维护虚子树。如果通过某种手段可以让所有虚子树都处于叶节点，就可以直接链接过来而不会产生问题了。

做法和边分治比较类似：加入虚节点，把虚子树根的序列强制转成二叉树，就可以了。

注意的是，为了保证复杂度，维护虚子树的二叉树也需要 ，此时必须 虚节点，转到真节点的下方。 会发现：一个真节点的2,3号子节点，维护的序列是完全不会有联系的，因为都是 到真节点就停止了，不会到另一棵子树。这个不必困惑，因为首先这样做是不会让复杂度退化的，其次这样做可以使得对虚实节点的操作完全一视同仁，可以简化实现。

发表于 | 更新于

Link

Solution

训练指南的模板题，还是记一下吧 对于一个循环CC 假设项数nn为奇数 则C2C^2一定也有奇数个项 否则 C2C^2一定是两个n2\dfrac n2项的循环 根据这个结论判断能否构造合法解 自行举例感受一下

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define gets(x) scanf("%s",x)
bool Work()
{
	static char s[30];
	static bool ud[30];
	static int cnt[30];
	gets(s+1);
	memset(ud,0,sizeof(ud));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=26;++i)
		s[i]-='A'-1;
	for(int i=1;i<=26;++i)
	{
		if(ud[i]) continue;
		int l=0;
		while(!ud[i])
		{
			l++;
			ud[i]=1;
			i=s[i];
		}
		cnt[l]++;
	}
	for(int i=2;i<=26;i+=2)
		if(cnt[i]&1) return 0;
	return 1;
}
int main()
{
	freopen("input","r",stdin);
	int T;get(T);
	while(T--)
		puts(Work()?"Yes":"No");
	return 0;
}
/* AC Record(Bugs)
++->+=2
*/

发表于 | 更新于

WC像梦一般就过去了，记一些碎片吧 有幸结识了很多大神。 舍友是qdez的dms，wxy，nzm， 虽然我们学校只有我一个人，但和每天和他们一块感觉非常愉快 认识了总是把包背在前面的hwc 认识了今年唯一一个Au wjh 还见到了闻名已久的zyz，Menci，ShallWe，Yveh 还认识了大连24中的几位特别会玩狼人杀的大神

day 0

一句话看完开幕式 CCF ONI，拒绝作弊； P NOI，拒绝作弊； 因为相爱，拒绝作弊。

day 1

走之前swh跟我说要享受WC，听了第一节课才发现WC被称为冬眠营是有原因的 jcvb讲字符串导论，讲了各种神奇的结论和各种神奇的引理，听了几个证明之后脑子就转不动了 任之洲讲Ulam猜数游戏，讨论了一些容错的问题的解法，比较有趣 尛焱轟讲IOI2016的试题，感到一些思路是非常妙的，IOI和NOI风格还是差别比较大 晚上姻缘交流，matthew99讲了一种BM算法，可以很快地求递推式？听起来很厉害的样子 SkyDec讲了一道有趣的字符串题，标程30k，1000行 讲完之后不久，uoj上就多了十几个差评 好像不记得另一位大神的名字了，讲了仙人掌计数，看起来很厉害

day 2

胡渊鸣讲物理模拟，比较长见识 杜教讲并行算法，比较长见识 猪猪侠和cy讲了一般图最大匹配的矩阵做法 immortalCO和WrongAnswer讲了一些关于DFS序和仙人掌的东西，但中途和dms他们跑去试机了，没有听完

day 3

北大一位讲师来讲近似算法，看起来比较学术，好吧我复习FFT 毕老师讲整数与多项式，一开始还可以，后来就跟不上了 晚上试机赛，起床困难综合征和小Q的运动季。dms参加比赛多，第一题写过4遍，就直接T2。1h后，我写完拍完T1，看T2。 T2是提答，看来今年考提答。第一个点枚举，第二个点dms猜答案在2322^{32}之内，枚了30min发现解很差，我看了看想枚举子集用扩欧解，dms告诉我子集枚举不完，我就想随机子集做扩欧。 dms大爷一拍大腿，想出了正解：解模数互质的最大独立集，然后CRT。我写程序验证下，发现所有模数互质。dms太神了！！

day 4

wangyisong讲底层优化，据说和考试有着密切关系。卡常数当然与考试有关了！但我猜中开始没猜中结局 kefandong讲线性代数，感觉他讲课还是不错的，语速平缓，发音清楚，但我听着听着还是掉线了 jiry讲压缩算法，带领全场开车 下午+晚上就写了可持久化Treap和单纯形！Treap的SIZE一开始待定就开成了0，结果没RE反而把输入缓冲区冲了。。学了构造初始可行解的办法，狂T不止，结果不知道随便怎么改改就A了，SMG!!

day 5

考试，早晨吃了不少为了防止饿，结果最后灌了一杯奶茶，肚子就废掉了，又去上厕所，白吃了那么多， 听了dms的话没有带水，结果旁边的妹子不仅带水，还带了一瓶饮料！ 又开始犯大赛嗓子干综合征(不过还好开场不久就发了优酸乳)，然后比赛开始了 T1判前20分是很好写的吧。没错我没有意识到后面是环和环套树！ 于是开始写暴力，结果写了很长时间，居然是ii，jj弄错了！！眼高手低得治！ 两种暴力放着拍，做T2。 三道题。。好吧，，模板是大括号不换行，从0开始计数的。。。很不习惯，手动把大括号换行 T1把sort(a,n)改成std::sort(a,a+n)就有5分，剩下的看起来一脸不可做，只能桶排吧 前16位排，后16位排，写完很兹磁啊，结果WA掉了。又查了很久，发现连桶排的顺序都搞错了。。今天是怎么了。改掉之后就不管了，反正已经达到复杂度最优，我也想不出什么别的优化方法了 T2纯暴力 T3纯暴力 然后开提答。提答1分1分地给？好吧。 前后手玩几分，贪心构造几分，最后9分收场，花了2h。出场时候大家都说十几分很好做，感觉自己弱爆了 在结束前10分钟，我回去看第一题，忽然发现有个很好写的环。但也肯定没办法，只好扔掉了，但似乎状态少爆搜可以过？ 离场之后去食堂，结果是第一个到食堂的选手，被志愿者认成了志愿者 比较压抑，回宿舍看新出的Agents Of Shield，刚看到Mace被包围了就被叫去看成绩 在赛场门口等了一年的样子。迅速走到座位，深呼吸，一看69分。似乎没有挂的很惨？遗憾的就是环居然没有看出来，少了10分。 讲题之前，集训队爷把T2出题人松爷开了。 讲题，immortalCO说T1前40分因为状态总数少，40分写一个爆搜就行了。dms就是这样做的，10min四十分。我后面的爆搜全WA了，想想是因为我没指望50的范围，排列在8的范围内的hash是不爆int的，而50的范围就相当于直接自然溢出，一个是容易冲突，再一个没准出现负数，模一下得到的hash值也是负数。正解是个置换之类的东西，不懂。 T2的T1要分三段，因为考虑Cache缓存的大小三段可以更好地存下。听到这，我就不听后两问了。 T3做法更复杂，最高分才30+ 我也就拿了暴力分，但似乎很多大神考挂了 晚上联欢，Menci和24OI合唱了一首改编的歌，唱出了OIer的生活，掌声雷动

day 6

社会活动日，去柯岩和鲁迅故居。 在鲁迅故居和龙哥一起转了转鲁迅纪念馆，龙哥教导了我很多人生的经验。能结识龙哥这样的富有人格魅力的大神，真的感到幸运之至 下午dms签到了PKU的省队一本。 zyz和韩神和汪神去THUWC学车

day 7

回家

总结

WC的考试成绩我觉得不能说明什么，就是比rp和暴力。 但这也是我第一次考到前五，希望在省选中也能考到这样的名次。

以后在考试之前要多喝水 多打打CF，简单题越快越好 练习提答

继续努力吧。加油

发表于 | 更新于

买票买晚了，结果没买上高铁票，只好坐汽车。 结果大年初六出发，高速免费的最后一天！！ 简直上天了，向南走的半条路变成了停车场，向北走的半条路畅通无阻。就看着对面的车一辆辆呼啸而去，自己的车gu gu yong yong（方言缓慢移动的意思），心里仿佛有 只CnmC_n^m在奔腾。 于是司机果然是experienced，下高速在乡间小路绕来绕去，最后还是晚了6个小时？啊本来应该8个小时的。。期间一个服务区都没停，下车之后感觉腿已经不是自己的了。 背上放在行李架上的背包，一股花生油的香味向我袭来。。。行李架上居然还存在着一桶漏了的花生油？！！于是只好提着背包了。 本来想直接转车到绍兴，但是已经9点多了。。 到酒店安顿下已经10点了。。但是饿了一天，不吃不行，于是出去吃了一顿火锅。 哦以上是

day -1

现在是

day 0

早上在外面走，过马路的时候看到一辆客车。我们停下等车过去，可司机居然停下车做手势让我们先过去；路上一个人在我们没有开口问的情况下为我们指了一下车站的方向——果然文明程度高啊！ 10点到了绍兴一中。 外面看校舍比较旧了，一进宿舍发现居然是大学那样上面床下面书桌的配置！简直了，想起日照一中8个床位的上下铺，不禁感慨::同样是一中，宿舍的差距怎么那么大呢。。