分类 - 数论、数学

? 解题记录 ? ? 组合数 ? ? 动态规划 ? ? UOJ ?    2018-12-19 14:41:24    395    0    0
我是原题 题目等价于求最长下降子序列长度不超过2" role="presentation" style="position: relative;">222的排列个数,否则就不可能让冒泡排序在复杂度下限。 先想一个dp" role="presentation" style="position: relative;">dpdpdp做法:设f(i,j)" role="presentation" style="position: relative;">f(i,j)f(i,j)f(i,j)是放到了第i" role="presentation" style="position:
? 解题记录 ? ? BZOJ ? ? 模拟 ?    2018-12-19 12:10:04    402    0    0
【题目描述】给出一个N个顶点、M条边的无向图,边(u,v)有权值w(u,v),顶点i也有权值p(i), 并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。 现在要将顶点i的权值减去z(i),其中0≤z(i)≤p(i)。 修改后设顶点i的权值p'(i)=p(i)-z(i),对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。 求sum{z(i)}的最小值和最大值。   【输入】第一行两个正整数n,m (n≤500,000, m≤3,000,000)。 第二行n个整数,依次表示p(1),p(2),...,p(n) (0≤p(i)≤10^6)。 下面m行,
? 解题记录 ? ? SPOJ ? ? 原根 ?    2018-12-19 11:24:41    429    0    0
题目描述 给你一个质数p" role="presentation" style="position: relative;">ppp以及n" role="presentation" style="position: relative;">nnn组询问, 判定给定的r" role="presentation" style="position: relative;">rrr是否为p" role="presentation" style="position: relative;">ppp的原根。 输入输出格式 输入格式 题目有多组测试数据。 每组测试数据的第一行两
? 解题记录 ? ? BZOJ ? ? 二次剩余 ? ? BSGS ?    2018-12-19 10:52:32    566    0    0
Description Fib数列为1,1,2,3,5,8... 求在Mod10^9+9的意义下,数字N在Fib数列中出现在哪个位置 无解输出-1 Input 一行,一个数字N,N < = 10^9+9 Output 如题 Sample Input 3 Sample Output 4 109+910^9+9明示55有二次剩余。 考虑FibFib的通项公式: fn=1√5((1+√52)n−(1−√52)n) f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\
? 类欧几里得 ?    2018-12-19 10:49:10    1660    0    0
类欧几里得是统计直线下整点贡献的一种套路,最常见的类欧几里得是求: &#x2211;i=0n&#x230A;ai+bc&#x230B;" role="presentation" style="position: relative;">∑i=0n⌊ai+bc⌋∑i=0n⌊ai+bc⌋ \sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor 也就是直线ax+bc" role="presentation" style="position: relative;">ax+bcax+bc\fr
? 解题记录 ? ? BZOJ ? ? 类欧几里得 ?    2018-12-18 18:57:19    374    0    0
题意: 给定a,b,c" role="presentation" style="position: relative;">a,b,ca,b,ca,b,c,求满足方程Ax+By&#x2264;C" role="presentation" style="position: relative;">Ax+By≤CAx+By≤CAx+By\le C的非负整数解 A,B&#x2264;109,C&#x2264;Min(A,B)&#x2217;109" role="presentation" style="position: relative;">A,B
? 解题记录 ? ? 莫比乌斯函数 ? ? 亚线性筛 ?    2018-12-09 17:39:22    175    0    0
Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaution N2−3N+2=∑d|Nf(d) calulate ∑Ni=1f(i) mod 109+7. Input the first line contains a positive integer T,means the number of the test cases. next T lines there is a number
? 解题记录 ? ? LOJ ? ? 生成函数 ? ? 期望概率 ? ? FFT|NTT ?    2018-12-09 16:21:41    430    0    0
题目地址:"噔" 题目给定的条件不太好求。 发现原题死了人之后概率的分母会变,十分不可做。 然后就有一步神转化了,我们将原题改为打死人之后这个人并不出局,而是被打上标记。如果开枪射中打标记的人,那么这一枪无效,重新射击。 这样我们发现,分母一定了,容易了许多。 整理一下,发现我们没有办法确切算出1" role="presentation" style="position: relative;">111在最后一个死的概率,但是我们可以确切算出至少有k" role="presentation" style="position: relative;">kkk个人死在1"
? 解题记录 ? ? LOJ ? ? 组合数 ? ? 动态规划 ?    2018-12-05 20:07:46    695    0    0
题目地址:大家好,我是"题目地址" 想比较不容易偏,但写着细节贼多的题。 首先考虑最优策略,注意到题目给出强化牌的wi&gt;1" role="presentation" style="position: relative;">wi>1wi>1wi>1的条件。 因此,优先打出最大的强化牌一定是最优的,考虑选择了两张最大的攻击牌,仍然与选择最小的强化牌等价。 接下来我们考虑选牌的情况: 设拿到了强化牌c" role="presentation" style="position: relative;">ccc张,攻击牌m&#x2212;c
? 解题记录 ? ? UOJ ? ? 生成函数 ? ? FFT|NTT ? ? 牛顿迭代 ?    2018-11-25 15:19:16    607    0    0
(题目背景)是没有的。 你有一个01" role="presentation" style="position: relative;">010101序列,初始时序列为空。你可以对序列进行两种操作: 在序列末端插入一个0" role="presentation" style="position: relative;">000。 在序列中删去一个子序列,并在序列末端插入一个1" role="presentation" style="position: relative;">111。这里对子序列的选取有一定限制,设子序列中包含x" role="presentation"