1220模拟赛 区间积

题目大意:

给一个序列和一些限制$l,r,ans$表示需要使得

$$\prod_{i=l}^{r}a_i\equiv ans(mod \space 10)$$

询问满足条件的序列个数。序列中每个数$0\le a_i< 10$。

我们发现$10$不是个素数,很难处理,所以我们把$10$拆成$2$和$5$,分别处理。

对于每个素数,我们考虑判断每个区间中有没有$0$。

设$g_{l,r}$为区间$[l,r]$中可以有$0$时的方案数,$f_{l,r}$为没有$0$时的方案数。

loj#6132. 「2017 山东三轮集训 Day1」Flair

原题传送门:>Here<

做过家喻户晓的小凯的疑惑的人应该会熟悉一个性质,即两种互质钱币最大不能表示的数为$ab-a-b​$。

而我们发现一个非常好的性质:$c_ic_j\le 10000(i\ne j)$

设$v=gcd(c_1,c_2,\cdots,c_m)$,则所有$\ge 10000$的$v​$的倍数都可以被表示。

这时我们只需要考虑选出的菜的数量$\%v=i​$的方案数。

设$f=(100-p)+px$,我们对这个多项式做循环卷积,得到$f^n$,$f^n_i$表示的就是在$n$道菜中随机选,选出菜的数量$\%v=i​$的方案数。

这样答案就是$\sum_{i=1}^{v-1}f^n_i(v-i)$

0108模拟赛 无人生还

原题传送门:>Here<

第一问

$prufer$序列乱搞即可,

$$ans={(n-2)! \over \prod_{i=1}^{n}(d_i-1)!}$$

loj#6503. 「雅礼集训 2018 Day4」Magic

原题传送门:>Here<

首先对题意进行一些转换:

  • 我们发现枚举格子肯定不可行,考虑枚举颜色;

  • 直接做无标号排列也不可行,考虑先对卡牌进行编号,最后再将答案除以本质相同的排列数,即$$n!\prod_{i=1}^{m}a_i!$$

  • 恰好$K$的魔术对也不能处理,考虑先做出$\ge K$的方案数,再容斥出答案,即$\sum_{i=K}^{n}(-1)^{i-K}\binom{i}{K}f_i$。

luoguP4244 [SHOI2008]仙人掌图 II

原题传送门:>Here<

我的实现在有些地方可能有点复杂,但是应该是比较直观的。

首先对原图建圆方树。

设`f_i`为`i`的子树中的点到`i`的最长距离。特殊的,对于一个方点,`f_i`表示子树中的点到`fa_i`的最长距离`-1`(这样比较好处理)。

`f`值的转移是比较简单的,现在我们考虑每个点子树之间的贡献。

在圆点上时和树上一样,直接处理即可。

在方点上时有点复杂:

设方点的子节点共有`S`个,按顺序编号为`p_0,p_1,\cdots,p_S-1`。这样两个点`p_i,p_j (i>j)`之间的距离`dis(i,j)=min(i-j,S+1-(i-j))`。

可以发现,对于`j\ge i-\lfloor \frac{S+1}{2} \rfloor`,`dis(i,j)=i-j`;

对于`j < i-\lfloor \frac{S+1}{2} \rfloor`,`dis(i,j)=S+1-(i-j)`。

可以对于两种情况分别开两个树状数组,分别查询即可。(当然前一问暴力存,后一问用单调队列也珂以,但是我懒)

loj#6496. 「雅礼集训 2018 Day1」仙人掌

原题传送门:>here<

树形DP版

考虑同样的问题在树上怎么做。

设`f_{i,0},f_{i,1}`分别表示i点的出度`\leq a[i]`以及`\leq a[i]-1`时,

为以i为根的子树中的所有边定向的方案数。

很容易发现每个结点的`f`值等同于将其子节点的`f`值的生成函数(即`f_{u,1}x+f_{u,0}`)卷积在一起,然后求前缀和。可以用分治+`NTT`保证复杂度。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×