题意 给定一个长度为nnn的数列aaa，求出当子序列长度为kkk时且构成等差数列的方案数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路 k=1k=1k=1时，方案数就为nnn,k=2k=2k=2时方案数为n∗(n−1)/2n*(n-1)/2n∗(n−1)/2也就是长度为2的子序列个数，因为这两种情况必定构成等差数列。 当k≥3k\geq3k≥3时，就有不同情况了。 假设三个数ai,aj,am(i>j>m)a_i,a_j,a_m(i>j>m)ai ,aj ,am (i>j>m)，当ai−aj=aj−ama_i-a_j=a_j-a_mai −aj =aj −am 时它们满足条件。 因此我们定义dp[i][j][k]dp[i][j][k]dp[i][j][k]为最后一个数为aia_iai ，该等差数列上一个数为aja_jaj 且长度为kkk的方案数 那dp[i][j][k]dp[i][j][k]dp[i][j][k]该怎么得到呢，就是由dp[i][j][k]dp[i][j][k]dp[i][j][k]加上每个满足条件的dp[j][m][k−1]dp[j][m][k-1]dp[j][m][k−1]（也就是当aia_iai 还没加入这个等差数列时的方案数） 那么状态转移方程就是dp[i][j][k]=(dp[i][j][k]+dp[j][m][k−1])mod  998244353dp[i][j][k]=(dp[i][j][k]+dp[j][m][k-1])\mod 998244353dp[i][j][k]=(dp[i][j][k]+dp[j][m][k−1])mod998244353 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现