histcat

Title#

Master#

ljt12138 first built $n$ Tesla electromagnetic towers, which are arranged in a row, numbered from $1$ to $n$ from left to right, with the height of the $i$-th tower being $h[i]$.

The architect needs to select some towers, and then these towers will shrink underground. At this point, if the heights of the towers left above ground form an arithmetic sequence from left to right, then this selection scheme will be considered aesthetically pleasing.

The architect needs to find out how many aesthetically pleasing selection schemes there are, with the answer modulo $998244353$.

Note that if only one or two towers are left above ground, then this scheme is also considered aesthetically pleasing. A scheme with no towers above ground is considered not aesthetically pleasing.

Also, note that the common difference of the arithmetic sequence can also be negative.

Let $v$ be the height of the tallest tower.

For $100%$ of the data, $n \le 10^3$, $v \leq2 \times 10^4$.

Solution#

Let f[i][j] be the number of schemes ending with $i$ and having a common difference of $j$ (length greater than two).

Then it can be transferred.

During the transfer, the second position can also enumerate $i$ instead of $v$.

Code#

#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];//represents the number of schemes ending with the $i$-th number and having a common difference of $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;
}