在一个n∗mn∗mn∗m的矩阵A的所有位置中随机填入000或111，概率比为x:yx:yx:y。令Bi=∑j=1mAi,jBi=∑_{j=1}^{m}A_{i,j}Bi=∑j=1mAi,j,求minBiminB_{i}minBi的期望，并将期望乘以(x+y)nm(x+y)^{nm}(x+y)nm后对109+710^{9}+7109+7取模
这是一道明显的期望转计数问题
稍有常识的OI选手就知道E=∑i=0mi∗P(min=i)E=\sum_{i=0}^{m}i*P(min = i)E=∑i=0mi∗P(min=i) 在乘上所有情况的时候 答案是：Ans=∑i=0m∗Casei∗iAns=\sum_{i=0}^{m}*Case_{i}*iAns=∑i=0m∗Casei∗i其中Casei=Case_{i}=Casei=答案为i的情况总数 定义：GiG_{i}Gi为表示恰好这一行值为iii的情况数 其恰好为：Gi=Cnj∗yi∗xm−iG_{i}=C_{n}^{j}*y^{i}*x^{m-i}Gi=Cnj∗yi∗xm−i 定义：FiF_{i}Fi为表示这一行至少值为iii的情况数 显而易见，FiF_{i}Fi为GiG_{i}Gi的后缀和 我们考虑算答案的贡献： 还是看原式子：Ans=∑i=0m∗Casei∗iAns=\sum_{i=0}^{m}*Case_{i}*iAns=∑i=0m∗Casei∗iCasei=∑j=1nCnj(Fi+1)n−j(Gi)jCase_{i}=\sum_{j=1}^{n}C_{n}^{j}(F_{i+1})^{n-j}(G_{i})^{j}Casei=∑j=1nCnj(Fi+1)n−j(Gi)j 为什么? 我们枚举当最小答案为iii的时候这个矩阵有多少行答案为iii 那么其他行答案至少为i+1i+1i+1 我们发现好像这是 二项式定理的逆定理 所以转为二项式定理Casei=(Fi+1+Gi)n−Cn0(Fi+1)nCase_{i}=(F_{i+1}+G_{i})^{n}-C_{n}^{0}(F_{i+1})^{n}Casei=(Fi+1+Gi)n−Cn0(Fi+1)n 那么可以线性求出答案：Ans=∑i=0m∗i∗((Fi+1+Gi)n−Cn0(Fi+1)n)Ans=\sum_{i=0}^{m}*i*((F_{i+1}+G_{i})^{n}-C_{n}^{0}(F_{i+1})^{n})Ans=∑i=0m∗i∗((Fi+1+Gi)n−Cn0(Fi+1)n)#include#include #include #include #include using namespace std;const int N=1e6+100;typedef int INT;#define int long longconst int mod=1e9+7;inline int Quick_Pow(int x,int k){ int ret=1; while(k){ if(k&1)ret=ret*x%mod; x=x*x%mod; k/=2; } return ret;}int Fac[N];int Inv[N];int C(int n,int m){ return Fac[n]*Inv[m]%mod*Inv[n-m]%mod;}int n,m,x,y;int G[N];int S[N];signed main(){ Fac[0]=1; for(int i=1;i<=200000;++i)Fac[i]=Fac[i-1]*i%mod; Inv[200000]=Quick_Pow(Fac[200000],mod-2); for(int i=199999;i>=0;--i)Inv[i]=Inv[i+1]*(i+1)%mod; cin>>n>>m>>x>>y; for(int i=0;i<=m;++i){ G[i]=C(m,i)*Quick_Pow(y,i)%mod*Quick_Pow(x,m-i)%mod; } for(int i=m;i>=0;--i)S[i]=(S[i+1]+G[i])%mod; int ans=0; for(int i=1;i<=m;++i){// ans=(ans+Quick_Pow(S[i+1]+G[i],n))%mod; ans=((ans+Quick_Pow(S[i+1]+G[i],n)*i%mod-C(n,0)*Quick_Pow(S[i+1],n)*i%mod)%mod+mod)%mod; } cout<
有趣的是：注释掉的代码也能求出答案233