P4933 大師 - histcat

題目#

大師#

ljt12138 首先建了 $n$ 個特斯拉電磁塔，這些電塔排成一排，從左到右依次標號為 $1$ 到 $n$，第 $i$ 個電塔的高度為 $h [i]$。

建築大師需要從中選出一些電塔，然後這些電塔就會縮到地下去。這時候，如果留在地上的電塔的高度，從左向右構成了一個等差數列，那麼這個選擇方案就會被認為是美觀的。

建築大師需要求出，一共有多少種美觀的選擇方案，答案模 $998244353$。

注意，如果地上只留了一個或者兩個電塔，那麼這種方案也是美觀的。地上沒有電塔的方案被認為是不美觀的。

同時也要注意，等差數列的公差也可以為負數。

設 $v$ 為最高的電塔高度。

對於 $100%$ 的數據，$n \le 10^3$，$v \leq2 \times 10^4$。

題解#

設f[i][j]為以 i 結尾的，公差為 j 的（長度大於二的）方案數

則可以轉移

轉移的時候第二位可以也枚舉 i 而不是 v

代碼#

#include<bits/stdc++.h>
using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

const int N = 1e3 + 10, M = 5e4 + 1000;

int f[N][M];//表示以第i個數結尾，公差為j的方案數 
int n, a[N];
const int x = 20010;
long long ans;
int main()
{
	n = read();

	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}

	for(int i = 1;i <= n;i++)
	{
		ans ++;
		for(int fl = 1; fl < i;fl++)
		{
			f[i][a[i] - a[fl] + x] += f[fl][a[i] - a[fl] + x] + 1;
			f[i][a[i] - a[fl] + x] %= 998244353;
			ans += (f[fl][a[i] - a[fl] + x] + 1) % 998244353;
		}
	}


	cout << ans % 998244353;


	return 0;
}