[SDOI2017]新生舞会题目描述学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有\(n\)个男生和\(n\)个女生参加舞会，一个男生和一个女生一起跳舞，互为舞伴。Cathy收集了这些同学之间的关系，比如两个人之前认识没，计算得出\(a_{i,j}\)。Cathy还需

[SDOI2017]硬币游戏还是因为感觉网上的写的不够清晰，所以来写一篇用\(P(i)\)表示第\(i\)个同学胜利的概率，\(s_i\)表示第\(i\)个同学猜的序列可以发现，第\(i\)个同学胜利当且仅当当前硬币序列\(T\)的后\(m\)位刚好为\(s_i\)，且\(T\)除了最后\(m\)位出现过\(s_i\)，其他任何位置都

Decribe:求\(\prod_{i=1}^{n}\prod_{j=1}^{m}f_{\gcd(i,j)}\)，其中\(f_i\)代表斐波那契数列的第\(i\)项。Solution：显然莫反启动！\[\prod_{i=1}^{\min(n,m)}f_i^{\sum_{j=1}^{n}\sum_{k=1}^{m}[gcd(j,k)==i]}\]\[\prod_{i=1}^{\min(n,m)}f_i^{\sum_{j=1}^{\lfloor\f

oj:https://gxyzoj.com/d/hzoj/p/P451概率与期望+hash+高斯消元声明一些东西，pre(S,l)表示串S的长度为l的前缀，lst(S,l)表示串S的长度为l的后缀一.对于所有串建立字典树，像「HNOI2013」游走一样高斯消元，时间复杂度\(O(n^3m^3)\)，预计50/70pts二.正解：显然，n项中，出现一个长度

[SDOI2017]天才黑客题目背景SD0062号选手小Q同学为了偷到SDOI7012的试题，利用高超的黑客技术潜入了SDOI出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这

[SDOI2017]树点涂色题目描述Bob有一棵\(n\)个点的有根树，其中\(1\)号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：1x表示把点\(x\)到根节点的路

题面传送门为啥大家都写两个log的线段树优化建边啊，神秘，这1log做法好想又好写捏。首先显然是可以把边看成点的，这样会变成\(O(m)\)个点和\(O(m^2)\)条边，寄。但是还没有完全寄掉，我们发现，对于原图的每个点，对于第一个跑到这个点的边暴力转移，剩下的边转移只有一个子树，否则会

传送门description对于一个元素都\(\leqn\)的正整数集合\(S\)（不含相同元素），\(f(i)\)表示使用集合\(S\)里的数加和为\(i\)的方案数，每个元素可以被使用多次，两个方案不同当且仅当存在一个元素在两种方案中使用次数不同。现给定\(n\)和\(f(i),1\leqi\leqn\)。求出集

P3704[SDOI2017]数字表格经典莫反。题目要求：\[\prod_{i=1}^n\prod_{j=1}^mfib(\gcd(i,j))\]不妨令\(n<m\)。套路地，我们设\(\gcd(i,j)=d\)，然后枚举\(d\)：\[\begin{aligned}&\quad\prod_{d=1}^n\prod_{i=1}^n\prod_{j=1}^mfib(d)^{[\gcd(i,j)==d]}\\&=\pr

DescriptionP3780[SDOI2017]苹果树给定一棵\(n\)个点的树，每个点有若干个价值相同的苹果，儿子能摘至少一个仅当父亲被摘至少一个。给定\(k\)，设\(h\)为你摘的苹果的最大深度，你做多能摘\(k+h\)个，求最大价值。对于所有数据，\(1\len\le5\times10^4\)，\(1\lek\le5\time

传送门跟YY的gcd如出一辙，得到一个显然的柿子\[\prod_{k}F_{k}^{z}\]\[z=\sum_{d}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor\]那么我们设T=kd，\[\prod_{T}\prod_{k|T}F_{k}^x\]\[x=\mu(\frac{T}{k})\lfloor\frac{n}{T}\rfloor\lfl

一、题目描述：用$f_i$表示斐波那契数列的第$i$项，那么有：$f_0=0,f_1=1;f_n=f_{n-1}+f_{n-2},n\ge2$现在有一个$n$行$m$列的数字表格，第$i$行第$j$列的数字是$f_{\gcd(i,j)}$。求这个表格所有数的乘积。共有$T$组数据，答案对$10^9+7$取模。

题意求如下表达式的值\[\prod_{i=1}^{n}\prod_{j=1}^{m}f_{gcd(i,j)}\pmod{10^9+7}\]其中，\(f_i\)为fibonacci数列的第\(i\)项，\(n,m\leqslant10^6\)Solution\[\prod_{i=1}^{n}\prod_{j=1}^{m}f_{gcd(i,j)}\]改变枚举顺序，优先枚举\(d=gcd(i,j)\)，\[=\prod_{d=1}

简要题意令\(f(i)\)为斐波那契数列第\(i\)项的值。\(T\)组数据，对于每一个\(n,m\)，求出：\[\prod_{i=1}^{n}\prod_{j=1}^{m}f(\gcd(i,j))\pmod{10^9+7}\]\(1\leqT\leq10^3,1\leqn,m\leq10^6\)思路这里将介绍一种自认为比题解更为简便的方法首先原式有\(\prod\)

4114「SDOI2017」数字表格题解个人评价：好题且套路多算法标签莫比乌斯反演题目难度：2700题面看我分析题面多组数据，每次给出\(n,m\),求解\(\prod_{i=1}^n\prod_{j=1}^mF_{gcd(i,j)}\)，其中\(F\)是斐波那契数列问题分析第一眼化出这个式子肯定是一脸懵，毕竟我们现在做的大