-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtemplate.tex
11977 lines (11045 loc) · 346 KB
/
template.tex
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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\input{head.tex}
\fancyhead[RO,RE]{Team Reference Document} %奇数页左侧,偶数页右侧显示页眉
\title{\yihao\hei Team Reference Document}
\author{TI1050: 薛鸿涛、潘律旨、罗天松}
\date{\today}
\begin{document}
\maketitle % 生成标题
\begin{figure}[ht]
\centering %居中显示
\includegraphics[scale=0.70]{images/ccpc_logo.png} % 插入图片
\end{figure}
\begin{figure}[ht]
\centering %居中显示
\includegraphics[scale=0.65]{images/icpc_logo.png} % 插入图片
\end{figure}
\newpage % 强制换页
\tableofcontents
\newpage
\section{数学}
\subsection{整数划分}
\subsubsection{小常数版本}
牛客 7803I
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 5e5 + 10;
constexpr int M = 1300;
constexpr int mod = 998244353;
int n, f[M], g[N];
// g[i] 表示 i 的划分数
void gao() {
f[1] = 1, f[2] = 2, f[3] = 5, f[4] = 7;
for (int i = 5; i < M; ++i) f[i] = 3 + 2 * f[i - 2] - f[i - 4];
g[0] = 1;
for (int i = 1; i <= n; ++i) {
ll sum[4] = {0}, now = 0;
int j = 1;
for (; f[j + 3] <= i; j += 4) {
sum[0] += g[i - f[j]];
sum[1] += g[i - f[j + 1]];
sum[2] -= g[i - f[j + 2]];
sum[3] -= g[i - f[j + 3]];
}
now = (sum[0] + sum[1] + sum[2] + sum[3]) % mod;
for (; f[j] <= i; ++j) {
if ((j + 1) >> 1 & 1) {
now += g[i - f[j]];
} else {
now -= g[i - f[j]];
}
}
now = (now + mod) % mod;
g[i] = now;
}
}
int main() {
cin >> n;
gao();
cout << g[n - 1] << endl;
return 0;
}
\end{lstlisting}
\subsubsection{牛逼版本}
牛客 7803I \par
好像只能求模数为 $998244353$ 的情况。
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+50, G=3, mod=998244353;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<0) ? (x-y+mod) : (x-y);}
inline int mul(int x,int y) {return (LL)x*y%mod;}
inline int power(int a,int b,int rs=1) {for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a); return rs;}
int n,k,g[N*8],f[N*8],tp[N*8],w[N*8],pos[N*8];
inline void init(int len) { k=len<<1; for(int i=1;i<k;i++) pos[i]=(i&1) ? ((pos[i>>1]>>1)^(k>>1)) : (pos[i>>1]>>1);}
inline void dft(int *a) {
for(int i=1;i<k;i++) if(pos[i]>i) swap(a[pos[i]],a[i]);
for(int bl=1;bl<k;bl<<=1) {
int tl=bl<<1, wn=power(G,(mod-1)/tl);
w[0]=1; for(int i=1;i<bl;i++) w[i]=mul(w[i-1],wn);
for(int bg=0;bg<k;bg+=tl)
for(int j=0;j<bl;j++) {
int &t1=a[bg+j], &t2=a[bg+j+bl], t=mul(t2,w[j]);
t2=dec(t1,t); t1=add(t1,t);
}
}
}
inline void fuck(int *a,int *b,int len) {
if(len==1) {b[0]=power(a[0],mod-2); return;}
if(len!=1) fuck(a,b,len>>1);
init(len);
for(int i=0;i<len;i++) tp[i]=a[i];
for(int i=len;i<k;i++) tp[i]=0;
dft(b); dft(tp);
for(int i=0;i<k;i++) b[i]=dec(mul(2,b[i]),mul(tp[i],mul(b[i],b[i])));
reverse(b+1,b+k); dft(b);
const int inv=power(k,mod-2);
for(int i=0;i<len;i++) b[i]=mul(b[i],inv);
for(int i=len;i<k;i++) b[i]=0;
}
//题目要求 n - 1 的划分数
int main() {
cin>>n;n--;
for(int k=1;(3*k*k-k)/2<=n;++k) {
int v=(k&1) ? mod-1 : 1;
g[(3*k*k-k)/2]+=v;
g[(3*k*k+k)/2]+=v;
} g[0]=1;
for(k=1;k<=n;k<<=1);
fuck(g,f,k);
cout<<f[n]<<endl;
}
\end{lstlisting}
\subsubsection{例题}
HDU 4651, 4658\par
题意:求$n$的划分数。4659要求元素重复次数小于$k$。\par
代码中$ans[i]$表示的就是$i$的划分数,$solve(n, k)$表示重复次数小于$k$的划分数
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int ans[N];
void init() {
memset(ans, 0, sizeof(ans));
ans[0] = 1;
for (int i = 1; i < N; ++i) {
ans[i] = 0;
for (int j = 1; ; j++) {
int tmp = (3 * j - 1) * j / 2;
if (tmp > i) break;
int _tmp = ans[i - tmp];
if (tmp + j <= i) {
_tmp = (_tmp + ans[i - tmp - j]) % mod;
}
if (j & 1) {
ans[i] = (ans[i] + _tmp) % mod;
} else {
ans[i] = (ans[i] - _tmp + mod) % mod;
}
}
}
}
int solve(int n, int k) {
int res = ans[n];
for (int i = 1; ; i++) {
int tmp = k * i * (3 * i - 1) / 2;
if (tmp > n) {
break;
}
int _tmp = ans[n - tmp];
if (tmp + i * k <= n) {
_tmp = (_tmp + ans[n - tmp - i * k]) % mod;
}
if (i & 1) {
res = (res - _tmp + mod) % mod;
} else {
res = (res + _tmp) % mod;
}
}
return res;
}
int main() {
init();
int _T, n, k;
cin >> _T;
while (_T--) {
cin >> n >> k;
cout << solve(n, k) << '\n';
}
return 0;
}
\end{lstlisting}
\subsection{线性基}
\subsubsection{应用}
\begin{enumerate}
\item UVALive 8512\par
题意:\par
给出$n$个数$a_i$,每次询问一个区间$[l, r]$,询问从中挑选任意个数的异或和再和$k$按位或的最大值,即假设挑选的数为$a_{p_1}, a_{p_2}, \cdots, a_{p_m}$,那么要使得下式最大:
\begin{eqnarray*}
k \;or\; (a_{p_1} \oplus a_{p_2} \cdots a_{p_m})
\end{eqnarray*} \par
思路:
先对所有$a_i$进行处理,将二进制位上$k$为$1$的位,在$a_i$中都置为$0$。\par
然后就是线段树维护线性基,求区间最大值。\par
因为这样一来,相当于把$k$为$1$的那些位和$a_i$对应的那些位剥离开来。\par
\end{enumerate}
\subsection{对偶问题}
\begin{eqnarray*}
max\{c^Tx|Ax\le b\}=min\{b^Ty|A^Ty\ge c\}
\end{eqnarray*}
\subsection{单纯形法}
线性规划的标准形式:\par
求$\displaystyle Max\;\;z = \sum\limits_{j = 1}^n C_jX_j$
\begin{eqnarray*}
\left\{
\begin{array}{cccc}
\sum\limits_{j = 1}^nA_{i, j}X_j &\leq B_j, i =& 1, 2, \cdots, m \\
X_j &\geq 0, j =& 1, 2, \cdots, n
\end{array}
\right.
\end{eqnarray*}
通俗来说,即:
\begin{itemize}
\item 目标函数要求最大化
\item 约束条件均为不等式
\item 决策变量非负约束
\end{itemize}
普通线性规划化为标准形:
\begin{itemize}
\item 若目标函数为最小化, 可以通过取负或者对偶, 求最大化
\item 约束不等式为等式,可以拆成两个不等式约束,即$\displaystyle X = b$可以拆成
\begin{eqnarray*}
\left\{
\begin{array}{cccc}
X &\leq& b \\
X &\geq& b
\end{array}
\right.
\rightarrow
\left\{
\begin{array}{cccc}
X &\leq& b \\
-X &\leq& -b
\end{array}
\right.
\end{eqnarray*}
\item 若存在取值无约束的变量,可转变为两个非负变量的差
\begin{eqnarray*}
-\infty \leq _k \leq \infty \rightarrow
\left\{
\begin{array}{cccc}
x_k &=& x_m - x_n \\
x_m, x_n &\geq& 0
\end{array}
\right.
\rightarrow
\left\{
\begin{array}{cccc}
x_k - x_m + x_n &=& 0 \\
x_m, x_n &\geq& 0
\end{array}
\right.
\end{eqnarray*}
再转化为两个不等式\par
\end{itemize}
\subsubsection{UOJ 179}
题意:\par
有$n$个实数变量$x_1, x_2, \cdots, x_n$, 和$m$条约束, 其中第$i$条约束形如$\sum\limits_{j = 1}^n a_{ij}x_j \leq b_j$
此外这$n$个变量需要满足非负性限制,即$x_j \geq 0$\par
指定$x_j$每个变量的取值, 使得目标函数$F = \sum\limits_{j = 1}^n c_jx_j$最大\par
无解输出"Infeasible"。\par
没有最大值输出"Unbounded"。\par
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-5;
struct LP {
int m, n;
vector<int> B, N;
vector<vector<db> > D;
LP() {}
LP(const vector<vector<db> > &A, const vector<db> &b, const vector<db> &c) {
m = (int)b.size(); n = (int)c.size(); N = vector<int>(n + 1); B = vector<int>(m + 1);
D = vector <vector<db> >(m + 2, vector<db>(n + 2));
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
N[n] = -1; D[m + 1][n] = 1;
}
void Pivot(int r, int s) {
for (int i = 0; i < m + 2; i++) if (i != r)
for (int j = 0; j < n + 2; j++) if (j != s)
D[i][j] -= D[r][j] * D[i][s] / D[r][s];
for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] /= D[r][s];
for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] /= -D[r][s];
D[r][s] = 1.0 / D[r][s];
swap(B[r], N[s]);
}
bool Simplex(int phase) {
int x = phase == 1 ? m + 1 : m;
while (true) {
int s = -1;
for (int j = 0; j <= n; j++) {
if (phase == 2 && N[j] == -1) continue;
if (s == -1 || D[x][j] < D[x][s] || (D[x][j] == D[x][s] && N[j] < N[s])) s = j;
}
if (D[x][s] > -eps) return true;
int r = -1;
for (int i = 0; i < m; i++) {
if (D[i][s] < eps) continue;
if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
((D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r])) r = i;
}
if (r == -1) return false;
Pivot(r, s);
}
}
db Solve(vector<db> &x) {
int r = 0;
for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
if (D[r][n + 1] < -eps) {
Pivot(r, n);
//无解
if (!Simplex(1) || D[m + 1][n + 1] < -eps) return -numeric_limits<db>::infinity();
for (int i = 0; i < m; i++) if (B[i] == -1) {
int s = -1;
for (int j = 0; j <= n; j++)
if (s == -1 || D[i][j] < D[i][s] || (D[i][j] == D[i][s] && N[j] < N[s])) s = j;
Pivot(i, s);
}
}
//无穷解
if (!Simplex(2)) return numeric_limits<db>::infinity();
x = vector<db>(n);
for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
return D[m][n + 1];
}
};
const int N = 1e4 + 10;
int n, m, t, c[N];
int main() {
while (scanf("%d%d%d", &n, &m, &t) != EOF) {
vector <vector<db> > A(m + 2, vector <db>(n + 2, 0));
vector <db> B(m);
vector <db> C(n);
vector <db> X;
for (int i = 0; i < n; ++i) scanf("%d", c + i), C[i] = c[i];
for (int i = 0, b; i < m; ++i) {
for (int j = 0, a; j < n; ++j) {
scanf("%d", &a);
A[i][j] = a;
}
scanf("%d", &b);
B[i] = b;
}
LP lp(A, B, C);
db res = lp.Solve(X);
if (res == -numeric_limits<db>::infinity()) {
puts("Infeasible");
} else if (res == numeric_limits<db>::infinity()) {
puts("Unbounded");
} else {
printf("%.10f\n", res);
if (t) for (int i = 0; i < n; ++i)
printf("%.10f%c", X[i], " \n"[i == n - 1]);
}
}
return 0;
}
\end{lstlisting}
\subsubsection{Luogu P3337}
$A[i][0] i \in [1, n]$等价于$B$矩阵。\par
$A[0][i] i \in [1, m]$等价于$C$矩阵。\par
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct LP {
static const T INF = 0x3f3f3f3f;
int n, m;
vector <T> v;
vector <vector<T> > a;
LP(const vector<vector<T> > &_a, int _n, int _m) {
a = _a; n = _n; m = _m;
v.resize(m + 1);
}
void pivot(int x, int y) {
int tp = 0;
for (int i = 0; i <= m; i++) if (a[x][i]) v[++tp] = i;
for (int i = 0;i <= n; i++) {
if (i != x && a[i][y]) {
int k = a[i][y]; a[i][y] = 0;
for (int j = 1; j <= tp; j++)
a[i][v[j]] -= k * a[x][v[j]];
}
}
}
T solve() {
a[n + 1][0] = INF;
while(1) {
int x = 0, y = n + 1;
for (int i = 1; i <= m; i++)
if (a[0][i] > 0) { x = i; break; }
if (!x) return -a[0][0];
for (int i = 1; i <= n; i++)
if(a[i][x] > 0 && a[i][0] < a[y][0]) y = i;
pivot(y, x);
}
}
};
const int N = 1e4 + 10;
int n, m, a[N];
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
vector <vector<int> > A(n + 2, vector <int>(m + 2, 0));
for (int i = 1; i <= n; ++i) scanf("%d", a + i), A[i][0] = a[i];
for (int i = 1, l, r, d; i <= m; ++i) {
scanf("%d%d%d", &l, &r, &d);
A[0][i] = d;
for (int j = l; j <= r; ++j)
A[j][i] = 1;
}
LP <int> lp(A, n, m);
printf("%d\n", lp.solve());
}
return 0;
}
\end{lstlisting}
\subsection{梯度下降法}
每次朝着函数的梯度的反方向前进$\alpha$步, $\alpha$为学习率\par
\begin{eqnarray*}
\Theta^n = \Theta^{n + 1} - \alpha \nabla J(\Theta)
\end{eqnarray*}
选定合适的$\alpha$和$n$迭代下去即可。\par
CometOJ 16J\par
题意:\par
有$n$个玩家玩一个游戏,游戏分两轮,对于每一轮游戏,标签相同的玩家需要跑到同一个点集合\par
假设一个玩家的初始位置为$S_0$, 两轮的集结点为$S_1, S_2$, 它需要付出的体力为$dis(S_1 - S_0) + dis(S_2 - S_1)$, 其中$dis$为两点之间的欧几里得距离。\par
对于每一轮每一种标签定一个集结点,使得所有玩家的消耗的体力和最少。\par
思路:\par
易知,$n$的大小不会影响体力消耗函数的梯度,不妨令它为$1$\par
我们令$x_i$表示初始位置向量的第$i$维度值,$y_i$表示第一轮集结点位置的第$i$维度的值, $z_i$表示第二轮集结点位置的第$i$维度的值,那么有:
\begin{eqnarray*}
f(y_0, y_1, z_0, z_1) = (y_0 - x_0)^2 + (y_1 - x_1)^2 + (z_0 - y_0)^2 + (z_1 - y_1)^2
\end{eqnarray*}
求其梯度分量有:
\begin{eqnarray*}
\frac{\partial f}{\partial y_0} &=& 2(2y_0 - x_0 - z_0) \\
\frac{\partial f}{\partial y_1} &=& 2(2y_1 - x_1 - z_1) \\
\frac{\partial f}{\partial z_0} &=& -y_0 + z_0 \\
\frac{\partial f}{\partial z_1} &=& -y_1 + z_1
\end{eqnarray*}
按公式迭代即可。\par
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 5e2 + 10;
int n, f[N], g[N];
db x[N][2], y[N][2], z[N][2], nxY[N][2], nxZ[N][2];
db sqr(db x) { return x * x; }
db gao() {
int loop = 50000;
db alpha = 1e-3;
while (loop--) {
for (int i = 1; i <= n; ++i) {
nxY[f[i]][0] -= alpha * (2.0 * y[f[i]][0] - x[i][0] - z[g[i]][0]);
nxY[f[i]][1] -= alpha * (2.0 * y[f[i]][1] - x[i][1] - z[g[i]][1]);
nxZ[g[i]][0] -= alpha * (-y[f[i]][0] + z[g[i]][0]);
nxZ[g[i]][1] -= alpha * (-y[f[i]][1] + z[g[i]][1]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
y[i][j] = nxY[i][j];
z[i][j] = nxZ[i][j];
}
}
}
db res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
res += sqr(x[i][j] - y[f[i]][j]);
res += sqr(y[f[i]][j] - z[g[i]][j]);
}
}
return res;
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; ++i) scanf("%lf%lf", x[i], x[i] + 1);
for (int i = 1; i <= n; ++i) scanf("%d", f + i);
for (int i = 1; i <= n; ++i) scanf("%d", g + i);
printf("%.6f\n", gao());
}
return 0;
}
\end{lstlisting}
\subsection{斯特灵数}
\subsubsection{第一类}
$\left[
\begin{array}{cccc}
n \\
m
\end{array}
\right]$表示$n$个元素分成$m$个环的方案数。\par
递推式:
\begin{eqnarray*}
\left[
\begin{array}{cccc}
n \\
m
\end{array}
\right]
=
\left[
\begin{array}{cccc}
n - 1 \\
m - 1
\end{array}
\right]
+
(n - 1) \cdot
\left[
\begin{array}{cccc}
n - 1 \\
m
\end{array}
\right]
\end{eqnarray*} \par
考虑之前已经放好的$n - 1$个数,那么有一个新加入的数时有两种选择,第一种是自己成一个环,贡献是$\left[\begin{array}{cccc} n - 1 \\ m - 1\end{array}\right]$,第二种是放到一个已经存在的环内,那么它可以放在任意一个数的前面,所以贡献是$n - 1 \cdot \left[ \begin{array}{cccc}
n - 1 \\ m
\end{array}\right]$。\par
下面用$S_1(n, m)$来表示$\left[\begin{array}{cccc}n \\ m\end{array}\right]$\par
\textbf{性质:}\par
\begin{itemize}
\item
\begin{eqnarray*}
n! = \sum\limits_{i = 0}^n S_1(n, i)
\end{eqnarray*} \par
证明:\par
第一类斯特林数的本质是环排列的个数,环的本质可以理解为置换,那么所有第一类斯特林数对应的环排列可以和置换一一对应,所以总数是$n!$。\par
也可以考虑有$n$个点,每个点的入度和出度都为$1$,每次选择一个入度为$0$和出度为$0$的点,将它们连上一条边,那么显然第一次有$n$种选择,第二次有$n - 1$种选择$\cdots$,
所以是$n!$。\par
\end{itemize}
\subsubsection{第二类}
$\left\{\begin{array}{cccc}
n \\ m
\end{array}\right\}$表示将$n$个元素放入$m$个相同盒子里,每个盒子非空的方案数。\par
递推式:
\begin{eqnarray*}
\left\{ \begin{array}{cccc}
n \\ m
\end{array}\right\}
=
\left\{
\begin{array}{cccc}
n - 1 \\
m - 1
\end{array}
\right\}
+ m \cdot
\left\{
\begin{array}{cccc}
n - 1 \\
m
\end{array}
\right\}
\end{eqnarray*}
\par
考虑新加入一个元素是新建一个盒子还是放入原有的盒子即可。\par
下面用$S_2(n, m)$来表示$\left\{\begin{array}{cccc}
n \\ m
\end{array}\right\}$ \par
容斥的计算方法:\par
\begin{eqnarray*}
S_2(n, m) = \frac{1}{m!} \sum\limits_{i = 0}^m (-1)^i {m \choose i}(m - i)^n
\end{eqnarray*} \par
考虑先将盒子进行编号,最后结果除去顺序。考虑有几个盒子为空,枚举出来,然后剩下的元素随便放在非空的盒子里,因为这里算完之后是至少有$i$个盒子为空,所以需要容斥。\par
和自然数幂的关系:\par
\begin{eqnarray*}
m^n = \sum\limits_{i = 0}^m S_2(n, i){m \choose i}i!
\end{eqnarray*} \par
$m^n$可以理解为把$n$个球放到$m$有标号的盒子里,盒子可以为空,现在枚举哪些盒子非空,放进去的方案数就是第二类斯特林数乘阶乘。\par
\subsection{威尔逊定理}
$p$是质数,有:
\begin{eqnarray*}
(p - 1)! \equiv -1 \bmod p
\end{eqnarray*}
\subsection{贝尔数}
贝尔数给出了集合划分的数目,$B_n$表示将$n$个元素进行划分成$1, 2, \cdots n$个集合的方案数。\par
$B_0 = B_1 = 1$,前几项的贝尔数为$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, \cdots$\par
递推公式:\par
\begin{itemize}
\item
\begin{eqnarray*}
B_{n + 1} = \sum\limits_{k = 0}^n {n \choose k} B_k
\end{eqnarray*} \par
\item Dobinski公式:
\begin{eqnarray*}
B_n = \frac{1}{e} \sum\limits_{k = 0}^{\infty} \frac{k^n}{k!}
\end{eqnarray*} \par
\item Touchard同余,若$p$是任意质数,有\par
\begin{eqnarray*}
B_{p + n} = B_n + B_{n + 1} \bmod p
\end{eqnarray*} \par
\item 每个贝尔数都是第二类Stirling数的和:\par
\begin{eqnarray*}
B_n = \sum\limits_{k = 1}^n S(n, k)
\end{eqnarray*} \par
其中第二类Stirling数$S(n, k)$是把基数为$n$的集划分为正好$k$个非空集的方法的数目\par
\item 贝尔函数的质数母函数是:\par
\begin{eqnarray*}
B(x) = \sum\limits_{n = 0}^{\infty} \frac{B_n}{n!}x^n = e^{e^x} - 1
\end{eqnarray*} \par
\end{itemize}
\subsubsection{应用}
\begin{enumerate}
\item 2019ICPC上海网络赛F\par
题意:\par
定义一个长度为$n$的字符串,每个位置需要满足当前位置的大小小于等于它前面那个字母的最大值$+1$,问字典序第$k$大的字符串是多少。\par
思路:\par
其实是个集合划分的字符串表示,方案总是数贝尔数。\par
那么考虑预处理一个$dp$,$f[n][i][j]$表示长度为$n$,当前在第$i$位,最大值为$j$的所有后缀的方案数是多少。\par
那么显然有$f[n][n][j] = 1$,那么考虑倒着推上去。\par
那么有:\par
\begin{eqnarray*}
f[n][i][j] = f[n][i +1][j] * j + f[n][i + 1][j + 1]
\end{eqnarray*}\par
表示下一个字符放$1 - j$的方案数为$f[n][i + 1][j]$,如果放$j + 1$那么其方案数为$f[n][i + 1][j + 1]$\par
然后从左往右逐位确定即可。\par
\end{enumerate}
\subsection{n个球放入m个盒子问题}
$n$个球, $m$个箱子。
\begin{enumerate}
\item 球相同、盒子不同、无空箱\par
\begin{eqnarray*}
f(n, m) =
\left\{
\begin{array}{cccc}
C(n - 1, m - 1) && n \geq m \\
0 && n < m
\end{array}
\right.
\end{eqnarray*} \par
使用插板法:$n$个球中间有$n - 1$个间隙,现在要分成$m$个盒子,不能有空箱子,所以需要在$n - 1$个间隙中选出$m - 1$个间隙。
\item 球相同、盒子不同、允许空箱\par
\begin{eqnarray*}
f(n, m) = C(n + m - 1, m - 1)
\end{eqnarray*} \par
在第一种情况下继续讨论,先假设$m$个盒子里都放好了$1$个球,其实就是现在有$m + n$个相同的球,要放入$m$个不同的箱子,没有空箱的问题。
\item 球不同,盒子相同,无空箱
第二类斯特林数$dp[n][m]$\par
\item 球相同,盒子相同,允许空箱\par
考虑 $\displaystyle f[i][j]$ 表示有$i$个箱子,$j$个小球的方案数。\par
\begin{itemize}
\item 当$i > j$时,总会有$i - j$个盒子空着,所以去掉它们对方案数没有影响,即$f[i][j] = f[j][j]$
\item 否则,分两种情况讨论:
\begin{itemize}
\item 如果至少有一个盒子空着,那么去掉它不影响方案数,即$f[i - 1][j]$
\item 否则,从每个盒子中都去掉一个球,不影响方案数,即$f[i][j - i]$
\end{itemize}
即$\displaystyle f[i][j] = f[i - 1][j] + f[i][j - i]$
\end{itemize}
\end{enumerate}
\subsection{Stern-Brocot 树与 Farey 序列}
\subsubsection{Stern-Brocot 树}
\begin{center}
\includegraphics[scale=0.45]{images/stern-brocot1.png} % 插入图片
\end{center}
第$i$层的序列是深度为$i - 1$的Stern-Brocot 树的中序遍历。\par
\textbf{性质:}
\begin{itemize}
\item 单调性\par
在每一层的序列中,真分数是单调递增的。\par
在满足$\displaystyle \frac{a}{b} \leq \frac{c}{d}$,即要证明$\displaystyle \frac{a}{b} \leq \frac{a + c}{b + d} \leq \frac{c}{d}$。\par
此处只证一边,有$\displaystyle \frac{a}{b} \leq \frac{c}{d} \to ad \leq bc \to ad + ab \leq bc + ab \to \frac{a}{b} \leq \frac{a + c}{b + d}$。\par
\item 最简性\par
序列中的分数(除了$\frac{0}{1}, \frac{1}{0}$), 都是最简分数。\par
\end{itemize}
\subsubsection{Farey 序列}
第$i$个Farey序列记作$F_i$, 表示把分母小于等于$i$的所有最简真分数按大小顺序形成的排列。\par
Farey序列$F_i$是Stern-Brocot第$i - 1$次迭代后的序列的子序列。\par
Farey序列同样满足最简性与单调性,对于序列中连续的三个数$\displaystyle \frac{a}{b}, \frac{x}{y}, \frac{c}{d}$,有$x = a + c, y = b + d$。\par
$F_i$的长度$\displaystyle L_i = 1 + \sum\limits_{k = 1}^i \varphi(k)$。\par
\subsubsection{SPOJ-DIVCNT1}
题意:\par
计算$\displaystyle S(n) = \sum \limits_{i=1}^n d(i)$,其中$d(i)$表示$i$的正因子个数。\par
时间复杂度$O(n^{\frac{1}{3}} \log n)$
\begin{lstlisting}
#include<bits/stdc++.h>
typedef long long ll;
typedef __int128 u128;
using namespace std;
const int N = 1e7 + 5;
namespace DIVCNT {
struct point{
ll x, y;
point(ll _x = 0,ll _y = 0){ x = _x; y = _y; }
point operator + (const point &t) const {
return point(x + t.x, y + t.y);
}
}st[N], L, R, M;
ll n;
inline bool inR(ll x,ll y) { return x * y <= n; }
inline double slope(ll x) { return (double)n / x / x;}
inline u128 gao(ll _n){
n = _n;
u128 ret = 0;
int t = 0, rt = cbrt(n);
st[++t] = point(1, 0);
st[++t] = point(1, 1);
ll m = sqrt(n), x = n / m, y = m + 1;
while (1) {
for (L = st[t--]; !inR(x + L.x, y - L.y); x += L.x, y -= L.y)
ret += x * L.y + (L.y + 1) * (L.x - 1) / 2;
if (y <= rt) break;
for (R = st[t]; inR(x + R.x, y - R.y); R = st[--t]) L = R;
while (1){
M = L + R;
if (!inR(x + M.x, y - M.y)) st[++t] = (R = M);
else {
if (slope(x + M.x) <= (double)R.y / R.x) break;
L = M;
}
}
}
for (int i = 1; i < y; i++) ret += n / i;
return ret * 2 - 1ll * m * m;
}
};
inline void write(u128 x){
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inline void writeln(const u128 &x){
write(x);
putchar('\n');
}
int main(){
int _T; scanf("%d", &_T);
while (_T--) {
ll n;
scanf("%lld", &n);
writeln(DIVCNT::gao(n));
}
return 0;
}
\end{lstlisting}
\subsection{各种表}
\subsubsection{因子个数表}
\begin{itemize}
\item $10^{5}$内, 拥有最大因子个数的数是$83160$, 有$128$个因子
\item $10^{6}$内, 拥有最大因子个数的数是$720720$, 有$240$个因子
\item $10^{7}$内, 拥有最大因子个数的数是$8648640$, 有$448$个因子
\item $10^{8}$内, 拥有最大因子个数的数是$73513440$, 有$768$个因子
\item $10^{9}$内, 拥有最大因子个数的数是$735134400$, 有$1344$个因子
\item $10^{10}$内, 拥有最大因子个数的数是$6983776800$, 有$2304$个因子
\item $10^{11}$内, 拥有最大因子个数的数是$97772875200$, 有$4032$个因子
\item $10^{12}$内, 拥有最大因子个数的数是$963761198400$, 有$6720$个因子
\item $10^{13}$内, 拥有最大因子个数的数是$9316358251200$, 有$10752$个因子
\item $10^{14}$内, 拥有最大因子个数的数是$97821761637600$, 有$17280$个因子
\item $10^{15}$内, 拥有最大因子个数的数是$866421317361600$, 有$26880$个因子
\item $10^{16}$内, 拥有最大因子个数的数是$8086598962041600$, 有$41472$个因子
\item $10^{17}$内, 拥有最大因子个数的数是$74801040398884800$, 有$64512$个因子
\end{itemize}
\section{图论}
\subsection{Dijkstra}
\subsubsection{无向图最小环}
CF 1325E\par
枚举每个起点, 跑$Dijkstra$,对于其中没有状态转移的边,$<u, v>$, 此时$dis[u] + dis[v] + 1$是一个环\par
时间复杂度$O(n^2 \log E)$
\begin{lstlisting}
int pre[N], dis[N], vis[N];
void bfs(int u) {
queue <int> que;
for (int i = 1; i < N; ++i) {
dis[i] = INF;
vis[i] = 0;
pre[i] = 0;
}
pre[u] = u;
dis[u] = 0;
que.push(u);
while (!que.empty()) {
int u = que.front(); que.pop();
for (auto &v : G[u]) {
if (!vis[v] && dis[v] > dis[u] + 1) {
vis[v] = 1;
dis[v] = dis[u] + 1;
pre[v] = u;
que.push(v);
} else {
if (pre[v] != u && pre[u] != v && dis[v] + dis[u] >= 2)
chmin(res, dis[v] + dis[u] + 1);
}
}
}
}
\end{lstlisting}
\subsection{Johnson 全源最短路}
添加一个$0$号点,向其它每个点连一条边权为$0$的边。\par
用$SPFA$以$0$号点为源点跑最短路,记为$h_i$, 加入存在一条从$u$到$v$的边, 边权为$w$的边, 则将该边的边权重新设置为$w + h_u - h_v$\par
再以每个点为起点,跑$n$轮$Dijkstra$即可,算法复杂度$O(nm \log n)$\par
\textbf{正确性证明:}\par
重新标注的图上,一条从$s$到$t$的路径$s \rightarrow p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_k \rightarrow t$的长度为:
\begin{eqnarray*}
(w(s, p_1) + h_s - h_{p_1}) + (w(p_1, p_2) + h_{p_1} - h_{p_2}) + \cdots + (w(p_k, t) + h_{p_k} - h_t)
\end{eqnarray*}
化简后为:
\begin{eqnarray*}
w(s, p_1) + w(p_1, p_2) + \cdots + w(p_k, t) + h_s - h_t
\end{eqnarray*}
所以对于$s \rightarrow t$的所有路径中,$h_s - h_t$的值不变,可以类比物理中的势能。\par
所以新图上的最短路等价于原图的最短路。\par
根据三角形不等式,新图上任意一条边满足$\displaystyle h_v \leq h_u + w(u, v)$,重新标记后为$\displaystyle w'(u, v) = w(u, v) + h_u - h_v \geq 0$,满足非负。\par
洛谷P5905\par
题意:给出$n$个点$m$条边的带权有向图, 求所有点对的最短路径长度, 边权可能非负,图中可能有重边和自环。\par
若图中有负环,输出$-1$\par
$1 \leq n \leq 3 \cdot 10^3, 1 \leq m \leq 6 \cdot 10^3$\par
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e3 + 10, INF = 1e9;
int n, m;
struct Graph {
struct E { int to, nx; ll w; }e[N << 1]; int h[N], cnt;
void init(int n) { for (int i = 0; i <= n; ++i) h[i] = -1; cnt = -1; }
void addedge(int u, int v, ll w = 0) { e[++cnt] = { v, h[u], w}; h[u] = cnt; }
}G;
struct SPFA {
ll dis[N]; int cnt[N]; bool used[N];
// true 没有负环
// false 有负环
bool gao(int s) {
for (int i = 0; i <= n; ++i) {
dis[i] = INF;
cnt[i] = 0;
used[i] = 0;
}
queue <int> que;
dis[s] = 0; used[s] = 1;
que.push(s);
while (!que.empty()) {
int u = que.front(); que.pop();
used[u] = 0;
for (int i = G.h[u]; ~i; i = G.e[i].nx) {
int v = G.e[i].to; ll w = G.e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!used[v]) {
used[v] = 1;
que.push(v);
++cnt[v];
if (cnt[v] == n) return false;
}
}
}
}
return true;
}
}spfa;
struct Dijkstra {
struct node {
int u; ll w;
node(int u = 0, ll w = 0) : u(u), w(w) {}
bool operator < (const node &other) const { return w > other.w; }
};
ll dis[N]; bool used[N];
void gao(int s) {
for (int i = 0; i <= n; ++i) {
dis[i] = INF;
used[i] = 0;
}
priority_queue <node> pq;
dis[s] = 0;
pq.push(node(s, dis[s]));
while (!pq.empty()) {