商城网站微信支付接口申请写完html wordpress
来源
题目
Problem Description
给定长度为 N 的序列 a。
一个序列有很多个子序列，每个子序列在序列中出现了若干次。
小马想请你输出序列 a 每个非空子序列出现次数的立方值的和，答案对 998244353​ 取模。
你可以通过样例解释来辅助理解题意。Input
第一行包含 1 个正整数 N。
第二行包含 N 个正整数，第 i 个正整数表示 ai（1≤ai,N≤250）。Output
输出共 1 行，输出 1 个整数，表示最终答案，答案对 998244353 取模。
Sample Input
3 1 2 2
Sample Output
19
思路
这题需要换一个角度，把题变成这样：有三个相同的序列，s1,s2,s3，设a,b,c分别是它们三个的子序列，问有多少种情况满足a=b=c
可以发现这个问题和题目要求的答案是同样的。
设dp[i][j][k]表示以s1,s2,s3分别以i,j,k位置结尾的子序列对答案的贡献，f[i][j][k]表示所有的s1中的1到i，s2中的1到j，s3中的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++.h>using 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;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])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])%mod+f[i][j-1][k])%mod+f[i][j][k-1])%mod+f[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;}}}cout<<f[n][n][n];
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;
// cin>>t;while (t--) solve();return 0;
}