题目： https://ac.nowcoder.com/acm/problem/15550
A [ 0 ] [ 0 ] = p A[0][0]=p A[0][0]=p，且 A [ i ] [ j ] = { A [ i ] [ j − 1 ] i = 0 , 0 < j < m max 0 ≤ k ≤ j { A [ i − 1 ] [ k ] + ∑ l = k + 1 j A [ i − 1 ] [ l ] j − k } 1 ≤ i , 0 ≤ j < m A[i][j]=\begin{cases} A[i][j-1]\quad i=0,0<j<m\\ \max\limits_{0\le k\le j}\{A[i-1][k]+\sum_{l=k+1}^{j}\frac{A[i-1][l]}{j-k}\}\quad 1\le i,0\le j<m \end{cases} A[i][j]=⎩⎨⎧A[i][j−1]i=0,0<j<m0≤k≤jmax{A[i−1][k]+∑l=k+1jj−kA[i−1][l]}1≤i,0≤j<m 求 A [ x ] [ y ] A[x][y] A[x][y]
思路： 手算一下发现就是 A A A数组的第 0 0 0行和第 0 0 0列都是 p p p，然后 A [ i ] [ j ] = A [ i − 1 ] [ j ] + A [ i − 1 ] [ j − 1 ] 1 ≤ i , j < m A[i][j]=A[i-1][j]+A[i-1][j-1]\quad 1\le i,j<m A[i][j]=A[i−1][j]+A[i−1][j−1]1≤i,j<m 用组合数学算一下第 0 0 0行和第 0 0 0列的数的贡献即可。
#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std; const int N=1000009; int T; ll p[N],p1[N],m,x,y,P; ll qpow(ll a, ll b) { ll res=1; a%=mod; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll cal(ll a,ll b) { if(a<0||b<0||a-b<0) return 0; return p[a]*p1[b]%mod*p1[a-b]%mod; } int main() { p[0]=1; for(int i=1; i<N; i++) p[i]=p[i-1]*i%mod; p1[N-1]=qpow(p[N-1],mod-2); for(int i=N-2; i>=0; i--) p1[i]=p1[i+1]*(i+1)%mod; while(scanf("%lld%lld%lld%lld",&m,&x,&y,&P)==4) { ll ans=0; x--; if(!x||!y) { cout<<P<<endl; continue; } ans+=cal(x,y); for(int i=1; i<=y; i++) ans=(ans+cal(x,y-i))%mod; cout<<ans*P%mod<<endl; } return 0; }