• 欢迎光临~

[CF1716D]Chip Move 题解

开发技术 开发技术 2022-08-05 次浏览

传送门QAQ

题目大意

一个数轴上,有一个芯片初始位置为 (0),它可以向右移动,第 (i) 次移动的距离必须是 (k+i-1) 的倍数,求走到 (1sim n) 每个点的方案数。

(1le k le nle 2times 10^5)

Preface

这道题真的后悔死了,场上就发现了性质,但优化没想出来,结果比赛一结束想出来了QAQ。

(写这篇文章时官方题解还没发布,这个方法是我自己 yy 出来的,可能比官方题解和别的大佬麻烦不少 qwq)

Analysis

首先会发现这题是一个 DP。

先把最简单朴素的 DP 列出来,然后再考虑优化:

(f(i,j)) 表示从 (0)(j) 步到达点 (i) 的方案数。

初始状态:(f(0,0)=1)

状态转移方程:(f(i,j) =sumlimits_{x=1}^{lfloor dfrac{i}{k+j-1} rfloor} f(i-xtimes (k+j-1),j-1))

然鹅这样时空复杂度均无法接受,考虑优化。

我们会发现一个问题:从 (0) 走到 (n) 的最大步数似乎并不是特别多。

假设 (k) 取最小值 (1),每步走的距离都最近,设步数为 (x),则:

(1+2+ldots x= frac{x(x+1)}{2} le n)

这时会发现,最大步数是 (O(sqrt{n})) 级别的,打个表列出来会发现最大也就 (640) 左右。

但是这么大的空间还是无法承受,并且我们上面的 DP 方程达不到 (O(ntimes 640))

(考场上我在这里卡住了,结果一下考场就想出来了 qwq)

观察一下上面的状态转移方程,会发现方程的第一维,(i,i-(k+j-1),i- 2times(k+j-1)ldots) 这样写下去貌似有一些规律。

其实不难发现 (iequiv i-xtimes (k+j-1) pmod{(k+j-1)})

那我们为什么要一点一点往前枚举呢?这完全可以直接开一个数组把前面的贡献全部存起来。

具体而言,令 (cnt(x,y)= sumlimits_{ibmod (k+x)=y}f(i,x))

初始状态:(cnt(0,0)=1)

此时状态转移方程化为:(f(i,j)= cnt(j-1,i bmod (k+j-1)))

每次遍历完 (i),即将遍历 (i+1) 时再维护一下 (cnt) 数组即可。

(cnt(j,ibmod (k+j)) gets cnt(j,i bmod (k+j))+f(i,j))

然鹅我们还要注意一下空间的问题,(f) 数组其实已经不是真正的 DP 数组了,可以把第一维直接省去。

但是 (cnt) 这两维还是很不好处理 o(╥﹏╥)o

此时就要充分发挥我们的乱搞精神,发现 (k le 2times 10^4) 的时候 (cnt) 还是开的下的,而 (kgt 2times 10^4) 时步数和转移次数至多为 (10),直接用我们最上面提到的朴素 DP 即可。

时间复杂度 (O(nsqrt{n})),卡得比较紧,为了常数小一点不建议开 long long

Code

// Problem: D. Chip Move
// Contest: Codeforces - Educational Codeforces Round 133 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1716/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define Chtholly set<node>::iterator
#define SIT set<int>::iterator
#define VEC vector<int>::iterator
#define mp make_pair
#define fir first
#define sec second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int mod = 998244353;
const int INF = 1e9;
const ll INFll = 1e16;
const int maxn = 2e5 + 5;
const int maxm = 3e6 + 5;
const int maxk = 1005;
int n,k;
int f[maxn],dp[maxn][15];
int cnt[maxk][maxk * 25];
void subtask() {
	dp[0][0] = 1;
	for(int i = 1;i < k;++ i) {
		printf("%d ",0);
	}
	for(int i = k;i <= n;++ i) {
		int ans = 0;
		for(int j = 1;j <= 10;++ j) {
			for(int x = 1;x <= i / (k + j - 1);++ x) {
				(dp[i][j] += dp[i - x * (k + j - 1)][j - 1]) %= mod;
			}
			(ans += dp[i][j]) %= mod;
		}
		printf("%d ",ans);
	}
	return ;
}
int main() {
	scanf("%d %d",&n,&k);
	if(k >= 20000) {
		subtask();
		return 0;
	}
	vector<int> G;
	int L[maxn];
	for(int cnt = 0,i = 0;cnt < n;) {
		cnt += k + i;
		++ i;
		G.pb(cnt);
	}
	for(int i = 1;i <= n;++ i) {
		L[i] = upper_bound(G.begin() , G.end() , i) - G.begin();
	}
	++ cnt[0][0];
	for(int i = 1;i <= n;++ i) {
		int ans = 0;
		for(int j = 1;j <= L[i];++ j) {
			f[j] = cnt[j - 1][i % (k + j - 1)];
			(ans += f[j]) %= mod; 
		}
		printf("%d ",ans);
		for(int j = 1;j <= L[i];++ j) {
			(cnt[j][i % (k + j)] += f[j]) %= mod;
		}
	}
	return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿

程序员灯塔
转载请注明原文链接:[CF1716D]Chip Move 题解
喜欢 (0)