【解题报告】洛谷P6189 跑步

题目链接

https://www.luogu.com.cn/problem/P6189

思路

发现相当于给一个数字 nn ，问你有多少种方法能使得一个不递减序列的和为 nn

这实际上是一个分拆数的模板题目

根据OIES，这个分拆数的伪代码是

1
2
3
4
5
6
7
8
9
>def A000041(n):
   if n == 0: return 1
   S = 0; J = n-1; k = 2
   while 0 <= J:
       T = A000041(J)
       S = S+T if is_odd(k//2) else S-T
       J -= k if is_odd(k) else k//2
       k += 1
   return S

然后我们就把它翻译成C++就好了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=100005;
int n,p;
int f[maxn]; 
int main()
{
	cin>>n>>p;
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		int j=i-1,k=2;
		while(j>=0)
		{
			if((k/2)%2==1)
			f[i]=(f[i]+f[j])%p;
			else
			f[i]=(f[i]-f[j]+p)%p;
			if(k&1)
			j-=k;
			else
			j-=(k/2);
			k++;
		}
	}
	cout<<f[n]<<'\n';
	return 0;
}