题解

题意

给定一个长度为$n$的数列$a$，求出当子序列长度为$k$时且构成等差数列的方案数

思路

$k=1$时，方案数就为$n$,$k=2$时方案数为$n*(n-1)/2$也就是长度为2的子序列个数，因为这两种情况必定构成等差数列。
当$k\geq3$时，就有不同情况了。
假设三个数$a_i,a_j,a_m(i>j>m)$，当$a_i-a_j=a_j-a_m$时它们满足条件。
因此我们定义$dp[i][j][k]$为最后一个数为$a_i$，该等差数列上一个数为$a_j$且长度为$k$的方案数
那$dp[i][j][k]$该怎么得到呢，就是由$dp[i][j][k]$加上每个满足条件的$dp[j][m][k-1]$（也就是当$a_i$还没加入这个等差数列时的方案数）
那么状态转移方程就是$dp[i][j][k]=(dp[i][j][k]+dp[j][m][k-1])\mod 998244353$

代码实现

#include<iostream>
using namespace std;
typedef long long ll;
const int N=100;
const ll mod=998244353;
int n;
ll a[N],dp[N][N][N],ans[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        for(int j=1;j<=n;j++)
            dp[i][j][2]=1;
    }
    ans[1]=n;
    ans[2]=n*(n-1)/2;
    for(int k=3;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                for(int m=1;m<j;m++){
                    if(a[j]-a[m]==a[i]-a[j])
                        dp[i][j][k]=(dp[i][j][k]+dp[j][m][k-1])%mod;
                }
            }
        }
    }
    for(int k=3;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
                ans[k]=(ans[k]+dp[i][j][k])%mod;
    for(int k=1;k<=n;k++){
        printf("%lld ",ans[k]);
    }
    return 0;
}