-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1177 lines (957 loc) · 130 KB
/
index.html
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
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="utf-8" />
<title>Throne</title>
<meta name="author" content="Lxy" />
<meta name="description" content="读一些无用的书，做一些无用的事，花一些无用的时间，都是为了在一切已知之外，保留一个超越自己的机会，人生中一些很了不起的变化，就是来自这种时刻。——梁文道" />
<meta name="keywords" content="" />
<meta
name="viewport"
content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0"
/>
<link rel="icon" href="/images/avatar.webp" />
<link rel="preconnect" href="https://s4.zstatic.net" />
<script src="https://s4.zstatic.net/ajax/libs/vue/3.3.7/vue.global.prod.min.js"></script>
<link rel="stylesheet" href="https://s4.zstatic.net/ajax/libs/font-awesome/6.4.2/css/all.min.css" />
<link rel="preconnect" href="https://fonts.googleapis.cn" />
<link rel="preconnect" href="https://fonts.gstatic.cn" crossorigin />
<link
rel="stylesheet"
href="https://fonts.googleapis.cn/css2?family=Fira+Code:wght@400;500;600;700&family=Lexend:wght@400;500;600;700;800;900&family=Noto+Sans+SC:wght@400;500;600;700;800;900&display=swap"
/>
<script> const mixins = {}; </script>
<script src="https://polyfill.alicdn.com/v3/polyfill.min.js?features=default"></script>
<script src="https://s4.zstatic.net/ajax/libs/highlight.js/11.9.0/highlight.min.js"></script>
<script src="https://s4.zstatic.net/ajax/libs/highlightjs-line-numbers.js/2.8.0/highlightjs-line-numbers.min.js"></script>
<link
rel="stylesheet"
href="https://s4.zstatic.net/ajax/libs/highlight.js/11.9.0/styles/github.min.css"
/>
<script src="/js/lib/highlight.js"></script>
<script src="https://s4.zstatic.net/ajax/libs/KaTeX/0.16.9/katex.min.js"></script>
<script src="https://s4.zstatic.net/ajax/libs/KaTeX/0.16.9/contrib/auto-render.min.js"></script>
<link rel="stylesheet" href="https://s4.zstatic.net/ajax/libs/KaTeX/0.16.9/katex.min.css" />
<script src="/js/lib/math.js"></script>
<script src="/js/lib/preview.js"></script>
<script src="/js/lib/home.js"></script>
<link rel="stylesheet" href="/css/main.css" />
<meta name="generator" content="Hexo 7.1.1"><link rel="alternate" href="/rss2.xml" title="Throne" type="application/rss+xml">
</head>
<body>
<script src="/js/<file>"></script>
<link rel="stylesheet" href="/css/<file>" />
<div id="layout">
<transition name="fade">
<div id="loading" v-show="loading">
<div id="loading-circle">
<h2>LOADING</h2>
<p>加载过慢请开启缓存 浏览器默认开启</p>
<img src="/images/loading.gif" />
</div>
</div>
</transition>
<div id="menu" :class="{ hidden: hiddenMenu, 'menu-color': menuColor}">
<nav id="desktop-menu">
<a class="title" href="/">
<span>THRONE</span>
</a>
<a href="/">
<i class="fa-solid fa-house fa-fw"></i>
<span> Home</span>
</a>
<a href="/about">
<i class="fa-solid fa-id-card fa-fw"></i>
<span> About</span>
</a>
<a href="/archives">
<i class="fa-solid fa-box-archive fa-fw"></i>
<span> Archives</span>
</a>
<a href="/categories">
<i class="fa-solid fa-bookmark fa-fw"></i>
<span> Categories</span>
</a>
<a href="/tags">
<i class="fa-solid fa-tags fa-fw"></i>
<span> Tags</span>
</a>
</nav>
<nav id="mobile-menu">
<div class="title" @click="showMenuItems = !showMenuItems">
<i class="fa-solid fa-bars fa-fw"></i>
<span> THRONE</span>
</div>
<transition name="slide">
<div class="items" v-show="showMenuItems">
<a href="/">
<div class="item">
<div style="min-width: 20px; max-width: 50px; width: 10%">
<i class="fa-solid fa-house fa-fw"></i>
</div>
<div style="min-width: 100px; max-width: 150%; width: 20%">Home</div>
</div>
</a>
<a href="/about">
<div class="item">
<div style="min-width: 20px; max-width: 50px; width: 10%">
<i class="fa-solid fa-id-card fa-fw"></i>
</div>
<div style="min-width: 100px; max-width: 150%; width: 20%">About</div>
</div>
</a>
<a href="/archives">
<div class="item">
<div style="min-width: 20px; max-width: 50px; width: 10%">
<i class="fa-solid fa-box-archive fa-fw"></i>
</div>
<div style="min-width: 100px; max-width: 150%; width: 20%">Archives</div>
</div>
</a>
<a href="/categories">
<div class="item">
<div style="min-width: 20px; max-width: 50px; width: 10%">
<i class="fa-solid fa-bookmark fa-fw"></i>
</div>
<div style="min-width: 100px; max-width: 150%; width: 20%">Categories</div>
</div>
</a>
<a href="/tags">
<div class="item">
<div style="min-width: 20px; max-width: 50px; width: 10%">
<i class="fa-solid fa-tags fa-fw"></i>
</div>
<div style="min-width: 100px; max-width: 150%; width: 20%">Tags</div>
</div>
</a>
</div>
</transition>
</nav>
</div>
<transition name="fade">
<div id="menu-curtain" @click="showMenuItems = !showMenuItems" v-show="showMenuItems"></div>
</transition>
<div id="main" :class="loading ? 'into-enter-from': 'into-enter-active'">
<div id="home-head">
<div
id="home-background"
ref="homeBackground"
data-images="/images/background.webp"
></div>
<div id="home-info" @click="homeClick">
<span class="loop"></span>
<span class="loop"></span>
<span class="loop"></span>
<span class="loop"></span>
<span class="info">
<div class="wrap">
<h1>Throne</h1>
<h3> </h3>
<h5>读一些无用的书，做一些无用的事，花一些无用的时间，都是为了在一切已知之外，保留一个超越自己的机会，人生中一些很了不起的变化，就是来自这种时刻。——梁文道</h5>
</div>
</span>
</div>
</div>
<div
id="home-posts-wrap"
ref="homePostsWrap"
true
>
<div id="home-posts">
<div class="post">
<a href="/2024/10/18/2024CCPC%E6%B7%B1%E5%9C%B3%E7%AB%99%E7%BB%84%E9%98%9F%E8%B5%9B%E9%A2%98%E8%A7%A3/">
<h2 class="post-title">2024CCPC深圳站组队赛题解</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/10/18
</span>
</div>
<div class="description">
<div class="content" v-pre>
<h3 id="a一道好题"><a class="markdownIt-Anchor" href="#a一道好题"></a> A:一道好题</h3>
<h4 id="description"><a class="markdownIt-Anchor" href="#description"></a> Description</h4>
<p>一道好题应该有一个简洁的题面。</p>
<p>有一个长度为 n，初始全为 0 的序列 a，另有一个长度为 n 的序列 b，你希望将 a 变成 b，你可以执行如下两种操作：</p>
<p>1 x：将 a 中所有值为 x 的数 +1。</p>
<p>2 x：将 a 中下标为 x 的数 +1。</p>
<p>你不需要最小化操作次数，但只能使用最多 20000 次操作。</p>
<h4 id="input"><a class="markdownIt-Anchor" href="#input"></a> Input</h4>
<p>第一行一个正整数 n（1≤n≤1000）。</p>
<p>第二行 n 个非负整数 b1,⋯,bn（0≤bi≤n）描述序列 b。</p>
<h4 id="output"><a class="markdownIt-Anchor" href="#output"></a> Output</h4>
<p>第一行一个整数 k 表示操作次数，你需要保证 0≤k≤20000。</p>
<p>之后 k 行每行两个整数 1 x 或 2 x，表示一次操作。对于 1 x 类型的操作，你需要保证 0≤x≤n，对于 2 x 类型的操作，你需要保证 1≤x≤n。</p>
<h4 id="分析"><a class="markdownIt-Anchor" href="#分析"></a> 分析：</h4>
<p>第一次做的时候 各种贪心，分块超次数了。</p>
<p>首先看到操作次数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>20000</mn><mo>></mo><mo>=</mo><mi>n</mi><mo>∗</mo><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">20000>=n*logn</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">2</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">></span></span><span class="base"><span class="strut" style="height:0.36687em;vertical-align:0em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.46528em;vertical-align:0em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">n</span></span></span></span> ，所以可以大约往出来算法运行次数为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">nlogn</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">n</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">n</span></span></span></span> 级别的考虑。</p>
<p>考虑分治。在一段 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>−</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1-n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">n</span></span></span></span> 的区间中，把 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mi mathvariant="normal">/</mi><mn>2</mn><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[(n+1)/2,n]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mord">/</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">n</span><span class="mclose">]</span></span></span></span> 的先依次加一,这样整体就分成了不同两部分，在运用第一种操作整体加一。</p>
<p>具体细节看代码<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi><mi>e</mi><mi>r</mi><mi>g</mi><mi>e</mi></mrow><annotation encoding="application/x-tex">merge</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">m</span><span class="mord mathnormal">e</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">e</span></span></span></span>函数：</p>
<pre class="highlight"><code class="c++"><span class="hljs-type">int</span> n, a[N], c[N];
PII b[N];
vector<array<<span class="hljs-type">int</span>, 2>> op;
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">merge</span><span class="hljs-params">(<span class="hljs-type">int</span> l, <span class="hljs-type">int</span> r, <span class="hljs-type">int</span> val)</span><span class="hljs-comment">//val：此时整个区间的值</span>
</span>{
<span class="hljs-keyword">if</span> (b[r].f == val)
<span class="hljs-keyword">return</span>;
<span class="hljs-type">int</span> mid = l + r + <span class="hljs-number">1</span> >> <span class="hljs-number">1</span>, now = val;
<span class="hljs-keyword">if</span> (b[mid].f > val)
{
<span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = mid; i <= r; i++)
{
op.<span class="hljs-built_in">pb</span>({<span class="hljs-number">2</span>, b[i].s});
}
now++;
}
<span class="hljs-keyword">while</span> (now < b[mid].f)<span class="hljs-comment">//让整个右区间的值变成mid</span>
op.<span class="hljs-built_in">pb</span>({<span class="hljs-number">1</span>, now}), now++;
<span class="hljs-keyword">if</span> (b[r].f > now)
<span class="hljs-built_in">merge</span>(mid, r, now);
<span class="hljs-built_in">merge</span>(l, mid - <span class="hljs-number">1</span>, val);
}
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">solve</span><span class="hljs-params">()</span>
</span>{
cin >> n;
<span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= n; i++)
cin >> a[i], b[i] = {a[i], i};
<span class="hljs-built_in">sort</span>(b + <span class="hljs-number">1</span>, b + <span class="hljs-number">1</span> + n);
<span class="hljs-built_in">merge</span>(<span class="hljs-number">1</span>, n, <span class="hljs-number">0</span>);
cout << op.<span class="hljs-built_in">size</span>() << <span class="hljs-string">"\n"</span>;
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &[x, y] : op)
cout << x << <span class="hljs-string">" "</span> << y << <span class="hljs-string">"\n"</span>;
}
</code></pre>
<h2 id="f见面礼"><a class="markdownIt-Anchor" href="#f见面礼"></a> F:见面礼</h2>
<h4 id="description-2"><a class="markdownIt-Anchor" href="#description-2"></a> Description</h4>
<p>给定一个 n 个点 n 条边的无向图，你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案，使得删去 (x,y) 后图变成一棵树，且这棵树以 p 为根时每个节点的儿子个数均不超过 3。<strong>保证至少存在一种这样的方案。</strong></p>
<h4 id="input-2"><a class="markdownIt-Anchor" href="#input-2"></a> Input</h4>
<p>输入的第一行一个整数 n（2≤n≤105） 表示节点数，接下来 n 行每行两个整数 x,y（1≤x,y≤n） 描述图上的一条边。保证图中没有重边自环。</p>
<h4 id="output-2"><a class="markdownIt-Anchor" href="#output-2"></a> Output</h4>
<p>输出一行一个正整数表示答案。</p>
<h4 id="分析-2"><a class="markdownIt-Anchor" href="#分析-2"></a> 分析：</h4>
<p>队友写的，应该是个结论题。</p>
<p>粘一下官方题解：</p>
<p>由于保证存在一个方案，所以给出的图一定是一棵基环树。找到 基环树的环后，删去的边一定在环上。 枚举被删去的边（也就是环上的边），我们需要快速地确定选根 的方案数。 考虑一个点作为根的条件。注意到每个点的儿子个数不超过3的 充要条件是：根的度数不超过3，其余节点的度数不超过4。 于是维护每种度数的出现次数（注意到保证有解时，所有节点的 度数均不会超过5），删边时修改相邻的两个节点的度数。当不 存在度数为5的节点时，选根的方案数即为度数不超过3的节 点个数，否则不存在选根的方案。</p>
<pre class="highlight"><code class="c++"><span class="hljs-type">int</span> T, n, m;
vector<<span class="hljs-type">int</span>>v[N];
<span class="hljs-type">int</span> p[N], ff = <span class="hljs-number">0</span>, q[N], cnt = <span class="hljs-number">0</span>;
<span class="hljs-type">bool</span> st[N];
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-type">int</span> u, <span class="hljs-type">int</span> f)</span>
</span>{
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> it : v[u])
{
<span class="hljs-keyword">if</span>(it == f) <span class="hljs-keyword">continue</span>;
<span class="hljs-keyword">if</span>(ff) <span class="hljs-keyword">return</span>;
p[it] = u;
<span class="hljs-comment">// cout << it << '\n';</span>
<span class="hljs-keyword">if</span>(st[it])
{
<span class="hljs-comment">// cout << " ---" << it << '\n';</span>
<span class="hljs-type">int</span> x = it;
<span class="hljs-keyword">while</span>(p[x] != it && p[x] != <span class="hljs-number">0</span>)
{
q[++ cnt] = p[x];
x = p[x];
}
q[++ cnt] = p[x];
<span class="hljs-comment">// for(int i = 1; i <= cnt; i ++)</span>
<span class="hljs-comment">// {</span>
<span class="hljs-comment">// cout << q[i] <<" \n"[i == cnt];</span>
<span class="hljs-comment">// }</span>
ff = <span class="hljs-number">1</span>;
<span class="hljs-keyword">return</span>;
}
st[it] = <span class="hljs-literal">true</span>;
<span class="hljs-built_in">dfs</span>(it, u);
<span class="hljs-keyword">if</span>(ff) <span class="hljs-keyword">return</span>;
}
}
<span class="hljs-type">int</span> num[N];
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">solve</span><span class="hljs-params">()</span>
</span>{
cin >> n;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= n; i ++)
{
<span class="hljs-type">int</span> x, y;
cin >> x >> y;
v[x].<span class="hljs-built_in">push_back</span>(y);
v[y].<span class="hljs-built_in">push_back</span>(x);
num[x] ++;
num[y] ++;
}
<span class="hljs-built_in">dfs</span>(<span class="hljs-number">1</span>, <span class="hljs-number">0</span>);
q[cnt + <span class="hljs-number">1</span>] = q[<span class="hljs-number">1</span>];
<span class="hljs-type">int</span> cnt1 = <span class="hljs-number">0</span>, cnt2 = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= n; i ++)
{
<span class="hljs-keyword">if</span>(num[i] == <span class="hljs-number">5</span>) cnt1 ++;
<span class="hljs-keyword">if</span>(num[i] == <span class="hljs-number">4</span>) cnt2 ++;
}
<span class="hljs-type">int</span> ans = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= cnt; i ++)
{
<span class="hljs-type">int</span> t1 = q[i], t2 = q[i + <span class="hljs-number">1</span>];
<span class="hljs-type">int</span> n1 = <span class="hljs-number">0</span>, n2 = <span class="hljs-number">0</span>;
<span class="hljs-keyword">if</span>(num[t1] == <span class="hljs-number">5</span>) n1 ++, n2 --;
<span class="hljs-keyword">if</span>(num[t1] == <span class="hljs-number">4</span>) n2 ++;
<span class="hljs-keyword">if</span>(num[t2] == <span class="hljs-number">5</span>) n1 ++, n2 --;
<span class="hljs-keyword">if</span>(num[t2] == <span class="hljs-number">4</span>) n2 ++;
<span class="hljs-keyword">if</span>(cnt1 - n1 != <span class="hljs-number">0</span>) <span class="hljs-keyword">continue</span>;
ans += n - (cnt2 - n2);
}
cout << ans << <span class="hljs-string">'\n'</span>;
}
</code></pre>
<h2 id="g相似基因序列问题"><a class="markdownIt-Anchor" href="#g相似基因序列问题"></a> G:相似基因序列问题</h2>
<p><strong>【题目描述】</strong></p>
<p>已知一棵包含了 N 个生物的系统进化树，这些生物的 DNA 序列对应的对齐至 M 个片段的序列可以用仅含小写字母的字符串表示为 s1,…,sN。在这棵系统进化树上，如果两个生物对应的序列最多只有 K 处对应位置上的片段不相同（即对应字母不同），就称这两个生物的亲缘关系相近。</p>
<p>现有 Q 个尚未确定亲缘关系的生物，对齐得到序列分别为 t1,…,tQ。为了确定这些生物在系统进化树上的位置，请对 Q 个生物分别求出，原树中有多少个生物与其亲缘关系相近。</p>
<h4 id="input-3"><a class="markdownIt-Anchor" href="#input-3"></a> Input</h4>
<p>输入的第一行包含四个正整数 N,Q,M,K，分别表示系统进化树上的生物数量、待确定亲缘关系的生物数量、对齐后的序列长度和比较序列时容许的最大差异数。保证 1≤N,Q≤300，1≤M≤60,000，1≤K≤10。</p>
<p>接下来 N 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 si，表示系统进化树上的每个生物对应的模板序列。</p>
<p>接下来 Q 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 tj，表示待确定亲缘关系的每个生物对应的查询序列。</p>
<p>保证输入的两个字符串均仅包含小写字母。</p>
<h4 id="output-3"><a class="markdownIt-Anchor" href="#output-3"></a> Output</h4>
<p>输出共 Q 行，其中第 j 行输出一个非负整数，表示在系统进化树上与第 j 个待确定的生物亲缘关系相近的生物数量。</p>
<p>分析：</p>
<p>队友写的二分+hash。</p>
<p>中途我怕被卡hash跟他们说写双hash，mle了，改完单hash又tle一发 ，二分提前break过的。</p>
<pre class="highlight"><code class="c++"><span class="hljs-type">int</span> q, k, T, n, m;
string s[N], c[N];
<span class="hljs-type">const</span> <span class="hljs-type">int</span> mod = <span class="hljs-number">1e9</span> + <span class="hljs-number">13</span>, mod2 = <span class="hljs-number">1e9</span> + <span class="hljs-number">17</span>;
<span class="hljs-type">const</span> <span class="hljs-type">int</span> P = <span class="hljs-number">131</span>, P2 = <span class="hljs-number">13331</span>;
<span class="hljs-type">int</span> h[N][M], hc[N][M], p[M];
<span class="hljs-comment">// int h2[N][M], hc2[N][M], p2[M];</span>
<span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">check</span><span class="hljs-params">(<span class="hljs-type">int</span> l, <span class="hljs-type">int</span> r, <span class="hljs-type">int</span> t1, <span class="hljs-type">int</span> t2)</span>
</span>{
<span class="hljs-type">int</span> x1 = (hc[t1][r] - hc[t1][l - <span class="hljs-number">1</span>] * p[r - l + <span class="hljs-number">1</span>] % mod + mod) % mod;
<span class="hljs-type">int</span> x2 = (h[t2][r] - h[t2][l - <span class="hljs-number">1</span>] * p[r - l + <span class="hljs-number">1</span>] % mod + mod) % mod;
<span class="hljs-comment">// int y1 = (hc2[t1][r] - hc2[t1][l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;</span>
<span class="hljs-comment">// int y2 = (h2[t2][r] - h2[t2][l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;</span>
<span class="hljs-keyword">if</span>(x1 == x2) <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
}
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">solve</span><span class="hljs-params">()</span>
</span>{
cin >> n >> q >> m >> k;
p[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>;
<span class="hljs-comment">// p2[0] = 1;</span>
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= m; i ++)
{
p[i] = p[i - <span class="hljs-number">1</span>] * P % mod;
<span class="hljs-comment">// p2[i] = p2[i - 1] * P2 % mod2;</span>
}
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= n; i ++)
{
cin >> s[i];
<span class="hljs-type">int</span> z = s[i].<span class="hljs-built_in">size</span>();
s[i] = <span class="hljs-string">' '</span> + s[i];
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> j = <span class="hljs-number">1</span>; j <= z; j ++)
{
h[i][j] = (h[i][j - <span class="hljs-number">1</span>] * P % mod + s[i][j]) % mod;
<span class="hljs-comment">// h2[i][j] = (h2[i][j - 1] * P2 % mod2 + s[i][j]) % mod2;</span>
}
}
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i <= q; i ++)
{
cin >> c[i];
<span class="hljs-type">int</span> z = c[i].<span class="hljs-built_in">size</span>();
c[i] = <span class="hljs-string">' '</span> + c[i];
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> j = <span class="hljs-number">1</span>; j <= z; j ++)
{
hc[i][j] = (hc[i][j - <span class="hljs-number">1</span>] * P % mod + c[i][j]) % mod;
<span class="hljs-comment">// hc2[i][j] = (hc2[i][j - 1] * P2 % mod2 + c[i][j]) % mod2;</span>
}
<span class="hljs-type">int</span> ans = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> j = <span class="hljs-number">1</span>; j <= n; j ++)
{
<span class="hljs-type">int</span> lr = <span class="hljs-number">1</span>, cnt = <span class="hljs-number">0</span>;
<span class="hljs-keyword">while</span>(lr <= m)
{
<span class="hljs-type">int</span> l = lr, r = m;
<span class="hljs-keyword">while</span>(l < r)
{
<span class="hljs-type">int</span> mid = l + r >> <span class="hljs-number">1</span>;
<span class="hljs-keyword">if</span>(<span class="hljs-built_in">check</span>(l, mid, i, j)) l = mid + <span class="hljs-number">1</span>;
<span class="hljs-keyword">else</span> r = mid;
}
<span class="hljs-keyword">if</span>(c[i][l] != s[j][l])
{
cnt ++;
}
lr = l + <span class="hljs-number">1</span>;
<span class="hljs-keyword">if</span>(cnt > k) <span class="hljs-keyword">break</span>;
}
<span class="hljs-keyword">if</span>(cnt <= k) ans ++;
}
cout << ans << <span class="hljs-string">'\n'</span>;
}
}
</code></pre>
<h2 id="description-3"><a class="markdownIt-Anchor" href="#description-3"></a> Description</h2>
<p><strong>【题目描述】</strong></p>
<p>出生于魔王家族的 Mary，从小便与同龄的普通人类有所不同。比如说，Mary 的头两侧长有一对犄角，可以捕捉到远处细微的变化；比如说，Mary 身上的魔力会吸引神秘的生物，这些友善的来客自在地游曳在魔王城中，将其点缀成了一座坐落于偏僻孤岛上的水族馆；再比如，Mary 有一棵与生俱来的有根树。</p>
<p>Mary 有棵有根树。</p>
<p>在 Mary 出生时，这棵有根树也一同降临在了世界上。照料好自己的有根树是魔王家族世世代代的传承，但让有根树生长的方法却因人而异。Mary 不知道如何让这棵只有一个结点的有根树生长，而她的父母也不得而知。虽然 Mary 的有根树从未生长，但是 Mary 像普通人类一样不断成长，她所能驾驭的魔力也随之越来越强。Mary 的成长获得了父母的认可，他们将魔王家族中象征着力量成熟的魔法——闪耀魔法传授给了 Mary。当 Mary 第一次成功施展了闪耀魔法时，她的有根树终于产生了变化：从原来的根结点上，长出了 M 个新的结点。原来，每当 Mary 施展一次闪耀魔法时，她的有根树都会有一个叶结点恰好长出 M 个<strong>可以区分的</strong>子结点。每次进行生长的叶结点是在所有尚未生长的叶结点中等概率随机产生的，而已经拥有 M 个子结点的非叶结点不会再次生长。</p>
<p>Mary 想知道：在她总共使用了 K 次闪耀魔法之后，她的有根树上各个结点的深度总和的期望。最初没有使用闪耀魔法时，只有一个结点的有根树的深度定义为 0。</p>
<h4 id="input-4"><a class="markdownIt-Anchor" href="#input-4"></a> Input</h4>
<p>输入仅一行，包括两个由单个空格隔开的正整数 M，K，表示从一个结点上可以长出的子结点的数量，以及使用闪耀魔法的次数。保证 1≤M≤100，1≤K≤107。</p>
<h4 id="output-4"><a class="markdownIt-Anchor" href="#output-4"></a> Output</h4>
<p>输出一个数，表示 Mary 的有根树的结点深度和的期望。假设期望深度和化为最简分式后的形式为 p/q（即其中 p,q 互质），请输出非负整数 x 使得 qx≡p(mod1,000,000,009)，且 0≤x<1,000,000,009。可以证明，在本题数据范围下，x 存在且唯一。</p>
<h4 id="分析-3"><a class="markdownIt-Anchor" href="#分析-3"></a> 分析：</h4>
<p>设<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>f</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">f_1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>表示叶子节点深度的全部期望，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>f</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">f_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>表示非叶子节点深度的全部期望。</p>
<p>在进行一次闪耀魔法时：</p>
<p>全部叶子的节点数量:<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi><msub><mi>z</mi><mi>i</mi></msub><mo>=</mo><mi>s</mi><msub><mi>z</mi><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>m</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">sz_i=sz_{i-1}+m-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord mathnormal">s</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.04398em;">z</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.04398em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.791661em;vertical-align:-0.208331em;"></span><span class="mord mathnormal">s</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.04398em;">z</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.04398em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.208331em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span></p>
<p>一个叶子节点的期望深度:d=<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><msub><mi>f</mi><mn>1</mn></msub><mrow><mi>s</mi><msub><mi>z</mi><mi>i</mi></msub></mrow></mfrac></mrow><annotation encoding="application/x-tex">\frac{f_1}{sz_i}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.377316em;vertical-align:-0.44509999999999994em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.9322159999999999em;"><span style="top:-2.655em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">s</span><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.04398em;">z</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3280857142857143em;"><span style="top:-2.357em;margin-left:-0.04398em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.143em;"><span></span></span></span></span></span></span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.446108em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31731428571428577em;"><span style="top:-2.357em;margin-left:-0.10764em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.143em;"><span></span></span></span></span></span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.44509999999999994em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span></p>
<p>显然会有一个叶子节点变为非叶子节点：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>f</mi><mn>2</mn></msub><mo>+</mo><mo>=</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">f_2+=d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord">+</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">d</span></span></span></span></p>
<p>新的叶子节点一定是上一次的叶子节点期望深度+1：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>+</mo><mo>=</mo><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mo>∗</mo><mi>m</mi><mo>−</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">f_1+=(d+1)*m-d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord">+</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">d</span></span></span></span></p>
<p>那么对于最终的答案就是<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>f</mi><mn>1</mn></msub><mo>+</mo><msub><mi>f</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">f_1+f_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.10764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>.</p>
<pre class="highlight"><code class="c++"><span class="hljs-type">int</span> f1[N],f2[N];
<span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">qmi</span><span class="hljs-params">(<span class="hljs-type">int</span> a,<span class="hljs-type">int</span> b)</span></span>{
<span class="hljs-type">int</span> res=<span class="hljs-number">1</span>;
<span class="hljs-keyword">while</span>(b){
<span class="hljs-keyword">if</span>(b&<span class="hljs-number">1</span>)res=res*a%P;
a=a*a%P;
b>>=<span class="hljs-number">1</span>;
}
<span class="hljs-keyword">return</span> res;
}
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">solve</span><span class="hljs-params">()</span></span>{
<span class="hljs-type">int</span> m,k;cin>>m>>k;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i=<span class="hljs-number">1</span>,sum=<span class="hljs-number">1</span>;i<=k;i++,sum+=m<span class="hljs-number">-1</span>,sum%=P){
<span class="hljs-type">int</span> ver=f1[i<span class="hljs-number">-1</span>]*<span class="hljs-built_in">qmi</span>(sum,P<span class="hljs-number">-2</span>)%P;
f2[i]=f2[i<span class="hljs-number">-1</span>]+ver;
f2[i]%=P;
f1[i]=(f1[i<span class="hljs-number">-1</span>]+(ver+<span class="hljs-number">1</span>)*m%P-ver+P)%P;
}
cout<<(f1[k]+f2[k])%P<<<span class="hljs-string">"\n"</span>;
}
</code></pre>
<h2 id="i不定方程"><a class="markdownIt-Anchor" href="#i不定方程"></a> I：不定方程</h2>
<h4 id="description-4"><a class="markdownIt-Anchor" href="#description-4"></a> Description</h4>
<p>给定正整数 n,k，求不定方程 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>a</mi><mi>k</mi></msup><mtext>−</mtext><msup><mi>b</mi><mi>k</mi></msup><mo>=</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">a^k−b^k=n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.932438em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord mathnormal">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mord">−</span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">n</span></span></span></span> 的正整数解数量。</p>
<h4 id="input-5"><a class="markdownIt-Anchor" href="#input-5"></a> Input</h4>
<p>输入第一行一个整数 T（1≤T≤20） 表示询问数量。之后 T 行，每一行两个整数 n,k 表示一次询问。保证 1≤n≤1018，3≤k≤64。</p>
<h4 id="output-5"><a class="markdownIt-Anchor" href="#output-5"></a> Output</h4>
<p>对于每一组询问，输出一行一个非负整数表示答案。</p>
<h4 id="分析-4"><a class="markdownIt-Anchor" href="#分析-4"></a> 分析：</h4>
<h5 id="正解"><a class="markdownIt-Anchor" href="#正解"></a> 正解：</h5>
<h5 id="偏解"><a class="markdownIt-Anchor" href="#偏解"></a> 偏解：</h5>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>a</mi><mi>k</mi></msup><mo>−</mo><msup><mi>b</mi><mi>k</mi></msup><mo>=</mo><mo stretchy="false">(</mo><mi>a</mi><mo>−</mo><mi>b</mi><mo stretchy="false">)</mo><mo stretchy="false">(</mo><msup><mi>a</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><msup><mi>a</mi><mrow><mi>k</mi><mo>−</mo><mn>2</mn></mrow></msup><mi>b</mi><mo>+</mo><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><msup><mi>b</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>=</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+...b^{k-1}=n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.932438em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord mathnormal">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.0991079999999998em;vertical-align:-0.25em;"></span><span class="mord mathnormal">b</span><span class="mclose">)</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.9324379999999999em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord mathnormal">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span><span class="mbin mtight">−</span><span class="mord mtight">2</span></span></span></span></span></span></span></span></span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8491079999999999em;vertical-align:0em;"></span><span class="mord">.</span><span class="mord">.</span><span class="mord">.</span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">n</span></span></span></span></p>
<p>设<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo>=</mo><mo stretchy="false">(</mo><mi>a</mi><mo>−</mo><mi>b</mi><mo stretchy="false">)</mo><mo separator="true">,</mo><mi>a</mi><mo>=</mo><mi>b</mi><mo>+</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">c=(a-b),a=b+c</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">c</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">b</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">c</span></span></span></span> 带入原式：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>b</mi><mo>+</mo><mi>c</mi><msup><mo stretchy="false">)</mo><mi>k</mi></msup><mo>−</mo><msup><mi>b</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">(b+c)^k-b^k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.099108em;vertical-align:-0.25em;"></span><span class="mord mathnormal">c</span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span></span></span></span></p>
<p>首先通过第一行可以看出（a-b）是n的质因子，其次<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>b</mi><mo>+</mo><mi>c</mi><msup><mo stretchy="false">)</mo><mi>k</mi></msup><mo>−</mo><msup><mi>b</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">(b+c)^k-b^k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.099108em;vertical-align:-0.25em;"></span><span class="mord mathnormal">c</span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span></span></span></span> 显然单调递增</p>
<p>所以我们可以枚举n的因子，然后二分答案寻找b</p>
<p>由于n很大我们可以用<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>P</mi><mi>o</mi><mi>l</mi><mi>l</mi><mi>a</mi><mi>r</mi><mi>d</mi><mo>−</mo><mi>R</mi><mi>h</mi><mi>o</mi></mrow><annotation encoding="application/x-tex">Pollard-Rho</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathnormal" style="margin-right:0.13889em;">P</span><span class="mord mathnormal">o</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">a</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal" style="margin-right:0.00773em;">R</span><span class="mord mathnormal">h</span><span class="mord mathnormal">o</span></span></span></span>在<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mfrac><mn>1</mn><mn>4</mn></mfrac></msup></mrow><annotation encoding="application/x-tex">n^{\frac{1}{4}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9540200000000001em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.9540200000000001em;"><span style="top:-3.363em;margin-right:0.05em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mopen nulldelimiter sizing reset-size3 size6"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8443142857142858em;"><span style="top:-2.656em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mtight">4</span></span></span></span><span style="top:-3.2255000000000003em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line mtight" style="border-bottom-width:0.049em;"></span></span><span style="top:-3.384em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.344em;"><span></span></span></span></span></span><span class="mclose nulldelimiter sizing reset-size3 size6"></span></span></span></span></span></span></span></span></span></span></span></span></span>枚举单个因子 ，带回除掉再找其他的因子。</p>
</div>
</div>
<div class="post-tags">
</div>
<a href="/2024/10/18/2024CCPC%E6%B7%B1%E5%9C%B3%E7%AB%99%E7%BB%84%E9%98%9F%E8%B5%9B%E9%A2%98%E8%A7%A3/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/09/16/%E8%A1%A5%E9%A2%98/">
<h2 class="post-title">补题</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/9/16
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p>[P2508 <a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P2508">HAOI2008] 圆上的整点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)</a></p>
<p>分析：</p>
<p>$y<sup>2=r</sup>2-x^2=(r-x)(r+x) $</p>
<p>设<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>d</mi><mo>=</mo><mi>g</mi><mi>c</mi><mi>d</mi><mo stretchy="false">(</mo><mi>r</mi><mo>−</mo><mi>x</mi><mo separator="true">,</mo><mi>r</mi><mo>+</mo><mi>x</mi><mo stretchy="false">)</mo><mo separator="true">,</mo><mi>r</mi><mo>−</mo><mi>x</mi><mo>=</mo><mi>u</mi><mo>∗</mo><mi>d</mi><mo separator="true">,</mo><mi>r</mi><mo>+</mo><mi>x</mi><mo>=</mo><mi>v</mi><mo>∗</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">d=gcd(r-x,r+x),r-x=u*d,r+x=v*d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mord mathnormal">c</span><span class="mord mathnormal">d</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.7777700000000001em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">x</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.46528em;vertical-align:0em;"></span><span class="mord mathnormal">u</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">d</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.46528em;vertical-align:0em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">d</span></span></span></span></p>
<p>则原式变为：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>y</mi><mn>2</mn></msup><mo>=</mo><msup><mi>d</mi><mn>2</mn></msup><mo>∗</mo><mi>u</mi><mo>∗</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">y^2=d^2*u*v</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.008548em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03588em;">y</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">d</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.46528em;vertical-align:0em;"></span><span class="mord mathnormal">u</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span></span></span></span></p>
<p>则可以列出两个等式：</p>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>=</mo><mfrac><mrow><mi>v</mi><mo>−</mo><mi>u</mi></mrow><mn>2</mn></mfrac><mi>d</mi><mo separator="true">,</mo><mn>2</mn><mi>r</mi><mo>=</mo><mo stretchy="false">(</mo><mrow><mi>u</mi><mo>+</mo><mi>v</mi></mrow><mo stretchy="false">)</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">x=\frac{v-u}{2}d,2r=({u+v})d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.1473309999999999em;vertical-align:-0.345em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.802331em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03588em;">v</span><span class="mbin mtight">−</span><span class="mord mathnormal mtight">u</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mord mathnormal">d</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">u</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span></span><span class="mclose">)</span><span class="mord mathnormal">d</span></span></span></span></p>
<p>枚举2r的约数d并枚举u可以在<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>o</mi><mo stretchy="false">(</mo><msqrt><mi>r</mi></msqrt><mo>+</mo><mo>∑</mo><mfrac><mrow><mn>2</mn><mi>r</mi></mrow><mi>d</mi></mfrac><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">o(\sqrt{r}+\sum\frac{2r}{d})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.05028em;vertical-align:-0.25em;"></span><span class="mord mathnormal">o</span><span class="mopen">(</span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8002800000000001em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord mathnormal" style="margin-right:0.02778em;">r</span></span></span><span style="top:-2.76028em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702
c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14
c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54
c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10
s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429
c69,-144,104.5,-217.7,106.5,-221
l0 -0
c5.3,-9.3,12,-14,20,-14
H400000v40H845.2724
s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7
c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z
M834 80h400000v40h-400000z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.23972em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.190108em;vertical-align:-0.345em;"></span><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.845108em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">d</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mord mathnormal mtight" style="margin-right:0.02778em;">r</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">)</span></span></span></span>解决该问题，显然时间复杂度不能接受</p>
<p>注意到u,v互质并且等式左边为平方数则u,v为平方数：</p>
<p>不妨设<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>u</mi><mo>=</mo><msup><mi>s</mi><mn>2</mn></msup><mo separator="true">,</mo><mi>v</mi><mo>=</mo><msup><mi>t</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">u=s^2,v=t^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">u</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.008548em;vertical-align:-0.19444em;"></span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathnormal">t</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></p>
<p>则等式变为：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>=</mo><mfrac><mrow><msup><mi>t</mi><mn>2</mn></msup><mo>−</mo><msup><mi>s</mi><mn>2</mn></msup></mrow><mn>2</mn></mfrac><mi>d</mi><mo separator="true">,</mo><mn>2</mn><mi>r</mi><mo>=</mo><mo stretchy="false">(</mo><msup><mi>s</mi><mn>2</mn></msup><mo>+</mo><msup><mi>t</mi><mn>2</mn></msup><mo stretchy="false">)</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">x=\frac{t^2-s^2}{2}d,2r=(s^2+t^2)d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.36292em;vertical-align:-0.345em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.01792em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathnormal mtight">t</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8913142857142857em;"><span style="top:-2.931em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mbin mtight">−</span><span class="mord mtight"><span class="mord mathnormal mtight">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8913142857142857em;"><span style="top:-2.931em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mord mathnormal">d</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mord mathnormal" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal">t</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span><span class="mord mathnormal">d</span></span></span></span></p>
<p>此时枚举2r的约束d并枚举s可以在<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>o</mi><mo stretchy="false">(</mo><msqrt><mi>r</mi></msqrt><mo>+</mo><mo>∑</mo><msqrt><mfrac><mrow><mn>2</mn><mi>r</mi></mrow><mi>d</mi></mfrac></msqrt><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">o(\sqrt{r}+\sum \sqrt\frac{2r}{d})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.05028em;vertical-align:-0.25em;"></span><span class="mord mathnormal">o</span><span class="mopen">(</span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8002800000000001em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord mathnormal" style="margin-right:0.02778em;">r</span></span></span><span style="top:-2.76028em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702
c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14
c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54
c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10
s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429
c69,-144,104.5,-217.7,106.5,-221
l0 -0
c5.3,-9.3,12,-14,20,-14
H400000v40H845.2724
s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7
c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z
M834 80h400000v40h-400000z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.23972em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.84em;vertical-align:-0.604946em;"></span><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.235054em;"><span class="svg-align" style="top:-3.8em;"><span class="pstrut" style="height:3.8em;"></span><span class="mord" style="padding-left:1em;"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.845108em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">d</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mord mathnormal mtight" style="margin-right:0.02778em;">r</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span><span style="top:-3.195054em;"><span class="pstrut" style="height:3.8em;"></span><span class="hide-tail" style="min-width:1.02em;height:1.8800000000000001em;"><svg width='400em' height='1.8800000000000001em' viewBox='0 0 400000 1944' preserveAspectRatio='xMinYMin slice'><path d='M983 90
l0 -0
c4,-6.7,10,-10,18,-10 H400000v40
H1013.1s-83.4,268,-264.1,840c-180.7,572,-277,876.3,-289,913c-4.7,4.7,-12.7,7,-24,7
s-12,0,-12,0c-1.3,-3.3,-3.7,-11.7,-7,-25c-35.3,-125.3,-106.7,-373.3,-214,-744
c-10,12,-21,25,-33,39s-32,39,-32,39c-6,-5.3,-15,-14,-27,-26s25,-30,25,-30
c26.7,-32.7,52,-63,76,-91s52,-60,52,-60s208,722,208,722
c56,-175.3,126.3,-397.3,211,-666c84.7,-268.7,153.8,-488.2,207.5,-658.5
c53.7,-170.3,84.5,-266.8,92.5,-289.5z
M1001 80h400000v40h-400000z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.604946em;"><span></span></span></span></span></span><span class="mclose">)</span></span></span></span>求解</p>
<p>r数的约数可以粗略估计为<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mn>10</mn></msup></mrow><annotation encoding="application/x-tex">2^{10}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">0</span></span></span></span></span></span></span></span></span></span></span></span>最大不会超过r，所以最大时间复杂度为<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>o</mi><mo stretchy="false">(</mo><msqrt><mi>r</mi></msqrt><mo>∗</mo><msup><mn>2</mn><mn>10</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">o(\sqrt{r}*2^{10})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.05028em;vertical-align:-0.25em;"></span><span class="mord mathnormal">o</span><span class="mopen">(</span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8002800000000001em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord mathnormal" style="margin-right:0.02778em;">r</span></span></span><span style="top:-2.76028em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702
c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14
c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54
c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10
s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429
c69,-144,104.5,-217.7,106.5,-221
l0 -0
c5.3,-9.3,12,-14,20,-14
H400000v40H845.2724
s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7
c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z
M834 80h400000v40h-400000z'/></svg></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.23972em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">0</span></span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span> 约为<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>∗</mo><mn>1</mn><msup><mn>0</mn><mn>7</mn></msup></mrow><annotation encoding="application/x-tex">3*10^7</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">7</span></span></span></span></span></span></span></span></span></span></span></p>
<p>(实际远比这个小)</p>
<pre class="highlight"><code class="c++"><span class="hljs-type">int</span> ans,R;
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">get</span><span class="hljs-params">(<span class="hljs-type">int</span> d,<span class="hljs-type">int</span> r)</span></span>{
<span class="hljs-comment">// cout<<d<<" "<<r<<"\n";</span>
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i=<span class="hljs-number">1</span>;i<=r/i;i++){
<span class="hljs-type">int</span> s=i,t=<span class="hljs-built_in">sqrt</span>(r-i*i);
<span class="hljs-keyword">if</span>(s*s+t*t!=r||__gcd(s,t)!=<span class="hljs-number">1</span>)<span class="hljs-keyword">continue</span>;
<span class="hljs-type">int</span> x=(t*t-s*s)/<span class="hljs-number">2</span>*d,y=d*s*t;
<span class="hljs-comment">// cout<<x<<" "<<y<<"\n";</span>
<span class="hljs-keyword">if</span>(x><span class="hljs-number">0</span>&&y><span class="hljs-number">0</span>&&x*x+y*y==(R/<span class="hljs-number">2</span>)*(R/<span class="hljs-number">2</span>))ans+=<span class="hljs-number">2</span>;
}
}
<span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">solve</span><span class="hljs-params">()</span></span>{
<span class="hljs-type">int</span> r;cin>>r;
r<<=<span class="hljs-number">1</span>;
R=r;
<span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i=<span class="hljs-number">1</span>;i<=r/i;i++){
<span class="hljs-keyword">if</span>(r%i==<span class="hljs-number">0</span>)<span class="hljs-built_in">get</span>(i,r/i);
<span class="hljs-keyword">if</span>(r%i==<span class="hljs-number">0</span>&&i*i!=r)<span class="hljs-built_in">get</span>(r/i,r/(r/i));
}
cout<<(ans+<span class="hljs-number">1</span>)*<span class="hljs-number">4</span><<<span class="hljs-string">"\n"</span>;
}
</code></pre>
</div>
</div>
<div class="post-tags">
</div>
<a href="/2024/09/16/%E8%A1%A5%E9%A2%98/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/09/13/%E6%95%B0%E4%BD%8DDP/">
<h2 class="post-title">数位DP</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/9/13
</span>
</div>
<div class="description">
<div class="content" v-pre>
<h1 id="zjoi2010-数字计数"><a class="markdownIt-Anchor" href="#zjoi2010-数字计数"></a> [ZJOI2010] 数字计数</h1>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>给定两个正整数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi></mrow><annotation encoding="application/x-tex">a</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">a</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal">b</span></span></span></span>，求在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord mathnormal">a</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">b</span><span class="mclose">]</span></span></span></span> 中的所有整数中，每个数码(digit)各出现了多少次。</p>
<h2 id="输入格式"><a class="markdownIt-Anchor" href="#输入格式"></a> 输入格式</h2>
<p>仅包含一行两个整数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>b</mi></mrow><annotation encoding="application/x-tex">a,b</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathnormal">a</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">b</span></span></span></span>，含义如上所述。</p>
<h2 id="输出格式"><a class="markdownIt-Anchor" href="#输出格式"></a> 输出格式</h2>
<p>包含一行十个整数，分别表示 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>∼</mo><mn>9</mn></mrow><annotation encoding="application/x-tex">0\sim 9</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∼</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">9</span></span></span></span> 在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord mathnormal">a</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathnormal">b</span><span class="mclose">]</span></span></span></span> 中出现了多少次。</p>
<h2 id="样例-1"><a class="markdownIt-Anchor" href="#样例-1"></a> 样例 #1</h2>
<h3 id="样例输入-1"><a class="markdownIt-Anchor" href="#样例输入-1"></a> 样例输入 #1</h3>
<pre class="highlight"><code class="">1 99
</code></pre>
<h3 id="样例输出-1"><a class="markdownIt-Anchor" href="#样例输出-1"></a> 样例输出 #1</h3>
<pre class="highlight"><code class="">9 20 20 20 20 20 20 20 20 20
</code></pre>
<h2 id="提示"><a class="markdownIt-Anchor" href="#提示"></a> 提示</h2>
<h4 id="数据规模与约定"><a class="markdownIt-Anchor" href="#数据规模与约定"></a> 数据规模与约定</h4>
<ul>
<li>对于 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>30</mn><mi mathvariant="normal">%</mi></mrow><annotation encoding="application/x-tex">30\%</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.80556em;vertical-align:-0.05556em;"></span><span class="mord">3</span><span class="mord">0</span><span class="mord">%</span></span></span></span> 的数据，保证 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo>≤</mo><mi>b</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>6</mn></msup></mrow><annotation encoding="application/x-tex">a\le b\le10^6</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83041em;vertical-align:-0.13597em;"></span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">6</span></span></span></span></span></span></span></span></span></span></span>；</li>
<li>对于 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mi mathvariant="normal">%</mi></mrow><annotation encoding="application/x-tex">100\%</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.80556em;vertical-align:-0.05556em;"></span><span class="mord">1</span><span class="mord">0</span><span class="mord">0</span><span class="mord">%</span></span></span></span> 的数据，保证 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>a</mi><mo>≤</mo><mi>b</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>12</mn></msup></mrow><annotation encoding="application/x-tex">1\le a\le b\le 10^{12}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.78041em;vertical-align:-0.13597em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathnormal">a</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83041em;vertical-align:-0.13597em;"></span><span class="mord mathnormal">b</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></span>。</li>
</ul>
<p>分析：</p>
<p>设dp_i表示在不考虑前导零，满i位（<10^i）时一种数出现了多少次</p>
<p>对于前i位：</p>
<p>1.前导零合法时，0~9的数量都相同：对于dp_i=dp_{i-1}*10</p>
</div>
</div>
<div class="post-tags">
</div>
<a href="/2024/09/13/%E6%95%B0%E4%BD%8DDP/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/07/29/2024%E2%80%9C%E9%92%89%E8%80%99%E7%BC%96%E7%A8%8B%E2%80%9D%E4%B8%AD%E5%9B%BD%E5%A4%A7%E5%AD%A6%E7%94%9F%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E8%B6%85%E7%BA%A7%E8%81%94%E8%B5%9B-4/">
<h2 class="post-title">2024“钉耙编程”中国大学生算法设计超级联赛(4)</h2>
</a>
<div class="category-and-date">
<span class="category">
<a href="/categories/%E6%AF%94%E8%B5%9B/">
<span class="icon">
<i class="fa-solid fa-bookmark fa-fw"></i>
</span>
比赛
</a>
</span>
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/7/29
</span>
</div>
<div class="description">
<div class="content" v-pre>
<h4 id="序列更新"><a class="markdownIt-Anchor" href="#序列更新"></a> 序列更新</h4>
<p>给定两个长度为n 的序列$ 𝑎_0,𝑎_1,…,𝑎_{𝑛−1}$ 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>𝑏</mi><mn>0</mn></msub><mo separator="true">,</mo><msub><mi>𝑏</mi><mn>1</mn></msub><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><msub><mi>𝑏</mi><mrow><mi>𝑛</mi><mtext>−</mtext><mn>1</mn></mrow></msub></mrow><annotation encoding="application/x-tex">𝑏_0,𝑏_1,…,𝑏_{𝑛−1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.902771em;vertical-align:-0.208331em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.301108em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="mord mtight">−</span><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.208331em;"><span></span></span></span></span></span></span></span></span></span></p>
<p>你需要依次执行q次操作，每次操作将会给出一个整数<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo stretchy="false">(</mo><mn>0</mn><mo>≤</mo><mi>𝑘</mi><mo><</mo><mi>𝑛</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">k(0≤𝑘<𝑛)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mopen">(</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.73354em;vertical-align:-0.0391em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，对于每个$ 𝑖 (0≤𝑖<𝑛)$，你需要将 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>𝑎</mi><mi>𝑖</mi></mrow><annotation encoding="application/x-tex">𝑎𝑖</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathnormal">a</span><span class="mord mathnormal">i</span></span></span></span> 更新为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mtext></mtext><mo stretchy="false">(</mo><msub><mi>𝑎</mi><mi>𝑖</mi></msub><mo separator="true">,</mo><msub><mi>𝑏</mi><mrow><mi>𝑖</mi><mo>+</mo><mi>𝑘</mi></mrow></msub><mtext> </mtext><mi>m</mi><mi>o</mi><mi>d</mi><mtext> </mtext><mi>𝑛</mi><mo stretchy="false">)</mo><mtext>。</mtext></mrow><annotation encoding="application/x-tex">max(𝑎_𝑖,𝑏_{𝑖+𝑘}\ mod\ 𝑛)。</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">m</span><span class="mord mathnormal">a</span><span class="mord mathnormal">x</span><span class="mord"></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathnormal">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361079999999999em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span><span class="mbin mtight">+</span><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.208331em;"><span></span></span></span></span></span></span><span class="mspace"> </span><span class="mord mathnormal">m</span><span class="mord mathnormal">o</span><span class="mord mathnormal">d</span><span class="mspace"> </span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mord cjk_fallback">。</span></span></span></span>为了证明你确实维护了a序列，请在每次操作之后输出 $\sum_{i=0}^{i<n}a_i $的值。</p>
</div>
</div>
<div class="post-tags">
<span class="icon">
<i class="fa-solid fa-tags fa-fw"></i>
</span>
<span class="tag">
<a href="/tags/%E6%9C%9F%E6%9C%9B/" style="color: #03a9f4">期望</a>
</span>
<span class="tag">
<a href="/tags/%E6%A6%82%E7%8E%87%E8%AE%BA/" style="color: #ffa2c4">概率论</a>
</span>
<span class="tag">
<a href="/tags/%E6%A0%B9%E5%8F%B7%E6%80%9D%E6%83%B3/" style="color: #00bcd4">根号思想</a>
</span>
</div>
<a href="/2024/07/29/2024%E2%80%9C%E9%92%89%E8%80%99%E7%BC%96%E7%A8%8B%E2%80%9D%E4%B8%AD%E5%9B%BD%E5%A4%A7%E5%AD%A6%E7%94%9F%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E8%B6%85%E7%BA%A7%E8%81%94%E8%B5%9B-4/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/07/21/2024%E6%9A%91%E5%81%87%E9%9B%86%E8%AE%AD%E7%AC%AC%E4%B8%80%E5%91%A8%E6%80%BB%E7%BB%93/">
<h2 class="post-title">2024暑假集训第一周总结</h2>
</a>
<div class="category-and-date">
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/7/21
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p><em>迟来的第一周总结…</em></p>
<p>第一周一共四场比赛：总的来说还有很多东西没学，或者学的不深，个人感觉八月之前应该在不停的学新东西了，八月之后得对算法加深一些理解和掌握。比赛得时候，签到和能出得思维大家都一样，后期就看谁知识点学过或者掌握的更深了…</p>
</div>
</div>
<div class="post-tags">
</div>
<a href="/2024/07/21/2024%E6%9A%91%E5%81%87%E9%9B%86%E8%AE%AD%E7%AC%AC%E4%B8%80%E5%91%A8%E6%80%BB%E7%BB%93/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/06/11/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86-%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86-%E6%89%A9%E5%B1%95%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/">
<h2 class="post-title">费马小定理&欧拉定理&扩展欧拉定理</h2>
</a>
<div class="category-and-date">
<span class="category">
<a href="/categories/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/">
<span class="icon">
<i class="fa-solid fa-bookmark fa-fw"></i>
</span>
欧拉定理
</a>
</span>
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/6/11
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p>sdf dsf</p>
</div>
</div>
<div class="post-tags">
<span class="icon">
<i class="fa-solid fa-tags fa-fw"></i>
</span>
<span class="tag">
<a href="/tags/%E7%AC%94%E8%AE%B0/" style="color: #03a9f4">笔记</a>
</span>
</div>
<a href="/2024/06/11/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86-%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86-%E6%89%A9%E5%B1%95%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/06/10/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F-scc%E7%BC%A9%E7%82%B9-tarjan/">
<h2 class="post-title">强连通分量(scc缩点/tarjan)</h2>
</a>
<div class="category-and-date">
<span class="category">
<a href="/categories/%E7%AC%94%E8%AE%B0/">
<span class="icon">
<i class="fa-solid fa-bookmark fa-fw"></i>
</span>
笔记
</a>
</span>
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/6/10
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p>学习了一下强连通分量，整理一下：</p>
</div>
</div>
<div class="post-tags">
<span class="icon">
<i class="fa-solid fa-tags fa-fw"></i>
</span>
<span class="tag">
<a href="/tags/dfs/" style="color: #ffa2c4">dfs</a>
</span>
<span class="tag">
<a href="/tags/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/" style="color: #ff7d73">强连通分量</a>
</span>
<span class="tag">
<a href="/tags/tarjan/" style="color: #03a9f4">tarjan</a>
</span>
<span class="tag">
<a href="/tags/%E6%8B%93%E6%89%91/" style="color: #ffa2c4">拓扑</a>
</span>
</div>
<a href="/2024/06/10/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F-scc%E7%BC%A9%E7%82%B9-tarjan/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/05/27/lca%E4%B8%8E%E6%A0%91%E4%B8%8A%EF%BC%88%E8%B7%AF%E5%BE%84%E4%BA%A4%E3%80%81%E5%B9%B6%EF%BC%8C%E7%9B%B4%E5%BE%84%EF%BC%89%E9%97%AE%E9%A2%98/">
<h2 class="post-title">lca与树上（路径交、并，直径）问题</h2>
</a>
<div class="category-and-date">
<span class="category">
<a href="/categories/%E7%AC%94%E8%AE%B0/">
<span class="icon">
<i class="fa-solid fa-bookmark fa-fw"></i>
</span>
笔记
</a>
</span>
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/5/27
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p>最近的一些比赛中经常用到树上<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>l</mi><mi>c</mi><mi>a</mi></mrow><annotation encoding="application/x-tex">lca</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">c</span><span class="mord mathnormal">a</span></span></span></span>的常见模型，整理一下：</p>
</div>
</div>
<div class="post-tags">
<span class="icon">
<i class="fa-solid fa-tags fa-fw"></i>
</span>
<span class="tag">
<a href="/tags/%E5%9B%BE%E8%AE%BA/" style="color: #00a596">图论</a>
</span>
<span class="tag">
<a href="/tags/%E6%A0%91%E8%AE%BA/" style="color: #ffa2c4">树论</a>
</span>
<span class="tag">
<a href="/tags/LCA/" style="color: #03a9f4">LCA</a>
</span>
<span class="tag">
<a href="/tags/Tarjan/" style="color: #00bcd4">Tarjan</a>
</span>
<span class="tag">
<a href="/tags/st%E8%A1%A8/" style="color: #ffa2c4">st表</a>
</span>
<span class="tag">
<a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="color: #ff7d73">数据结构</a>
</span>
<span class="tag">
<a href="/tags/%E5%B9%B6%E6%9F%A5%E9%9B%86/" style="color: #ffa2c4">并查集</a>
</span>
<span class="tag">
<a href="/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/" style="color: #03a9f4">线段树</a>
</span>
<span class="tag">
<a href="/tags/dfs/" style="color: #00bcd4">dfs</a>
</span>
<span class="tag">
<a href="/tags/bfs/" style="color: #ff7d73">bfs</a>
</span>
</div>
<a href="/2024/05/27/lca%E4%B8%8E%E6%A0%91%E4%B8%8A%EF%BC%88%E8%B7%AF%E5%BE%84%E4%BA%A4%E3%80%81%E5%B9%B6%EF%BC%8C%E7%9B%B4%E5%BE%84%EF%BC%89%E9%97%AE%E9%A2%98/" class="go-post">阅读全文</a>
</div>
<div class="post">
<a href="/2024/04/03/2023%20Hubei%20Provincial%20Collegiate%20Programming%20Contest/">
<h2 class="post-title">2023 Hubei Provincial Collegiate Programming Contest</h2>
</a>
<div class="category-and-date">
<span class="category">
<a href="/categories/%E8%A1%A5%E9%A2%98/">
<span class="icon">
<i class="fa-solid fa-bookmark fa-fw"></i>
</span>
补题
</a>
</span>
<span class="date">
<span class="icon">
<i class="fa-solid fa-calendar fa-fw"></i>
</span>
2024/4/3
</span>
</div>
<div class="description">
<div class="content" v-pre>
<p><a target="_blank" rel="noopener" href="https://codeforces.com/gym/104337/problem/I">Problem - I - step</a></p>
</div>
</div>
<div class="post-tags">
<span class="icon">
<i class="fa-solid fa-tags fa-fw"></i>
</span>