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;
}