2020NOI在线能力测试【入门组】跑步

天，我似乎要掉到PJ了。。。

题意就是让你把n分成若干个块，大小从小到大排序后的不同的方案数。

很容易想到(DP)，设(f[i][j])表示和为(i)，有(j)个数的方案数。
转移：(f[i][j]=f[i-1][j-1]+f[i][j-i])
我们可以多添加一个新的(1)，也可以在原有的数上全部加(1)。
时间复杂度(O(n^2))

然后我懵了，怎么办？
想着打表找规律，结果(GG)。
题解是分块（雾）。我们把(<=sqrt(n))和(>sqrt(n))的分开来讨论。

(<=sqrt(n))

我们可以设(g[i][j])表示和为(i)，用小于等于(j)的数构造的方案数。
转移：(g[i][j]=g[i-j][j]+g[i][j-1])
我们可以加一个(j)的数，也可以增大取值范围（可以理解为不再加(j)了）

(>sqrt(n))

跟(O(n^2))的做法有点类似。
但是我们每次添加一个新的数，是以(sqrt(n)+1)为基础的，而不是(1)。
也就这里改改而已。
然后我们发现这两个刚好互补。于是可以乘法计算答案。

(Code)

#include <cstdio>
#include <cmath>
#define N 100010
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define mpy(x, y) memcpy(x, y, sizeof y)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
#define go(x) for (int p = tail[x], v; p; p = e[p].fr)
using namespace std;
int n, p, st, f[N][320], sum[N], g[N], ans = 0, tot = 0;

int main()
{
	freopen("running.in", "r", stdin);
	freopen("running.out", "w", stdout);
	scanf("%d%d", &n, &p); st = sqrt(n); 
	f[0][0] = 1; sum[0] = 1;
	fo(i, 1, n) fo(j, 1, st)
	{
		if (i >= j) f[i][j] = f[i - j][j];
		if (i > st) f[i][j] = ((ll)f[i][j] + f[i - st - 1][j - 1]) % p;
		sum[i] = ((ll)sum[i] + f[i][j]) % p;
	}	
	g[0] = 1;
	fo(i, 1, st) fo(j, i, n)
		g[j] = ((ll)g[j] + g[j - i]) % p;
	fo(i, 0, n) ans = ((ll)ans + (ll)sum[n - i] * g[i]) % p;
	printf("%d
", ans);
	return 0;
}