思路:
- 遇到字典序 一般就是要 从左边到右边一个一个贪心的比较, //////////// 边界条件.
- 于是由此DP, dp[i],表示i之前都是一样的 i 这个地方比他bi 小的 种类数
- 关键是 后面这个 有重复元素的组合情况:
- 结论 有n个数 然后 有些数是重复的, 他的组合情况是: n!/num[i]..... 就是除以每一个数出现次数的阶层即可
- 递推维护这个式子
- 少一个数, 就是 *num[i]/n (当前个数) n--,
- 在更新 选一个数比ti小时, 就 先/n, 在看 这些比ti小的数的个数和, 利用树状数组维护
- 把他变成一样的时候, 同理维护
#include <bits/stdc++.h> using namespace std; #define ri register int #define M 2000005 int n,m; long long num[M],p[M],t[M]; const int mod=998244353; long long inv[M]; long long ksn(long long a,long long b) { long long ans=1; while(b) { if(b&1) ans=ans*a%mod; b>>=1;a=a*a%mod; } return ans; } long long ans=1; int val[M]; void add(int a) { while(a<=2e5) { val[a]++; a+=a&(-a); } } void del(int a) { while(a<=2e5) { val[a]--; a+=a&(-a); } } int qu(int a) { int ans=0; while(a>=1) { ans+=val[a]; a-=a&(-a); } return ans; } long long inv2[M]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(ri i=1;i<=n;i++) { cin>>p[i]; num[p[i]]++; add(p[i]); } for(ri i=1;i<=m;i++) cin>>t[i]; for(ri i=1;i<=n;i++) { ans=ans*i%mod; inv[i]=ksn(ans,mod-2); } for(ri i=1;i<=n;i++) { inv2[i]=ksn(i,mod-2); } for(ri i=1;i<=200000;i++) { if(num[i]) /////////////////////// i nong cheng = p[i] { ans=ans*inv[num[i]]%mod; } } long long ans2=0; long long cnt=n; for(ri i=1;i<=min(n,m);i++) { long long tmp=qu(t[i]-1); ans2+=tmp*ans%mod*inv2[cnt]%mod; ans2%=mod; if(num[t[i]]==0) break; del(t[i]); ans=ans*inv2[cnt]%mod*num[t[i]]%mod; num[t[i]]--; cnt--; if(i==min(n,m)) { if(n<m) ans2=(ans2+ans)%mod; } } cout<<ans2; }View Code
后记:
- i 不要 弄成p[i], 搞一个乌龙
- 边界(包含左和右)条件特判
标签:序小,longlong,int,long,num,数学,ans,ri,dp From: https://www.cnblogs.com/Lamboofhome/p/16851077.html