题目大意:
- 给出一个序列P , n 个点
- 每次可以选择2个 相邻区间进行合并, 会产生一个贡献值,当然合并n-1就合并完了, 问在所有的情况下, 贡献和是多少
思路:
- 易错点:
- 这个所有情况, 你枚举的合并的那个先后顺序是有关系的!!!
- 因此直接去区间dp只能把各个合并的情况给弄出来,但是他的先后顺序是给定的!!!!
- 将合并2个区间的操作 转化成-> 点亮 i 和 i+1之间的边, 这样就转化为了组合数问题,
- 考虑 l-r区间的值 会被贡献几次, 从整体上看, 选的点,他一定是比左右端点连着的2个边先选, 就利用组合数去做就彳于了
#include <bits/stdc++.h> using namespace std; #define ri int #define M 2000005 int n,m; long long arr[M]; long long dp[M]; const int mod=998244353; long long inv[M]; long long ksn(long long a,int b) { long long ans=1; while(b) { if(b&1) ans=ans*a%mod; b>>=1;a=a*a%mod; } return ans; } long long C(int a,int b) { if(a<b) return 0; if(b==0) return 1; if(a==b) return 1; return dp[a]*inv[a-b]%mod*inv[b]%mod; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; for(ri i=1;i<=n;i++) { cin>>arr[i]; arr[i]+=arr[i-1]; arr[i]%=mod; } dp[0]=1; for(ri i=1;i<=n;i++) { dp[i]=dp[i-1]*i%mod; inv[i]=ksn(dp[i],mod-2); } long long ans=0; for(ri k=2;k<=n;k++) { for(ri i=1;(i+k-1)<=n;i++) { int j=i+k-1; int tmp=0; if(i>1) tmp++; if(j<n) tmp++; for(ri g=(j-i);g<=n-1-tmp;g++) { ans+=(arr[j]-arr[i-1]+mod)%mod*C(g-1,j-i-1)%mod*dp[j-i]%mod*dp[n-1-j+i-tmp]%mod*dp[tmp]%mod*C(n-1-tmp-g+1+tmp-1,tmp)%mod; ans%=mod; } } } cout<<ans; }