[abc] abc 253E - Distance Sequence

前言

t a g : tag : tag: 计数 前缀和优化dp 难
传送门 :

题意 :
给定 N , M N,M N,M询问有多少种序列满足条件

条件如下 :
∀ i   , ( 1 ≤ a [ i ] ≤ M ) \forall i\ ,(1\le a[i] \le M) ∀i ,(1≤a[i]≤M)
∣ a ∣ = N |a|=N ∣a∣=N
∣ a i − a i + 1 ∣ ≥ K |a_i-a_{i+1}|\ge K ∣ai​−ai+1​∣≥K
即长度 N N N,值域是 M M M,相邻元素的差绝对值大于 K K K

思路 :
状态表示 :
d p [ i ] [ j ] dp[i][j] dp[i][j] 前 i i i个并且以 j j j结尾的方案数

状态转移 :
d p [ i + 1 ] [ j ] = ( d p [ i ] [ 1 ] + . . . . + d p [ i ] [ j − K ] ) + ( d p [ i ] [ j + K ] + . . . . d p [ i ] [ M ] ) dp[i+1][j]=(dp[i][1]+....+dp[i][j-K])+(dp[i][j+K]+....dp[i][M]) dp[i+1][j]=(dp[i][1]+....+dp[i][j−K])+(dp[i][j+K]+....dp[i][M])

时间复杂度 O ( N M 2 ) O(NM^2) O(NM2)显然 T L E TLE TLE

但是其实我们并不需要去枚举转移

我们发现,我们可以单独计算出来上一层的 d p [ i ] [ 1 ] + . . . . d p [ i ] [ j − k ] dp[i][1]+....dp[i][j-k] dp[i][1]+....dp[i][j−k] 这种状态

显然这里可以使用到 前缀和进行优化

因此时间复杂度将为 O ( N M ) O(NM) O(NM)

code :

ll f[N][N];
ll s[N];
int n,m,k;

void solve(){
	cin>>n>>m>>k;
	
	
	for(int i=1;i