CFdiv2-Chip Move-(线性dp+状态枚举方式)

D

题意：
就是有n个点，初始在0点，每次你可以跳跃一个长度，但是第一次的长度是k的倍数，第二次是k+1的倍数…(并且是正数)。问你从0跳到x有多少种方案数。x是1到n，分别输出。

思考：
1.对x从1到n分别输出，肯定就是跑一次1到n就处理出来。发现每次跳跃都是正数，那么至少是1+2+3+…，可以发现最多跳650次。
2.那么就可以定义dp为走到i点，跳的是j的倍数。转移的话，肯定是从前面中dp[t][j-1]转移过来的，t和i的距离是j的倍数就行。但是这样又加了个log，复杂度n650log(n)，直接超时。然后我就想了想，要不要每次都枚举t呢？我感觉可以直接从前面一个转移过来，因为以前的点都是重复走的。但是就是这里感觉不知道脑子里想的啥，也没推出来。结束后看了下别人的代码，恍然大悟。就是dp[i][j]直接从dp[i-j][j]转移过来，因为在i-j之前往后跳，方案都是一样的，我直接从dp[i-j][j]跳步到i这里。但是方案还少一点，少哪里？就是从dp[i-j][j-1]跳过来的时候没算。因为dp[i-j][j]，只是从i-j之前的dp[t][j-1]转移过来的。所以加上这个方案就好了，那么就是dp[i][j] = dp[i-j][j]+dp[i-j][j-1]。
3.到这里复杂度就是n*650了，1e8差不多。但是发现数组的话1e8会炸空间， 所以这样就不行了。又观察了下dp的转移方程，第二维每次都是从j或者j-1转移过来。是不是可以先枚举m，再处理n，也就是先对每个n处理第i个。开两个数组，dp是上一层的，tp是这一层的，每次更新tp。然后让dp = tp。这样就完美解决了每次只用上一层的j和这一层的j。
4.对于答案，由于先枚举的m，那么对于不同的j，每次就累加一次答案就可以了。因为定义的是恰好为j的倍数的时候，并不是不超过。一般求方案数都是恰好，这样转移的时候精确明确。
5.对于先枚举n还是先枚举m，要看不同的题目。比如背包问题，先枚举n再枚举m就可以优化掉一维，因为每次就只用上一层的。但是这个题先枚举n再枚举m就没法优化，因为不仅要用这一层的，还要用上一层的。所以对于这种一般就是先枚举m了。

代码：

最开始的想法：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 998244353,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int dp[N][640];

signed main()
{
	IOS;
	cin>>n>>k;m = 635;
	for(int i=1;i<=n;i++) dp[i][k] = (i%k==0);
	for(int i=1;i<=n;i++)
	{
		for(int j=k+1;j<=m;j++)
		{
			for(int t=j;i-t>=0;t+=j)
			dp[i][j] = (dp[i][j]+dp[i-t][j-1])%mod;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int sum = 0;
		for(int j=k;j<=m;j++) sum = (sum+dp[i][j])%mod;
		sum = (sum%mod+mod)%mod;
		cout<<sum<<" ";
	}
	return 0;
}

优化时间后的：
#include
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 998244353,inf = 1e9;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int dp[N][200];

signed main()
{
	IOS;
	cin>>n>>k;m = 150;
	for(int i=1;i<=n;i++) dp[i][k] = (i%k==0);
	for(int i=1;i<=n;i++)
	{
		for(int j=k+1;j<=m;j++)
		{
			if(i>=j) //要么从j层过来要么从j-1层来
			dp[i][j] = (dp[i-j][j]+dp[i-j][j-1])%mod;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int sum = 0;
		for(int j=k;j<=m;j++) sum = (sum+dp[i][j])%mod;
		sum = (sum%mod+mod)%mod;
		cout<<sum<<" ";
	}
	return 0;
}

优化空间后的:
#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 998244353,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int dp[N];
int tp[N];
int anw[N];

signed main()
{
	IOS;
	cin>>n>>k;m = 650;
	dp[0] = 1;
	while(m--)
	{
		for(int i=0;i<=n;i++) tp[i] = 0;
		for(int i=k;i<=n;i++) tp[i] = (dp[i-k]+tp[i-k])%mod;
		for(int i=0;i<=n;i++) dp[i] = tp[i];
		for(int i=1;i<=n;i++) anw[i] = (anw[i]+tp[i])%mod;
		k++;
	}
	for(int i=1;i<=n;i++) cout<<anw[i]<<" ";
	return 0;
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

总结：
多想一想，别总是觉的不简单啥的，不难，多想想就可以了。