题解 P3270 【[JLOI2016]成绩比较】

开始的时候这么多量我是一头雾水，所以只好一点点求。 //所涉及到的变量如未特殊声明即为题目中的变量 . 1.首先根据题意同学们是互不相同的。(显然...) $k$ 名同学被B神碾压。$k$ 名同学的组成共有 $C^k_{n-1}$ 种方式。 2.嗯..然后 $n-k-1$ (记为 $num$ ) 名同学是没有被B神碾压的，所以每人都至少有一科比B神高。 3.再然后，B神排名是已知的，所以考虑比B神某科高的人出现在 $num$ 名同学中的方案。显然为 $C^{Rk-1}_{num}$。 4.把 $m$ 科一起算，计 $T_{num}$ 为m个科目分给 $num$ 人的方案数，为 $$T_{num}=\prod_{k=1}^{m} {C^{R_k-1}_{num}}$$ 5.不过有个问题，$num$ 人不被B神碾压，要求每个人都至少有一科比B神高，这样计算会出现只涉及到一部分人的情况。 容斥一下。得 $$T=\sum_{i=0}^{num}(-1)^{num-i} C_{num}^i T_{i}$$ $$=\sum_{i=0}^{num}(-1)^{num-i} C_{num}^i\prod_{k=1}^{m} {C^{R_k-1}_{i}}$$ 那么到现在 $C^{k}_{n-1}T$ 即为同学比B神的成绩相对大小的方案数。不过还没有考虑分数的问题。 6.先考虑单科，考虑某一科满足B神排名为 $Ri$ 的方案数。 7.首先，$n$ 个同学分布在 $x$ 分内的方案显然为 $x^n$ (最低为1分，开始我没好好读题以为可以有0分卡了好久)，因为我们只是考虑同学与B神的分数高低方案，同学间的高低没算在内，所以不是组合数形式... 因为 $Ri-1$ 名同学必须严格大于B神，$n-Ri$ 名同学是小于等于B神，所以不能简单乘一乘，那就枚举b神的分数 $$Si=\sum_{x=1}^{Ui} x^{n-Ri}(Ui-x)^{Ri-1}$$ 这显然会T，因为 $Ui$ 很大。 8.所以~~根据经验~~就乱搞一下———把后面的$(Ui-x)^{Ri-1}$展开~~应该会很不错~~。然后交换一下求和的顺序。 $$Si=\sum_{x=1}^{Ui} x^{n-Ri}(Ui-x)^{Ri-1}$$ $$=\sum_{x=1}^{Ui} x^{n-Ri} \sum_{t=0}^{Ri-1}(-1)^t C^t_{Ri-1}Ui^{Ri-1-t}x^t$$ $$=\sum_{x=1}^{Ui} \sum_{t=0}^{Ri-1}(-1)^t C^t_{Ri-1}Ui^{Ri-1-t}x^t x^{n-Ri}$$ $$= \sum_{t=0}^{Ri-1}(-1)^t C^t_{Ri-1}Ui^{Ri-1-t}\sum_{x=1}^{Ui}x^{n-Ri+t}$$ 那么这个东西就可求了。求出 $\sum_{x=1}^{Ui}x^{n-Ri+t}$就可以了。 怎么就可求了呢？ 9.考虑$1^2+2^2+3^2+4^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$的证明方法。其中一种证明法为： 设$Tn=(n+1)^3-n^3$,有 $$Tn=(n+1)^3-n^3=3n^2+3n+1$$ 然后显然的是 $$\sum_{i=1}^n Ti=(n+1)^3-n^3+n^3-(n-1)^3+...-1^3$$ $$=(n+1)^3-1$$ 根据上面还有 $$\sum_{i=1}^n Ti=3 \sum_{i=1}^n i^2+3\sum_{i=1}^ni+\sum_{i=1}^n1$$ 10.所以对于 $1^t+2^t+3^t+...+n^t$ 可以用类似方法求。把这个数列记为 $X_t^n$，则有 $$(n+1)^{t+1}-1=\sum_{i=0}^t C_{t+1}^{t-i+1} X_i^n$$ $$X_t^n=(n+1)^{t+1}-1-\sum_{i=0}^{t-1} C_{t+1}^{t-i+1}X_i^n$$ $$X_0^n=n$$ 可以在$O(t^2)$时间内得到 $X$。 11.认真考虑一下，好像没有别的了。当然乘一起。 $$ans=C^k_{n-1}T\prod_{i=1}^m Si$$ $$=C^k_{n-1}(\sum_{i=0}^{num}(-1)^{num-i}C_{num}^i \prod_{k=1}^{m} {C^{R_k-1}_{i}})\prod_{i=1}^m \sum_{t=0}^{Ri-1}(-1)^t C^t_{Ri-1}Ui^{Ri-1-t}X_{n-Ri+t}^{Ui}$$ 复杂度$O(mn^2)$，主要在于处理 $X$ 。 ```cpp #include <bits/stdc++.h> #define rap(i,s,n) for(int i=s;i<=n;i++) #define drap(i,s,n) for(int i=s;i>=n;i--) #define N 233 #define ll long long #define P 1000000007 #define m(s,k) memset(s,k,sizeof s) using namespace std; char xB[1<<15],*xS=xB,*xTT=xB; #define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++) #define isd(c) ((c>='0'&&c<='9')||(c=='-')) template<typename T> inline bool rd(T& xa){ char xchh; T f=1; while(xchh=getc(),(!isd(xchh))&&(xchh!=0)); if(xchh==0) return 0; if(xchh=='-') xchh=getc(),f=-1; xa=xchh-'0'; while(xchh=getc(),isd(xchh)) xa=xa*10+xchh-'0'; xa*=f; return 1; } ll mpow(ll a,ll k,ll p){ll res=1; while(k){if(k&1) res=res*a%p; k>>=1; a=a*a%p;} return res%p;} int n,m,nm,num,k,R[N]; ll U[N],C[N][N],X[N][N],inv[N]; int main(){ rd(n),rd(m),rd(k); rap(i,1,m) rd(U[i]); rap(i,1,m) rd(R[i]); num=n-k-1,nm=max(n,m); C[0][0]=1; rap(i,1,nm+10){C[i][0]=1; rap(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;} inv[1]=1; rap(i,2,n+10) inv[i]=inv[P%i]*(P-P/i)%P; ll T=0,f=-1; drap(i,num,0){f=-f; ll Ti=1; rap(k,1,m) Ti=(Ti*C[i][R[k]-1])%P; T=(T+Ti*f*C[num][i]+P)%P;} rap(k,1,m) rap(t,0,n){ ll s=0; rap(i,0,t-1) s=(s+C[t+1][t-i+1]*X[k][i])%P; X[k][t]=(mpow(U[k]+1,t+1,P)-1-s+P)%P*inv[t+1]%P; } ll S=1; rap(i,1,m){ ll si=0,f=-1; rap(t,0,R[i]-1) f=-f,si=(si+f*C[R[i]-1][t]*mpow(U[i],R[i]-1-t,P)%P*X[i][n-R[i]+t]%P+P)%P; S=(S*si+P)%P; } printf("%lld\n",C[n-1][k]*T%P*S%P); return 0; } ```