（才了解到根号分治这样的妙方法……）

将每个数当成一种物品，最终要凑成n，这就是一个完全背包问题，复杂度O(n2)，可以得80分（在考场上貌似足够了……）

1 #include
2 //#define loveGsy
3 #define N 1000005
4 using namespace std;
5 int f[N];
6
7 int main() {
8 #ifdef loveGsy
9 freopen("a.in", "r", stdin);
10 freopen("a.out", "w", stdout);
11 #endif
12 int n, p;
13 cin >> n >> p;
14 f[0] = 1;
15 for (int i = 1; i <= n; i++)
16 for (int j = i; j <= n; j++)
17 f[j] = (f[j-i] + f[j]) % p;
18 cout << f[n] <<endl;
19 return 0;
20 }

接着采用根号分治，将1~n这些数由sqrt(n)分成两半，前一半还是用完全背包的做法，复杂度O(n*sqrt(n))，再考虑另一种DP，gi,j表示从sqrt(n)~n之间选i个数，它们的和为j。

转移方程是g[i][j]=g[i][j-i]+g[i-1][j-m]。其中m就是sqrt(n)。g[i][j-i]可以理解为给数集中的每个数都加上1，g[i-1][j-m]理解为在数集中加入m这个数。两种DP统计完之后合并就行了（乘法原理），前一个为i，后一个就是n-i。

那么第二种DP为什么可以用呢？，因为从m~n之间选的数的个数一定不超过m，复杂度也就是O(n*sqrt(n))。

1 #include
2 #define ll long long
3 using namespace std;
4 const int N = 1e5 + 10;
5
6 int n, p, m; ll ans = 0;
7 int f[N], g[410][N];
8
9 signed main() {
10 cin >> n >> p;
11 m = sqrt(n) + 1;
12 f[0] = 1;
13 for (int i = 1; i < m; i++) 14 for (int j = i; j <= n; j++) 15 f[j] = (f[j] + f[j - i]) % p; 16 g[0][0] = 1; 17 for (int i = 1; i < m; i++) 18 for (int j = i; j <= n; j++) { 19 g[i][j] = g[i][j - i]; 20 if (j >= m) g[i][j] = (g[i][j] + g[i - 1][j - m]) % p;
21 }
22 for (int i = 0; i <= n; i++) {
23 int sum = 0;
24 for (int j = 0; j < m; j++) sum = (sum + g[j][n - i]) % p;
25 ans = (ans + 1ll * f[i] * sum) % p;
26 }
27 cout << ans << endl;
28 return 0;
29 }