标签：int long 序列 立方 DP 255
- 直接做很难下手。考虑“出现次数的立方值”的组合意义，就是在原序列中选三个相同的子序列的方案数，然后DP即可
- 利用容斥原理计算高维前缀和
- 老生常谈的取模后运算得负数的问题
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int a[255];
long long f[255][255][255],sum[255][255][255];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(a[i]==a[j]&&a[j]==a[k])
{
f[i][j][k]=(sum[i-1][j-1][k-1]+1)%mod;
}
sum[i][j][k]=(sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1]+f[i][j][k])%mod;
}
}
}
cout<<(sum[n][n][n]+mod)%mod<<endl;
return 0;
}
标签：int,
long,
序列,
立方,
DP,
255
From： https://www.cnblogs.com/watersail/p/18312314