做学校和企业对接的网站,网站开发培训光山,企业所得税2021最新,广元市建设局官方网站来源
题目 Problem Description 给定长度为 N 的序列 a。 一个序列有很多个子序列#xff0c;每个子序列在序列中出现了若干次。 小马想请你输出序列 a 每个非空子序列出现次数的立方值的和#xff0c;答案对 998244353 取模。 你可以通过样例解释来辅助理解题意。 Input 第…来源
题目 Problem Description 给定长度为 N 的序列 a。 一个序列有很多个子序列每个子序列在序列中出现了若干次。 小马想请你输出序列 a 每个非空子序列出现次数的立方值的和答案对 998244353#8203; 取模。 你可以通过样例解释来辅助理解题意。 Input 第一行包含 1 个正整数 N。 第二行包含 N 个正整数第 i 个正整数表示 ai1≤ai,N≤250。 Output 输出共 1 行输出 1 个整数表示最终答案答案对 998244353 取模。 Sample Input 3 1 2 2 Sample Output 19 思路 这题需要换一个角度把题变成这样有三个相同的序列s1,s2,s3设a,b,c分别是它们三个的子序列问有多少种情况满足abc 可以发现这个问题和题目要求的答案是同样的。 设dp[i][j][k]表示以s1,s2,s3分别以i,j,k位置结尾的子序列对答案的贡献f[i][j][k]表示所有的s1中的1到is2中的1到js3中的1到k位置的贡献之和f其实就是一个三维的前缀和。 考虑dp的转移如何s1[i]s2[j]s3[k]即a[i]a[j]a[k]整体的答案应该是前i-1,j-1,k-1位的答案之和的两倍加上1所以增加的贡献就是前面这些的贡献之和加上一 三维前缀和的算法基本就是类似容斥的原理。 代码 #include bits/stdc.husing namespace std;
#define int long long
const int N 260;
const int mod 998244353;
const int INF 0x3f3f3f3f;int a[N];
int dp[N][N][N];
int f[N][N][N];void solve() {int n;cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){for(int j1;jn;j){for(int k1;kn;k){if(a[i]a[j]a[j]a[k])dp[i][j][k](f[i-1][j-1][k-1]1)%mod;f[i][j][k](((((((dp[i][j][k]f[i-1][j][k])%modf[i][j-1][k])%modf[i][j][k-1])%modf[i-1][j-1][k-1])%mod-f[i-1][j-1][k]mod)%mod-f[i-1][j][k-1]mod)%mod-f[i][j-1][k-1]mod)%mod;}}}coutf[n][n][n];
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t 1;
// cint;while (t--) solve();return 0;
}
