- 博客(14)
- 收藏
- 关注
RSS订阅原创 数模笔记 (一) : 评价类模型
对题中所给目标按照一定的标准进行分类将题中数据运用数学模型进行处理，并得到唯一指标结果进行比较或排序探究某一综合问题的不同方面并计算验证其总体实现程度。
2023-07-24 22:03:38
342
1原创 NTT(快速数论变换)
用途: 计算整系数多项式卷积。前置芝士FFT原根作用我们发现，很多多项式系数为整数，而 FFTFFTFFT 引入了毒瘤的虚数，会出现精度误差且运算速度较慢，这时候就需要一个基于整数的的算法来计算多项式的卷积。做法我们先来考虑为什么 FFTFFTFFT 要用到虚数( nnn 次单位根作为点表示法的横坐标)。因为它能优化运算次数(废话)。那是什么让他可以优化运算次数呢?FFT板子#include<cmath>#include<cstdio>#include<
2022-10-25 14:34:26
255
原创 ABC193 E-Oversleeping 题解
暴力做法:按题意模拟正确做法: EXCRTEXCRTEXCRT出题人怕人看不出是解同余方程组，专门把柿子糊脸上了(。根据题意,要找到一个最小时间 ttt 满足这个方程组:{ t≡i (mod (2X+2Y) ) (i∈[X,X+Y))t≡j (mod (
2021-03-07 14:05:39
251
原创 莫比乌斯反演
莫比乌斯函数定义: 将 xxx 质因子分解分解 x=p1d1p2d2p3d3⋅⋅⋅pkdkx=p_{1}^{d_{1}}p_{2}^{d_{2}}p_{3}^{d_{3}}···p_{k}^{d_{k}}x=p1d1p2d2p3d3⋅⋅⋅pkdk.μ(x)={0∃ di≥21x=1(−1)k \mu (x)=\left\{\begin{array}{rcl}0 & & \exists \ d_{i}\ge 2\\1 &
2021-02-20 14:15:20
102
原创 任意模数FFT(拆系数FFT)
作用求多项式卷积对 ppp 取模的结果，ppp 不一定能写成 2k+12^k+12k+1 的形式。做法菜鸡不会三模数只好拆系数将两个多项式拆开乘就不会乘爆，最后加一下取个模就行了。把多项式 (A 和 B)(A\ 和\ B)(A 和 B) 的系数拆成 ai=Ai>>15 , bi=Ai&32767 ,ci=Bi>>15 , &nbs
2021-02-18 17:11:25
403
原创 多项式求逆
前置知识NTT多项式取模: 多项式模 xnx^{n}xn 表示取多项式的前 nnn 位多项式求逆给定f(x)=a0+a1x1+a2x2+⋅⋅⋅+anxnf(x)=a_{0}+a_{1}x^{1}+a_{2}x^{2}+···+a_{n}x^{n}f(x)=a0+a1x1+a2x2+⋅⋅⋅+anxn求出g(x)=b0+b1x1+b2x2+⋅⋅⋅+bkxk (k≤n)g(x)=b_{0}+b_{1}x^{1}+b_{2}x^{2}+···+b_{k}x^{
2021-02-18 16:20:12
303
原创 整 数
数学归纳法(非常有用的证明方法)数学归纳原理(弱归纳)一个包含整数 111 的正整数集合如果具有以下性质，即若其包含整数 kkk ,则其也包含整数 k+1k+1k+1,那么这个集合一定是所有正整数的集合。高考要考的。举个栗子,证明:∑i=1ni2=n(n+1)(n+2)6\sum_{i=1}^{n} i^{2}=\frac{n(n+1)(n+2)}{6}i=1∑ni2=6n(n+1)(n+2)将 n=1n=1n=1 代入得 ∑i=11i2=1\sum_{i=1}^{1} i^{2}
2021-02-14 19:04:54
427
原创 [SDOI2008]递归数列 题解
矩乘板子题k≤15k \le 15k≤15 且 ai=∑j=i1cj∗ai−j (i>k)a_{i}= {\textstyle \sum_{j=i}^{1}}c_{j}*a_{i-j} \ \ \ \ (i>k)ai=∑j=i1cj∗ai−j (i>k) (这一看就很矩乘) 考虑矩阵加速。题目让求一段区间的和，可以转化为两前缀和相减的形式，同时，让矩阵边长加上 111 , 多加的 11
2021-02-05 08:27:55
129
原创 [NOIP2018 普及组] 摆渡车 题解
《关于我上冬令营网课时，听说普及组考过斜率优化DP这件事》题意理解摆渡车往返一次要 mmm 分钟，但摆渡车可以在起点等人，故可以将往返一次的时间 T∈[m,∞)T \in [m,\infty )T∈[m,∞)。(但是个人都不会让他等于正无穷吧?)求这 nnn 个人等待时间之和最小值。设置状态首先，观察数据范围[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z5GpFtYm-1612343806801)(https://s3.ax1x.com/2021/02/02/y
2021-02-03 17:17:05
871
原创 Codeforces #698 (Div. 2) E. Nezzar and Binary String 题解
中文题意:TTT 组数据给你两个长度为 nnn 的01串 s,f,s,f,s,f,有 qqq 次询问。每次询问有区间 [ l,r ][\ l,r\ ][ l,r ] ,如果 [ l,r ][\ l,r\ ][ l,r ] 同时包含000和111，则询问终止，否则你可以改变区间[ l,r ][\ l,r\ ][ l,r ] 内严格小于 lenlrlen_{lr}lenlr 的数字。
2021-02-03 17:16:35
187
原创 poj 1038 Bugs Integrated, Inc. 题解
题面提供一种代码难度比较简单的做法(可能)状态表示：设置状态$ f[i][j] $,表示第 iii 行状态为 jjj 的最大放置数,因为这是个阴间题,因为题目内存设置很小，所以要用滚动数组，存储两行的状态就够了。状态用三进制表示：0 表示当前行和上一行均可用1 表示当前行可用，上一行不可用2 表示当前行和上一行都不可用为了方便不过常数确实略大,我们用两个数组 preprepre , nownownow 分别存放上一行和当前行的状态那么就有:inline int getstate(int
2021-02-03 17:16:04
199
原创 纪念碑 题解
题面题意：在一个有很多矩形覆盖的区域(n,m)内，找到未被覆盖区域中边长最大的正方形。显然，扫描线。考虑用两条扫描线(x=l,x=r)(x=l,x=r)(x=l,x=r)维护(l,0),(r,m)(l,0),(r,m)(l,0),(r,m)这个大矩形区域内纵坐标未被覆盖的最大长度。如图所示：x=l,x=rx=l,x=rx=l,x=r两条线段即为要维护的扫描线。根据肉眼观察:扫描线与区域范围所成的大矩形中纵坐标未被覆盖的最大长度就是蓝紫色标识的范围;在这种情况下大矩形中最大正方形边长就是l−
2021-02-03 17:15:10
342
原创 NOIP2020 T2 字符串匹配题解
首先考虑O(n^3)的暴力怎么写。显然，可以枚举字符串AAA+BBB的右端点，左端点显然是1，暴力判断是否能与后面的字符构成循环节，对于满足k∗(A+B)+C=k*(A+B)+C=k∗(A+B)+C= 整个字符串(k∈Z)(k \in Z)(k∈Z)的情况暴力枚举AAA,BBB分界点，对于L(x)≤R(x)L(x)\le R(x)L(x)≤R(x)的情况统计答案即可，L(x)L(x)L(x)为111到nnn出现奇数次的字符数量，R(x)R(x)R(x)为xxx到nnn出现奇数次的字符数量。其实这样由
2021-02-03 17:11:51
584
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人