問題#
マスター#
ljt12138 はまず $n$ 個のテスラ電磁塔を建てました。これらの電塔は一列に並び、左から右に順番に $1$ から $n$ まで番号が付けられています。第 $i$ 個の電塔の高さは $h [i]$ です。
建築のマスターはその中からいくつかの電塔を選び、その電塔は地下に縮むことになります。この時、地上に残る電塔の高さが左から右に等差数列を形成している場合、その選択方案は美観があると見なされます。
建築のマスターは、美観のある選択方案がいくつあるかを求める必要があります。答えは $998244353$ で割った余りです。
注意してください。地上に残る電塔が 1 つまたは 2 つだけの場合、その方案も美観があります。地上に電塔がない方案は不美観と見なされます。
また、等差数列の公差は負の数でも構いません。
$v$ を最高の電塔の高さとします。
$100%$ のデータに対して、$n \le 10^3$、$v \leq2 \times 10^4$ です。
解答#
f[i][j] を、i で終わる公差 j の（長さが 2 より大きい）方案数とします。
これにより、遷移が可能です。
遷移の際、第二位は v ではなく i を列挙することもできます。
コード#
#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;
}