把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1561D1 Up the strip(simple version)
题目大意：给两个数，n（范围为2e5）和m，你可以对n进行下列操作之一：①使得n=n-x，②使得n=n/x，其中x不得超过n，第二种中x不得为1，求最终使得n=1的方案数，对m取模。

解：

非常纯粹的题目，纯粹到只给你两个数字（笑。
这题如果仅仅是求路径倒是还好，最烦的地方在于同样的路径可以有多种……比如3一步到1，可以是3/3也可以是3/2,10000到1更是只要除以5000以上的数都可以办到……
通过观察（找规律）发现，一个数n除到另一个数k的方案数为n/k-n/(k+1)，有了这个，线性dp就可以实现，但关键是这样一做复杂度就O(n2)了，属实不太能接受。
但实际观察就能发现三点①一个数要通过另一个数除得，另一个数首先必须大于等于其两倍（废话），②超过一定范围之后，越大的数除得多个数来获得一个数时，目标数就越小（废话），③假设一个数n除以k能得到的数为fn(k)，可以发现k超过一定范围之后n(k)就恒等于1了，而再此之前fn(k)都是相对离散的（实际上未必真的离散，但是已经够了）。
因此我们从k=2开始，由于数值fn(k)和fn(k+1)在这种情况下相差很大，所以很快我们就能找到这个离散形式分布的终点：当fn(k)最终等于fn(k+1)的时候。
接下来才是重点，如果我们接下去让k相加，最后碰到的是标志性的一大块n(k)值连续的值，那么有没有什么方法直接处理这些值呢？有，我们反过来。
记录下当n(k)等于n(k+1)的时候的k值，并计算出n/k，很容易发现，对于所有i 再加上一些细枝末节的东西，包括n直接除到1的做法和n直接减到1的做法。
复杂度为O(nk)，其中k表示n(k)==fn(k+1)时k的值，这个值是不会很大的，可以自行想想为什么。
在除法相关的题中非常经典的一道题了，既有思维又有dp，做出来之后成就感还是不错的（虽然做的时候非常痛苦就是了……）

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
using namespace std;
ll dp[maxn], qzh[maxn];
inline ll cnt(ll n, ll x) {
	return n / x - n / (x + 1);
}
int main()
{
	cfast;
	ll n, m;
	cin >> n >> m;
	inc(i, 2, n + 1) {

		int now = 2,now1=2;
		while (now1 <= i / 2) {
			if (i / now1 == i / (1 + now1))break;
			dp[i] += dp[i / now1];
			dp[i] = dp[i] % m;
			now1++;
		}
		int mk = i / now1;
		while (now<=mk) {
			int ct = cnt(i, now);
			dp[i] += ct * dp[now];
			dp[i] = dp[i] % m;
			now++;
		}
		dp[i] += 1 + cnt(i, 1) + qzh[i - 1];
		dp[i] = dp[i] % m;
		qzh[i] = (qzh[i - 1] + dp[i]) % m;
		//cout <<"dp."<<i<<" = " <<dp[i] << endl;
	}
	//cout << endl;
	cout << dp[n];
}