GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
数学
反演

[Luogu P1829] [国家集训队]Crash的数字表格 / JZPTAB

题面 传送门:洛咕 Solution 调到自闭,我好菜啊 为了方便讨论,以下式子$m>=n$ 为了方便书写,以下式子中的除号均为向下取整 我们来颓柿子吧qwq 显然,题目让我们求: $\large \sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$ $lcm$没法玩,我们转到$gcd$形式: $\large \sum_{i=1}^n\sum_{j=1}^m \frac{i*j}{gcd(i,j)}$ 根据套路,我们去枚举$gcd$ $\large \sum_{i=1}^n\sum_{j=1…

2019年03月05日 0条评论 284点热度 0人点赞 阅读全文
反演

[Luogu P2522] [HAOI2011]Problem b

题面 传送门:洛咕 Solution 我怎么只会刷水题 这题的双倍经验题,不多说啥了。 啥?范围不一样? 那根据我们写数位DP及二维前缀和的经验,我们容斥一下...... 然后就没有然后了。 时间复杂度$O(m*\sqrt n)$ Code 人傻自带大常数,不开O2 T一个点 事实上这题可以把一些不必要的$longlong$改成$int$,刚好能过。可惜我太颓,不想改了 //Luogu P2522 [HAOI2011]Problem b //Jan,23rd,2019 //莫比乌斯函数双倍经验题 #include&…

2019年03月05日 0条评论 310点热度 0人点赞 阅读全文
反演

[Luogu P3327] [SDOI2015]约数个数和

题面: 传送门:洛咕 Solution 首先,我们需要一个结论: $\large d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ 证明 理性证明请看这篇博客的例五 本蒟蒻提供一个感性证明的方法:如果$x*y$是$i*j$的因数,我们必须有$x|i,y|j$,而后面那个$gcd(x,y)$是用来去重的 有了这个柿子之后,我们之后的推导就比较套路了: 为了方便讨论,之后的柿子均默认$m>n$ 为了方便书写,之后的除法默认向下取整 原式: $\large \sum_{i=…

2019年03月05日 0条评论 368点热度 0人点赞 阅读全文
反演

[Luogu P3455] [POI2007]ZAP-Queries

题面 传送门:洛咕 Solution 这题比这题不懂简单到哪里去了 好吧,我们来颓柿子。 为了防止重名,以下所有柿子中的$x$既是题目中的$d$ 为了方便讨论,以下柿子均假设$b>=a$ 为了方便书写,以下除号均为向下取整 题目要求的显然是: $\large \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=x]$ 根据套路,我们这里要先把这个$x$除掉 $\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}[gcd(i,j)=1]$ 再根据套路,根据莫比乌斯函数…

2019年03月04日 0条评论 296点热度 0人点赞 阅读全文
反演

[Luogu P2257] YY的GCD

题面 传送门:洛咕 Solution 推到自闭,我好菜啊 显然,这题让我们求: $\large \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$ 根据套路,我们可以把判断是否为质数改为枚举这个质数,有: 为了方便枚举,我们在这里假设有$m>n$ $\large \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k\in prime}^{n}[gcd(i,j)= k]$ 显然,要让$gcd(i,j)=k$,必须要有$i,j$均为$k$的倍数,因此有: …

2019年03月04日 0条评论 323点热度 0人点赞 阅读全文
卷积

狄利克雷卷积学习笔记

蒟蒻尚在学习,请各位dalao不要相信本文的任何一个字,包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下: $\large f*g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也可以写作: $\large f*g(n)=\sum_{i*j=n}f(i)*g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式暴力计算,枚举$i$即可,复杂度$O(\sqrt{n})$ 这里就不上代码了,跟暴力枚举质数长得基本上一…

2019年03月04日 0条评论 430点热度 0人点赞 阅读全文
数学

欧拉函数学习笔记

什么是欧拉函数 记欧拉函数为$\varphi(x)$表示比$x$小且与$x$互质的数的个数。 怎么算欧拉函数 通项公式:$\varphi(x)=x*\prod(1-\frac{1}{p_i})$ ($p_i$为$x$的质因数) 因为欧拉函数是一个积性函数,因此我们可以用欧拉筛(线性筛)在$O(n)$的时间内预处理出来:具体证明请见后文 void GetPrime() { memset(IsPrime,1,sizeof IsPrime); IsPrime[1]=false; phi[1]=1; for(int…

2019年03月01日 0条评论 356点热度 1人点赞 阅读全文
FFT/NTT

[Luogu P3723] [AH2017/HNOI2017]礼物

题面 传送门:洛咕 Solution 调得我头大,我好菜啊 好吧,我们来颓柿子吧: 我们可以只旋转其中一个手环。对于亮度的问题,因为可以在两个串上增加亮度,我们也可以看做是可以为负数的。 所以说,我们可以假设我们旋转$B$串,上下要加上的亮度差为$p$,可以直接拍出一个最暴力的柿子: 设$f(x)$表示$B$串以$x$为开头的差异值,有: $f(x)=\sum_{i=0}^{x-1}(B[i]-A[i+n-x]+p)^2+\sum_{i=x}^{n-1}(B[i]-A[i-x]+p)^2$ 大力展开化简后有: $f…

2019年03月01日 0条评论 351点热度 0人点赞 阅读全文
FFT/NTT

[Luogu P4173]残缺的字符串

题面 传送门:洛咕 Solution 这题我写得脑壳疼,我好菜啊 好吧,我们来说正题。 这题.....emmmmmmm 显然KMP类的字符串神仙算法在这里没法用了。 那咋搞啊(或者说这题和数学有半毛钱关系啊) 我们考虑把两个字符相同强行变为一个数学关系,怎么搞呢? 考虑这题是带通配符的,我们可以这样设: $C(x,y)=(A[x]-B[y])^2*A[x]*B[y]$ 因此,我们可以看出两个字符一样当且仅当$C(x,y)=0$ 因此,我们再设一个函数$P(x)$表示$B$串以第$x$项为结尾的长度为…

2019年03月01日 0条评论 313点热度 0人点赞 阅读全文
FFT/NTT

[Luogu P3338] [ZJOI2014]力

题面 传送门: 洛咕 BZOJ Solution 写到脑壳疼,我好菜啊 我们来颓柿子吧 $F_j=\sum_{i<j}\frac{q_i*q_j}{(i-j)^2}-\sum_{i>j}\frac{q_i*q_j}{(i-j)^2}$ $q_j$与$i$没有半毛钱关系,提到外面去 $F_j=q_j*\sum_{i<j}\frac{q_i}{(i-j)^2}-q_j*\sum_{i>j}\frac{q_i}{(i-j)^2}$ 左右同时除以$q_j$ $E_j=\sum_{…

2019年03月01日 0条评论 352点热度 0人点赞 阅读全文
123

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 70
  • 30
  • 83,347
  • 24,708

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号