首页 > 其他分享 >题解:HDU5628 Clarke and math

题解:HDU5628 Clarke and math

时间:2024-11-06 20:57:21浏览次数:1  
标签:log 卷积 题解 Clarke mid cdots HDU5628 text sum

数学题可爱捏~

Hint

Analysis

注意到形式很好看,猜测是某种神奇迭代。

考虑特殊情况 \(k=1\),于是有:

\(g(i)=\sum_{i_1\mid i}f(i_1)=(f*1)(i)\)$

即 \(g=f*1\)。

于是猜测 \(g=f*1^k\),这里的幂运算表示多次 Dirichlet 卷积

简单证明一下,采用数学归纳法:

基本情况 \(k=1\),已经证过,不在赘述。

当有

\[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})=f*1^{k-1} \]

时,左式卷 \(1\) 得:

\[\begin{align*} \text{LHS}*1&=[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})]*1 \\\ &=\sum_{d\mid i}[\sum_{i_1\mid d}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1})]\cdot 1(\frac{i}{d}) \\\\ &=\sum_{d\mid i}\sum_{i_1\mid d}\sum_{i_2\mid i_1}\cdots\sum_{i_{k-1}\mid i_{k-2}} f(i_{k-1}) \\\\ &=\sum_{i_1\mid i}\sum_{i_2\mid i_1}\sum_{i_3\mid i_2}\cdots\sum_{i_k\mid i_{k-1}} f(i_{k}) \end{align*}\]

右式卷 \(1\) 得:

\(\quad\text{ }\text{ }\text{RHS}*1=f*1^{k-1}*1=f*1^k\)

于是有:

\[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\sum_{i_3\mid i_2}\cdots\sum_{i_k\mid i_{k-1}} f(i_{k})=f*1^k \]

于是由 \(k-1\) 的情况可以得到 \(k\) 的情况,归纳性的,易得,

\(\color{red}{\text{Lemma:}}\)
对任意 \(k \in \mathbb{Z^*}\),有:

\[\sum_{i_1\mid i}\sum_{i_2\mid i_1}\sum_{i_3\mid i_2}\cdots\sum_{i_k\mid i_{k-1}} f(i_{k})=f*1^k \]

即 \(g=f*1^k\)。

于是使用快速幂计算 \(1^k\) 的卷积,单次卷积 \(O(n\log n)\),总时间复杂度 \(O(n\log n\log k)\)。

Code

// 咕咕咕~

标签:log,卷积,题解,Clarke,mid,cdots,HDU5628,text,sum
From: https://www.cnblogs.com/godmoo/p/18531033

相关文章

  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • CF2001 题解
    A给定循环数组,每次操作时,设当前大小为m。选择$i\in[0,m)$,若满足$a_i\lea_{i+1\bmodm}$,则可删除$a_i,a_{i+1\bmodm}$中的任意一个。求最小的操作次数,使得数组中所有元素都相等。$n\le100$操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。然而所有位置都......
  • 暂存的题解
    P4011孤岛营救问题感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。数据范围很小,搜索bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小......
  • [USACO22JAN] Minimizing Haybales P 题解
    [USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(......
  • [USACO21DEC] Tickets P 题解
    [USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路,建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了,之后你就会发现连样例都过......
  • 【问题解决】java.lang.SecurityException: JCE cannot authenticate the provider BC
    问题复现历史项目升级JDK(由1.7升级到8),进行加密/解密时出现报错java.lang.SecurityException:JCEcannotauthenticatetheproviderBC。问题原因Wikipa上查到JCE的描述如下:JavaCryptographyExtension(JCE)isanofficiallyreleasedStandardExtensiontotheJavaPl......
  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......
  • CF1909题解
    CF1909A一眼秒之题,我们发现就是四个方向选三个方向,若是存在一个点它的方向恰好在(0,0)点的另外一个方向,则一定不成立枚举4个方向,发现有点在这个方向,显然选除这个点之外的三个方向的方案就不可行点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=105;int......
  • 题解:P7082 [NWRRC2013] Dwarf Tower
    涉及知识点:动态规划。解题思路设\(dp_i\)为得到\(i\)最小的花费。可以得到转移方程:\(dp_{a_i}=\min(dp_{x_i}+dp_{y_i},dp_{a_i})\)。很明显最多迭代\(n\)次,还需要再外面套一个循化即可。但是有些OJ没有洛谷跑得快,所以需要加一点优化。如果当前循环没有更新......