-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1953 lines (1077 loc) · 71.1 KB
/
index.html
File metadata and controls
1953 lines (1077 loc) · 71.1 KB
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 class="theme-next pisces use-motion" lang="zh-Hans">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">
<meta name="baidu-site-verification" content="KTIrJPu40q" />
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
<link href="/css/main.css?v=6.0.1" rel="stylesheet" type="text/css" />
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.0.1">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=6.0.1">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=6.0.1">
<link rel="mask-icon" href="/images/logo.svg?v=6.0.1" color="#222">
<meta name="keywords" content="数学,单位根反演,FFT/NTT," />
<meta name="description" content="题目大意考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$） 一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a &lt; b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-">
<meta name="keywords" content="数学,单位根反演,FFT/NTT">
<meta property="og:type" content="article">
<meta property="og:title" content="HNOI2019 白兔之舞">
<meta property="og:url" content="https://zhang-rq.github.io/2019/07/09/HNOI2019白兔之舞/index.html">
<meta property="og:site_name" content="Loner">
<meta property="og:description" content="题目大意考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$） 一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a &lt; b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2021-03-07T12:19:40.613Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="HNOI2019 白兔之舞">
<meta name="twitter:description" content="题目大意考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$） 一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a &lt; b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Pisces',
version: '6.0.1',
sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
fancybox: false,
fastclick: false,
lazyload: false,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<link rel="canonical" href="https://zhang-rq.github.io/2019/07/09/HNOI2019白兔之舞/"/>
<title>Loner</title>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-112446994-1', 'auto');
ga('send', 'pageview');
</script>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container sidebar-position-left
page-home">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"> <div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">Loner</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle"></p>
</div>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档</a>
</li>
<li class="menu-item menu-item-search">
<a href="javascript:;" class="popup-trigger">
<i class="menu-item-icon fa fa-search fa-fw"></i> <br />搜索</a>
</li>
<li class="menu-item menu-item-canvas-toggle">
<a href="javascript:;" rel="section" id="stop-canvas" >
<i class="menu-item-icon fa fa-fw fa-stop"></i> <br /> 隐藏背景动画
</a>
<a href="javascript:;" rel="section" id="play-canvas">
<i class="menu-item-icon fa fa-fw fa-play"></i> <br /> 显示背景动画
</a>
</li>
</ul>
<div class="site-search">
<div class="popup search-popup local-search-popup">
<div class="local-search-header clearfix">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
<div class="local-search-input-wrapper">
<input autocomplete="off"
placeholder="搜索..." spellcheck="false"
type="text" id="local-search-input">
</div>
</div>
<div id="local-search-result"></div>
</div>
</div>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://zhang-rq.github.io/2021/03/07/new-blog/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Zhang_RQ">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/favicon-big.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Loner">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2021/03/07/new-blog/" itemprop="url">new-blog</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2021-03-07T20:28:40+08:00">2021-03-07</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Others/" itemprop="url" rel="index">
<span itemprop="name">Others</span>
</a>
</span>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2021/03/07/new-blog/#comments" itemprop="discussionUrl">
<span class="post-comments-count valine-comment-count" data-xid="/2021/03/07/new-blog/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>这个博客以后就不更了~</p>
<p>欢迎来新的博客玩~</p>
<p><a href="https://kamome.moe" target="_blank" rel="noopener">https://kamome.moe</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://zhang-rq.github.io/2019/07/09/HNOI2019白兔之舞/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Zhang_RQ">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/favicon-big.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Loner">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/07/09/HNOI2019白兔之舞/" itemprop="url">HNOI2019 白兔之舞</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-07-09T20:04:21+08:00">2019-07-09</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/题解/" itemprop="url" rel="index">
<span itemprop="name">题解</span>
</a>
</span>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2019/07/09/HNOI2019白兔之舞/#comments" itemprop="discussionUrl">
<span class="post-comments-count valine-comment-count" data-xid="/2019/07/09/HNOI2019白兔之舞/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="题目大意"><a href="#题目大意" class="headerlink" title="题目大意"></a>题目大意</h1><p>考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$）</p>
<p>一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a < b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-1]$都输出一个答案。</p>
<p>给定$n,w[][],L,x,y,d,t$，答案对质数$P$取模，保证有在模$P$意义下的$d$次单位根。</p>
<h1 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h1><p>考虑若对$x$的限制是$x=L$，那么这个问题可以直接使用矩阵快速幂解决。</p>
<p>加上题目里都明示要用单位根反演了，那我们考虑用单位根反演来解决这个问题。</p>
<p>我们可以比较容易地想到这个多项式：</p>
<script type="math/tex; mode=display">
f(x)=\left( \begin{bmatrix} 1 \ 0 \ 0 \\ 0 \ 1 \ 0 \\ 0 \ 0 \ 1 \end {bmatrix} + Wx \right)^L</script><p>其中，$W$是一个矩阵，数值就是给定的w数组。</p>
<p>那么我们要求的东西就是这个：</p>
<script type="math/tex; mode=display">
Ans_k=\sum_{i=0}^L [x \bmod k=t] [x^i]f(x) \qquad (for \ k \in[0,t-1])</script><p>然后就可以用矩阵乘法求答案了！</p>
<p>我们考虑使用单位根反演。注意：为了处理不是$d$的整次幂的情况，我们可以直接乘上一个$x^{d-k}$。</p>
<script type="math/tex; mode=display">
\begin{aligned}
Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} f(\omega_{d}^{i})(\omega_d^{i})^{d-k} \\
Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{-i\times k} \times f(\omega_{d}^{i})
\end{aligned}</script><p>注意到：$i \times k= {i +k \choose 2} - {i \choose 2} - {k \choose 2}$。</p>
<p>代入可得</p>
<script type="math/tex; mode=display">
\begin{aligned}
Ans_k = \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{ {k \choose 2} + {i \choose 2} - {i+k \choose 2} } \times f(\omega_{d}^{i}) \\
Ans_k = \frac{\omega_d^{ {k \choose 2} } }{d} \sum_{i=0} ^{d-1} \omega_d^{-{i+k \choose 2} } \times ( f(\omega_{d}^{i}) \times \omega_d^{ {i \choose 2} } )
\end{aligned}</script><p>后面的用矩阵快速幂预处理。</p>
<p>差一定的卷积，请。</p>
<p>（要写任意模数卷积。）</p>
<p>代码请移步Github仓库。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://zhang-rq.github.io/2019/04/09/WC2019-数树/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Zhang_RQ">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/favicon-big.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Loner">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/04/09/WC2019-数树/" itemprop="url">[WC2019] 数树</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-04-09T17:10:18+08:00">2019-04-09</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/题解/" itemprop="url" rel="index">
<span itemprop="name">题解</span>
</a>
</span>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2019/04/09/WC2019-数树/#comments" itemprop="discussionUrl">
<span class="post-comments-count valine-comment-count" data-xid="/2019/04/09/WC2019-数树/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="题目大意"><a href="#题目大意" class="headerlink" title="题目大意"></a>题目大意</h1><p>题目的模型是有两棵$n$个点树，求$y^{|T <em> 1 \cap T </em> 2 |}$。（$T <em> 1,T </em> 2$分别是两棵树的边集。）</p>
<p>有三个部分，分别是：</p>
<ul>
<li>给定两棵树求答案。</li>
<li>给定一棵树，然后求另一棵树是$n^{n-2}$种情况时的答案和。</li>
<li>只给一个$n$，求出两棵树在所有情况下的答案和（共$(n^{n-2})^2$种情况）</li>
</ul>
<h1 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h1><p>我们一次考虑每个部分的做法。</p>
<h2 id="给定两棵树"><a href="#给定两棵树" class="headerlink" title="给定两棵树"></a>给定两棵树</h2><p>这部分只有普及组难度，随便用个$set$记一下就行了。</p>
<h2 id="给定一棵树"><a href="#给定一棵树" class="headerlink" title="给定一棵树"></a>给定一棵树</h2><p>我们不妨钦定一些$T <em> 1$中的边为必选边，那么考虑$T </em> 2$的方案数是多少（记为$F$）。</p>
<p>我们发现，加入一些必选边后，$T _ 2$被连成了若干连通块，我们假设形成了$m$个连通块（说明钦定了$n-m$条边）。</p>
<p>有一个很直观的想法就是这$m$个连通块的生成树个树（即$m^{m-2}$），但是显然算少了很多，因为两个连通块间的边的个数不是$1$，而是两个连通块大小的乘积。</p>
<p>那么我们不妨从$m^{m-2}$的本质来考虑这件事，众所周知，$m^{m-2}$的来源是$prufer$序列，那我们从$prufer$序列来审视这个问题。</p>
<p>我们发现，假设一个连通块的出现次数在$prufer$的出现次数为$d <em> i$，它的大小为$siz </em> i$，显然，它的度数为$d <em> i+1$，它对答案有一个$siz </em> i^{d _ i+1}$的乘法贡献。</p>
<p>我们现在不妨枚举每个连通块在$prufer$序列的出现次数并且枚举$prufer$序列，注意要处理多重集合的排列。</p>
<p>那么方案数很容易写出：</p>
<script type="math/tex; mode=display">
F= m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i+1}}{d _ i!}</script><p>我们随手化简一下，可以得到</p>
<script type="math/tex; mode=display">
F= \prod _ {i=1}^{m} siz _ i \times m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i}}{d _ i!}</script><p>我们接下来来考虑后面这一坨东西的组合意义，相当于我们先给每个连通块分配了一些位置，然后每个位置可以填$siz <em> i$种数字。那么我们可以直接考虑每个位置能填的数字，显然种类数就是$\sum </em> {i} siz _ i =n$，那么可以进一步化简得到最终形式。</p>
<script type="math/tex; mode=display">
F = \prod _ {i=1} ^{m} siz _ i \times n^{m-2}</script><p>也就是说，我们现在可以暴力枚举边集，然后计算答案</p>
<script type="math/tex; mode=display">
Ans = \sum _ {E \subset T _ 1} y^{n-|E|} n^{n-|E|-2} \prod _ {i=1} ^{n-|E|-2} siz _ i\\
Ans = y^n n^{n-2} \sum _ {E \subset T _ 1} y^{-|E|} n^{-|E|} \prod _ {i=1} ^{n-|E|-2} siz _ i</script><p>接下来，为方便起见，我们令$y=y^{-1}$，最后统一乘$y^n$。</p>
<p>写个暴力，然后发现这玩意并不对，我们冷静分析一下，发现我们钦定出来的边集只是两个边集的交的一个子集，而不是最终的交。</p>
<p>那么接下来有两种处理方法，容斥和组合恒等式，这里只介绍组合恒等式的处理方法。</p>
<p>我们发现，我们设最终的交集为$|S|$，若我们钦定的集合的大小为$k$，那么这种大小的连通块对$S$的贡献就是.${|S| \choose k} \times val$。</p>
<p>我们知道有组合恒等式$y^{k} = \sum \limits _ {i=0} ^{k} {k \choose i} (y-1) ^ i$。</p>
<p>那么如果我们将权值$val$设置为$y-1$，再进行刚才的做法，发现每个集合的贡献恰好是$y^k$。</p>
<p>于是我们得到了一个指数级的做法，枚举边集。我们接下来考虑将复杂度降到$poly(n)$。</p>
<p>一个很自然的想法就是用树形$dp$来优化上述过程，我们发现，一个点状态只和这个点所在的连通块大小有关。那么可以设$f _ {x,s}$为考虑完以$x$为根的子树后，$x$所在的连通块的大小为$s$。这样，我们在合并儿子时考虑下$x$到儿子的这条边选不选，并且乘上相应的系数（$1$或$y^{-1}n^{-1}$）进行转移即可，使用$siz$优化，复杂度为$\mathcal{O}(n^2)$。</p>
<p>这个做法的复杂度我们显然无法接受，考虑继续优化。</p>
<p>我们发现，$\prod{siz _ i}$的组合意义是从每个连通块分别选出一个点的方案数。那么我们可以这个组合意义设置新的$dp$状态。</p>
<p>我们设$f _ {x,0/1}$为考虑完$x$为根的子树，$x$所在连通块是否已经选点了的方案数，转移讨论一下就行了，注意每个点必须要选出一个点。复杂度$\mathcal{O}(n)$。</p>
<h2 id="给定零棵树"><a href="#给定零棵树" class="headerlink" title="给定零棵树"></a>给定零棵树</h2><p>这里我们继续沿用给定一棵树时的做法。</p>
<p>我们设$f(E)=\prod <em> {i=1} ^{m} siz </em> i \times n^{m-2}$，其中，$E$是一个边集，$m$表示将$E$中的边连接后形成的连通块个数，${siz}$是每个连通块的大小。</p>
<p>那么我们枚举一个边集$E$，且这个边集必须是某棵树的边集的子集，那么这个边集对答案的贡献是$f(E)^2 y^{|E|}$。</p>
<p>所以答案就是$\sum \limits _ {E} y^{|E|} f(E)^2 $。</p>
<p>我们不妨枚举$|E|$，我们设$g <em> i=\sum \limits </em> {|E|=i} f(E)$，答案可以进一步化简为$\sum \limits <em> {i=0}^{n-1} y^i g </em> i$。</p>
<p>那么我们接下来就要处理${g}$数组了。</p>
<p>由$f(E)$的计算式，我们不妨考虑枚举将$E$中的边连起来后每个连通块的大小${a}$，然后可以得到以下式子：</p>
<script type="math/tex; mode=display">
g _ s = \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2</script><p>解释下这个式子是怎么来的：</p>
<p>首先，我们需要让这些连通块内部都是连通的，就是$\prod \limits <em> {i=1}^{n-s} a </em> i^{a <em> i-2}$，然后，我们将$n$个点划分到这些集合中，就是多重集合的排列，体现在式子中就是$n! \prod \limits </em> {i=1}^{n-s} \frac{1}{a _ 1!}$，最后，这些连通块其实是无序的，但是我们在枚举大小的时候是作为有序的做的，所以我们要除掉$(n-s)!$，最后那个平方项就是$f(E)^2$。</p>
<p>然后我们将这个式子带到答案的式子中，并进行一番化简：</p>
<script type="math/tex; mode=display">
\begin{aligned}
Ans &= \sum _ {s=0}^{n-1} \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2 \\
Ans &= \sum _ {s=0}^{n-1} n!\frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1}^{n-s} {\frac{a _ i^{a _ i}}{a _ i!}}\\
Ans &= n! \sum _ {s=0}^{n-1} y^s \frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\
Ans &= n! \sum _ {s=1}^{n} y^{(n-s)} \frac{n^{2 * (s-2)}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\
Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2 * s}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}}
\end{aligned}</script><p>注意，在第四个式子中，我用将$s$替换为了$n-s$。</p>
<p>然后我们发现第二个求和号的那个限制很难搞，但观察一下可以发现其实是个$\bf EGF$的形式，我们用$\bf EGF$来替换第二个求和号部分，并继续化简：</p>
<script type="math/tex; mode=display">
\begin{aligned}
Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2*s}}{s!} [x^n] \left( {\sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s\\
Ans &= \frac{n!y^n}{n^4} [x^n] \sum _ {s=1}^{n} \frac{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s}{s!}\\
Ans &= \frac{n!y^n}{n^4} [x^n] e^{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right)}
\end{aligned}</script><p>然后写个多项式$\bf Exp$就做完了。</p>
<p>复杂度：$\mathcal{O}(n \log n)$</p>
<p><a href="https://github.com/Zhang-RQ/OI_Code/blob/master/LOJ/2983.cpp" target="_blank" rel="noopener">代码</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://zhang-rq.github.io/2019/02/21/CodeForces-98E-Help-Shrek-and-Donkey/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Zhang_RQ">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/favicon-big.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Loner">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/02/21/CodeForces-98E-Help-Shrek-and-Donkey/" itemprop="url">[CodeForces 98E] Help Shrek and Donkey</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-02-21T18:56:51+08:00">2019-02-21</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/题解/" itemprop="url" rel="index">
<span itemprop="name">题解</span>
</a>
</span>
</span>
<span class="post-comments-count">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-comment-o"></i>
</span>
<a href="/2019/02/21/CodeForces-98E-Help-Shrek-and-Donkey/#comments" itemprop="discussionUrl">
<span class="post-comments-count valine-comment-count" data-xid="/2019/02/21/CodeForces-98E-Help-Shrek-and-Donkey/" itemprop="commentCount"></span>
</a>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="题目大意"><a href="#题目大意" class="headerlink" title="题目大意"></a>题目大意</h1><p>有两个人在玩一个游戏，规则如下：</p>
<ol>
<li><p>每个人的手上有一些牌，桌子上有一张牌，每个人只能看到自己手上的牌。（桌子上的看不到）</p>
</li>
<li><p>每张牌都不一样。</p>
</li>
<li><p>两个人轮流进行如下两个操作之一：</p>
<ul>
<li><p>猜桌子上的那张牌是什么，若猜对了，即获得胜利，否则算输掉比赛。</p>
</li>
<li><p>询问对方手中有没有一张牌，对方必须如实回答。</p>
</li>
</ul>
</li>
</ol>
<p>现在假设两个人都会执行最优策略，给定先后手的牌数$n,m$，询问两个人的胜率。</p>
<p>$n,m \leqslant 1000$</p>
<h1 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h1><p>不难发现，一个人若是进行询问操作，则有两种问法：</p>
<ol>
<li><p>询问自己手上没有的牌。（我们记这种询问为诚实的询问）</p>
</li>
<li><p>询问自己手上有的牌。（我们记这种询问为欺骗的询问）</p>
</li>
</ol>
<p>因为一个比较显然的思路是每次询问是问自己手上没有的牌（这样才能获得更多的信息）</p>
<p>然而我没也可以询问自己手上有的牌来误导对方自己手上没有这张牌，然后对方也没有这张牌的话就会认为桌子上是这张牌并猜是这张牌，然后他就输了。</p>
<p>然后对方也可以猜我这次的询问是不是诚实的询问（我们记为是否相信）。</p>
<h1 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h1><p>我们设$f(n,m)$为先手有$n$张牌，后手有$m$张牌时先手的胜率。</p>
<p>从刚才的分析中我们可以根据询问的诚实与否和是否相信来分为4种情况。</p>
<h2 id="情况的具体分析"><a href="#情况的具体分析" class="headerlink" title="情况的具体分析"></a>情况的具体分析</h2><h3 id="1-先手进行诚实询问，后手相信这次询问。"><a href="#1-先手进行诚实询问，后手相信这次询问。" class="headerlink" title="1. 先手进行诚实询问，后手相信这次询问。"></a>1. 先手进行诚实询问，后手相信这次询问。</h3><p>那么会有以下两种情况：</p>
<ol>
<li>$\frac{1}{m+1}$的概率猜到桌子上的牌，那么后手获胜（先手已经进行了操作，而后手已经知道了问的那张牌自己没有同时对方也没有，也就是桌子上的牌），对$f(n,m)$的贡献为$0$。</li>
<li>$\frac{m}{m+1}$的概率猜到后手手上的牌，那么先手知道了后手有问的那张牌（相当于后手失去了一张牌），后手知道了先手没有问的那张牌（没有得到新的信息），对$f(n,m)$的贡献是$\frac{m}{m+1} \times (1-f(m-1,n))$。（因为接下来先后手互换）</li>
</ol>
<h3 id="2-先手进行诚实询问，后手不相信这次询问。"><a href="#2-先手进行诚实询问，后手不相信这次询问。" class="headerlink" title="2.先手进行诚实询问，后手不相信这次询问。"></a>2.先手进行诚实询问，后手不相信这次询问。</h3><p>会出现以下两种情况：</p>
<ol>
<li>$\frac{1}{m+1}$的概率猜到桌子上的牌，那么后手会认为这张桌子上的牌会在先手的手中，也就是后手必败，对$f(n,m)$的贡献是$\frac{1}{m+1}$。</li>
<li>$\frac{m}{m+1}$的概率猜到后手手上的牌，那么后手肯定会相信这次询问，那么对答案的贡献就和上面一样了，即为$\frac{m}{m+1} \times (1-f(m-1,n))$。</li>
</ol>
<h3 id="3-先手进行欺骗询问，后手相信这次询问。"><a href="#3-先手进行欺骗询问，后手相信这次询问。" class="headerlink" title="3.先手进行欺骗询问，后手相信这次询问。"></a>3.先手进行欺骗询问，后手相信这次询问。</h3><p>那么后手就中招了，自己手上没有那张牌，且认为先手手上也没有问的那张牌，那么就会认为那张牌就是桌子上的牌，这样先手就会必胜，对$f(n,m)$的贡献是$1$。</p>
<h3 id="4-先手进行欺骗询问，后手不相信这次询问。"><a href="#4-先手进行欺骗询问，后手不相信这次询问。" class="headerlink" title="4.先手进行欺骗询问，后手不相信这次询问。"></a>4.先手进行欺骗询问，后手不相信这次询问。</h3><p>那么后手就会多知道先手手的一张牌（相当于先手失去了一张牌），对$f(n,m)$的贡献是$1-f(m,n-1)$。</p>
<h2 id="做法"><a href="#做法" class="headerlink" title="做法"></a>做法</h2><p>不难发现，这是一种混合策略的博弈游戏，就需要纳什均衡的那一套理论。</p>
<p>我们不妨假设先手进行诚实询问的概率为$p$，则进行欺骗询问的概率就是$1-p$。</p>
<p>那么后手选相信时对答案的贡献就是$p \times \frac{m}{m+1} \times (1-f(m-1,n)) + (1-p) \times 1$。</p>
<p>后手选不相信时对答案的贡献就是$p \times (\frac{1}{m+1}+\frac{m}{m+1} \times (1-f(m-1,n))) +(1-p) \times 1-f(m,n-1)$。</p>
<p>根据纳什均衡的理论，先手的最优决策点就是纳什均衡点，就是无论后手如何选择，答案均不会比当前情况更差的那个$p$，在这里就是令上下式子相等的那个$p$，解下方程就行了。</p>
<p>最后我们再记忆化一下就可以做到$\mathcal{O}(nm)$了。</p>
<h3 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN=<span class="number">1010</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">bool</span> vis[MAXN][MAXN];</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">double</span> f[MAXN][MAXN];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">double</span> <span class="title">F</span><span class="params">(<span class="keyword">int</span> n,<span class="keyword">int</span> m)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span>(vis[n][m]) <span class="keyword">return</span> f[n][m];</span><br><span class="line"> vis[n][m]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(!n) <span class="keyword">return</span> f[n][m]=<span class="number">1.0</span>/(m+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">if</span>(!m) <span class="keyword">return</span> f[n][m]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">double</span> k1=<span class="number">1.0</span>*m/(m+<span class="number">1</span>)*(<span class="number">1</span>-F(m<span class="number">-1</span>,n))<span class="number">-1</span>,k2=<span class="number">1.0</span>*m/(m+<span class="number">1</span>)*(<span class="number">1</span>-F(m<span class="number">-1</span>,n))+<span class="number">1.0</span>/(m+<span class="number">1</span>)+F(m,n<span class="number">-1</span>)<span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">double</span> x=(-F(m,n<span class="number">-1</span>))/(k1-k2);</span><br><span class="line"> <span class="keyword">return</span> f[n][m]=x*(<span class="number">1.0</span>*m/(m+<span class="number">1</span>)*(<span class="number">1</span>-F(m<span class="number">-1</span>,n)))+<span class="number">1</span>-x;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n,m;</span><br><span class="line"> <span class="built_in">cin</span>>>n>>m;</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">double</span> Ans=F(n,m);</span><br><span class="line"> <span class="built_in">cout</span><<fixed<<setprecision(<span class="number">15</span>)<<Ans<<<span class="string">" "</span><<<span class="number">1</span>-Ans<<<span class="built_in">endl</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>