- 博客(137)
- 收藏
- 关注
RSS订阅
原创 题目整理【持续更新】
1.题目Codeforces 592C简单题意给你一个数t，问你1- t里面有多少个D满足 D % w = D % b。正解思路【GCD && LCM】，思路：M = lcm(w, b)。(1)当M > t时，有ans = min(t, min(w-1, b-1))。(2)当M <= t时，考虑每个lcm(a, b)做出的贡献，可以推出每...
2019-09-24 17:34:13
102
原创 Partial Sums（组合数学+逆元）
You've got an arraya, consisting ofnintegers. The array elements are indexed from 1 ton. Let's determine a two step operation like that:First we build by the arrayaan arraysof partial sums, ...
2020-02-21 15:48:02
372
原创 来自亲爱的队友的题F - Color Stripe（模拟，分情况）
A colored stripe is represented by a horizontal row ofnsquare cells, each cell is pained one ofkcolors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of...
2020-02-16 22:58:25
226
原创 十进制矩阵快速幂解斐波那契数列poj3070
#include <cstdio>#include <iostream>#include <algorithm>#include<cmath>#include<cstring>#define ll long longusing namespace std;ll mod;char n[1000008];void mul(...
2020-02-14 23:15:42
171
原创 SDAU训练指南-数论2O
The Fibonacci number sequence is 1, 1, 2, 3, 5, 8, 13 and so on. You can see that except the first two numbers the others are summation of their previous two numbers. A Fibonacci Prime is a Fibonacci ...
2020-02-13 21:10:31
151
原创 SDAU训练指南-数论2L(等差数列）n*(a1+an)/2
Now a days a very common problem is: “The coordinate of two points in Cartesian coordinate system is (200, 300) and (4000, 5000). If these two points are connected we get a line segment. How many latt...
2020-02-12 20:14:19
254
原创 SDAU训练指南-数论1O欧拉降幂
Finding the exponent of any number can be very troublesome as it grows exponentially. But in this problem you will have to do a very simple task. Given two non-negative numbers m and n, you will have ...
2020-02-09 21:15:52
157
原创 SDAU训练指南-数论1V
代码：#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;typedef long long ll;ll v[36010],prime[36010],m;v...
2020-02-09 20:41:27
165
原创 SDAU训练指南-数论1 —H（最大公共多项式）
Given two polynomials f(x) and g(x) in Zn, you have to find their GCD polynomial, ie, a polynomial r(x) (also in Zn) which has the greatest degree of all the polynomials in Zn that divide both f(x) an...
2020-02-08 15:44:48
167
原创 2020-2-4
最近一直在刷数论专题，codeforce网页太卡，比赛也不多，并且有时候容易出问题，所以做得比较少。题做得挺顺的，简单题还是多的，碰到一些较为复杂的看看题解，花费个两三个小时也都不成问题，刷的过程中一些新的题型也见了些，不过一般数据很大有规律的通常都是先打表观察，仔细推推也较易看出来，真的遇到那些难想的，就比如有些题是结合莫比乌斯反演求解的，感觉并没有什么联系，就算是知道要用莫比乌斯解，自己也还是...
2020-02-06 00:16:50
75
原创 SDAU训练指南-数论1（等差数列+佩尔方程）
A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right...
2020-02-05 22:28:34
297
原创 SDAU训练指南-数论1R（质因数分解+gcd有坑为负数）
We say that x is a perfect square if, for some integer b, x = b 2 . Similarly, x is a perfect cube if, for some integer b, x = b 3 . More generally, x is a perfect pth power if, for some integer b, x ...
2020-02-05 14:15:46
246
原创 SDAU数论练习五（质因数分解，技巧）
The factorial function, n! is defined thus for n a non-negative integer: 0! = 1 n! = n * (n-1)! (n > 0)We say that a divides b if there exists an integer k such that k*a = b...
2020-02-04 15:20:21
145
原创 SDAU数论练习五F（扩展欧几里得）
On one of the Caribbean Islands there areNtourists and you want to move them from this island to another one.There are only two boats on this island, the first one can holdn1tourists and costc1...
2020-02-03 12:54:36
235
原创 C. Enlarge GCD -codeforces1047
Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.A common divisor for two positive ...
2020-02-03 11:45:54
108
原创 CodeForces 633B A Trivial Problem
Mr. Santa asks all the great programmers of the world to solve a trivial problem. He gives them an integermand asks for the number of positive integersn, such that the factorial ofnends with exac...
2020-02-02 17:01:36
97
原创 HDU 6063 RXD and math (数论+快速幂)
RXD is a good mathematician.One day he wants to calculate:∑i=1nkμ2(i)×⌊nki−−−√⌋∑i=1nkμ2(i)×⌊nki⌋output the answer module109+7109+7.1≤n,k≤10181≤n,k≤1018μ(n)=1(n=1)μ(n)=1(n=1)μ(n)=(−1)k(n...
2020-02-01 19:17:42
128
原创 hdu6395 Sequence（矩阵快速幂+分段）
Let us define a sequence as below⎧⎩⎨⎪⎪⎪⎪⎪⎪F1F2Fn===ABC⋅Fn−2+D⋅Fn−1+⌊Pn⌋{F1=AF2=BFn=C⋅Fn−2+D⋅Fn−1+⌊Pn⌋Your job is simple, for each task, you should outputFnFnmodule109+7109+7.InputThe fir...
2020-02-01 14:38:49
177
2
原创 hdu5878 I Count Two Three
I will show you the most popular board game in the Shanghai Ingress Resistance Team.It all started several months ago.We found out the home address of the enlightened agent Icount2three and decided ...
2020-01-31 16:21:28
143
原创 HDU 6441 - Find Integer（费马大定理）
people in USSS love math very much, and there is a famous math problem .give you two integersnn,aa,you are required to find22integersbb,ccsuch thatanan+bn=cnbn=cn.Inputone line contains one...
2020-01-31 15:39:35
97
原创 HDU Problem - 6124 Euler theorem
HazelFan is given two positive integersa,ba,b， and he wants to calculateamodbamodb. But now he forgets the value ofbband only remember the value ofaa, please tell him the number of different poss...
2020-01-29 13:06:13
108
原创 The Counting Problem（规律计数）
Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a = 1024 and b = 1032, the li...
2020-01-27 14:36:02
475
原创 HDU 1098 Ignatius's puzzle数论-扩展欧几里得及线性同余
Ignatius is poor at math,he falls across a puzzle problem,so he has no choice but to appeal to Eddy. this problem describes that:f(x)=5*x^13+13*x^5+k*a*x,input a nonegative integer k(k<10000),to fi...
2020-01-26 20:40:30
1154
原创 HDU 4675 GCD of Sequence(数论+莫比乌斯反演)
Alice is playing a game with Bob.Alice shows N integers a1, a2, …, aN, and M, K. She says each integers 1 ≤ ai≤ M.And now Alice wants to ask for each d = 1 to M, how many different sequences b...
2020-01-26 19:34:36
106
原创 CF1285C Fadi and LCM
C. Fadi and LCMtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputToday, Osama gave Fadi an integerXX, and Fadi was wondering about...
2020-01-20 16:01:31
243
原创 2019-1-19
从14号放假到现在过了有5天了，虽然过的很快吧，但是并没闲着，在学校呆了两天（纯属刚结束考试很累在休息，努力没有白费，各科成绩出来后都很不错），17号到家乡车站就被同学接去拉着各种聚会（囧，喝的睡了十几个小时，醒来又酒精过敏，起小红点），直到昨晚才回到自己家，同学又说来我家玩玩，今天下午才刚送走的。。。。（一群关系超好的狐朋狗友，完全没有办法），晚上登了codeforce看到有比赛就报名了，先刷了...
2020-01-19 23:45:49
67
原创 2020-1-6
2020年里的第一篇博客，哈哈，深夜放毒，最近一段是时间确实在ACM上下的功夫比较少，但是收获还是不小的，因为在复习数据结构，刚好我也在看这一块，在以后的编程中还是有所帮助的。对于我们这些苦逼的数学专业来讲，除了学习过C语言外就没学过别的和计算机相关的课了，（参加过ACM的就另当别论了）。所以挺麻烦的，又复习之前的指针，学了类，一些基本的东西都会了，还有8个排序，树，图，线性表什么的，之前学的也不...
2020-01-06 01:03:31
75
原创 2019-12-29
最近看了些树状数组和线段树的一些知识。之前很多知识都遗忘了，先看了点基础的题，以前发的有些树状数组，线段树和并查集都做了点。树状数组的实现比较容易。这类题的套路还没摸到，思路比较难想，想明白之后的代码很简单。线段树模板修改的事，一般也会和别的题组合求解。做的题和看的不多，以后逐渐熟悉熟悉再总结总结。...
2019-12-29 23:49:01
49
原创 2019-12-26
最近很忙，一直在复习数分，周五考试，数学部分这两天只看看了一些公式推导的博客，打算换个方向，也该起个数据结构的头了，接下来着重于数据结构，数学知识也会隔一段时间复习。...
2019-12-26 00:34:43
118
原创 2019-12-22
最近的数论题感觉像是混合题啊，用的是数论的思想，但是有好多题是dp，做题的时候往这方面想了但是除了期望概率外别的数学题没碰到过还有dp的。所以不敢写，见的题少了还是，虽然想了很长时间但是还是没有写出来，还有些结论题打算整理一下。专业课就要考试了，这两天主要还是复习复习，应付过去再说。...
2019-12-25 21:55:21
63
原创 2019-12-18
这几天刷了些概率期望有关的dp题目，这类题目没有固定的模板，而且概率可以很容易插入一些经典模型，我刷的这部分题目，无一例外均可用dp解决，无非就是先通过公式递推找出各条件下的关系，找出状态转移方程求解，dp还是至关重要，想要在这方面更灵活的运用还要花一些时间。然后就是刷数论题了，这个数论题不难，应该是考察知识面，有些结论我也没见到过，对知识面的扩充很有帮助，其他就是质因数分解，欧拉函数，gcd，因...
2019-12-19 01:34:45
60
原创 2019-12-16
这几天很累包括今晚上，忙各种各样的事情，所以才这么晚写博客，这几天搞了些求概率和期望dp的题，概率要顺着推，期望倒着推。其次就是关于概率DP状态的设计，概率DP的题往往设计状态比较直观，直接按照题意来就可以。关于状态的转移，其最重要的核心就是严格按照全概率公式和全期望公式来递推，要保证枚举出所有可能的状态，并保证他们是互斥的事件并且概率和为1。这部分的题不是很难，简单的推公式找状态。不过自己的dp...
2019-12-16 00:58:07
55
原创 2019-12-11
这两天看的有点心力憔悴，还是在看公式推导，群论和莫比乌斯函数相关的，通过这几天的折磨，有不少的收获，群论别人写的博客不全，离散课本上的挺详细，就在看课本上的定理证明推导，莫比乌斯函数是又补了之前的狄利克雷卷积，积性函数及两积性函数的乘积仍然是积性函数（很有趣的证明，数论书上的，其中跟约数相关，这个性质也即是证明了积性函数的狄利克雷卷积是积性函数，可以发现几乎长得是一样的，不过还没有些地方看的不是很...
2019-12-11 22:21:04
61
原创 2019-12-8
群论定理证明都看懂了，群论也是组合数学的东西，给定一些置换，求在这些置换下得到的不同种类数，Polya定理，或者Burnside引理，一般情况下不能直接用，polya的时间复杂度要比Burnside快但是通常给的n都是1e9，要先筛出一定范围的质数和欧拉函数，小的数直接拿，较大的数再用质数求欧拉函数，再计数求解。又看了康托展开和卡特兰数，挺简单的，推导和实现，也是关于组合数的，但是看博客说康托展开...
2019-12-08 23:49:41
54
原创 2019-12-04
最近在看具体数学和群论，看完了河内塔，约瑟夫环等一些经典问题的推导，以前做这些公式推导题都是直接记公式，现在感觉推导不算难，就是过程繁琐。起初从奇偶性，是否为质数，前后项关系等来看；联系，并列举前几项结果进行观察，再找第n项前后之间的关系，常用数学归纳法证明，得到公式后可利用前几项结果检验。群论一些基本知识：给定一个集合和集合上的二元运算,如果满足以下条件：（1）封闭性。对于任意的成立...
2019-12-05 00:43:37
139
原创 2019-12-1
这两天在做cf上的题，总的来说不是很好，一些模拟题做的很困难，要花费很长时间才能写出来，相比，c题可能比a, b要出的快很多。还是要细心做题，多锻炼。然后补了个遗漏的威尔逊定理，和自己之前省赛的数论题，看懂题解花了一个多小时，这个题挺不容易的，归到数论题里面，但是没有用到怎么卡数论的知识，就是先分类然后推公式求解。看懂之后感觉如果自己推公式熟练的话还是可以出的。接下来就是想多练练推公式的题，看具体...
2019-12-02 00:04:18
66
原创 2091-11-27
昨天在打codeforce，很晚了没来得及写博客，这两天一直在做题，补之前没刷完的专题和cf以前出的比赛，做到每天都至少抽2到3小时训练。
2019-11-28 08:29:49
59
原创 Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)
B. Boxtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputPermutationppp=[p1,p2,…,pn]p=[p1,p2,…,pn]nn11nn[3,4,1,2][3,4,1,2][1][1][1,...
2019-11-26 23:38:58
126
原创 2019年icpc亚洲区域赛上海站 赛后总结
感觉这次比赛成长了许多，但是不知道怎么写。刚翻了很多人的区域赛总结博客。有很多地方触动了我。可能是很多拿金拿银的大佬都习惯于刷知乎吧，看到的都是些铜奖，铜末，打铁的队伍。与我们队的情况有很多相似之处。 他们的心态也容易崩，在赛场上比较容易出的题，也可能做不出来，和我们一样实力还是不足。有的题知道用什么算法不够熟总是wr，有的题很简单但知识点没见过。都挺努力的，付出了不少，但是在这...
2019-11-26 15:13:44
1199
原创 2019-11-20
一直在复习比赛的相关知识，听学长说有3道思维题或者麻烦点的模拟题，不带算法的，较其他题目可能容易出一点，所以重点在这几道题上，到时候还是打算跟榜，算法题的话，模板大概应该能打印差不多100张左右的纸，用不用得到就到时候再说了-_-...心态已非常放松了，哈哈，努力吧！！fighting...
2019-11-20 23:55:20
78
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人