[转]CodePlus 2018 3月赛博弈论与概率统计

转自 https://blog.csdn.net/KsCla/article/details/79500222
  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstdio>
  6 #include<cstdlib>
  7 #include<stdio.h>
  8 #include<algorithm>
  9 using namespace std;
 10 
 11 const int maxn=250100;
 12 const int NN=250000;
 13 const int M=1000000007;
 14 typedef long long LL;
 15 
 16 struct data
 17 {
 18     int id,N,K;
 19 } ask[maxn];
 20 
 21 LL fac[maxn];
 22 LL nfac[maxn];
 23 
 24 int ans[maxn];
 25 int Div[maxn];
 26 int t,n,m;
 27 int sn=501;
 28 
 29 void Preparation()
 30 {
 31     fac[0]=1;
 32     for (LL i=1; i<=NN; i++) fac[i]=fac[i-1]*i%M;
 33     nfac[0]=nfac[1]=1;
 34     for (LL i=2; i<=NN; i++)
 35     {
 36         LL x=M/i,y=M%i;
 37         nfac[i]=M-x*nfac[y]%M;
 38     }
 39     for (LL i=2; i<=NN; i++) nfac[i]=nfac[i-1]*nfac[i]%M;
 40 }
 41 
 42 int C(int nn,int mm)
 43 {
 44     if (mm>nn) return 0;
 45     LL val=fac[nn];
 46     val=val*nfac[mm]%M;
 47     val=val*nfac[nn-mm]%M;
 48     return val;
 49 }
 50 
 51 bool Comp(data x,data y)
 52 {
 53     int a=x.N/sn;
 54     int b=y.N/sn;
 55     return ( a<b || ( a==b && x.K<y.K ) );
 56 }
 57 
 58 int Mod(int x)
 59 {
 60     if (x>=M) return x-M;
 61     else return x;
 62 }
 63 
 64 int Dec(int x)
 65 {
 66     if (x<0) return x+M;
 67     else return x;
 68 }
 69 
 70 int main()
 71 {
 72     freopen("D.in","r",stdin);
 73     freopen("D.out","w",stdout);
 74 
 75     Preparation();
 76     int p;
 77     scanf("%d%d",&t,&p);
 78     for (int i=1; i<=t; i++)
 79     {
 80         scanf("%d%d",&n,&m);
 81         if (n>=m) ans[i]=(long long)(n-m)*C(n+m,n)%M,ask[i].K=m-1;
 82         else ask[i].K=n-1;
 83         ask[i].N=n+m;
 84         ask[i].id=i;
 85         Div[i]=nfac[n+m];
 86         Div[i]=(long long)Div[i]*fac[n]%M;
 87         Div[i]=(long long)Div[i]*fac[m]%M;
 88     }
 89 
 90     sort(ask+1,ask+t+1,Comp);
 91     ask[0].N=-1e9;
 92     int val=0;
 93     for (int i=1; i<=t; i++)
 94     {
 95         if (ask[i].K==-1) continue;
 96         if ( ask[i-1].K==-1 || ask[i-1].N/sn<ask[i].N/sn )
 97         {
 98             n=ask[i].N;
 99             m=ask[i].K;
100             val=0;
101             for (int i=0; i<=m; i++) val=Mod(val+ C(n,i) );
102         }
103         else
104         {
105             while (n<ask[i].N) val=Dec( Mod(val<<1)-C(n,m) ),++n;
106             while (n>ask[i].N) --n,val=(long long)Mod(val+ C(n,m) )*nfac[2]%M;
107             while (m<ask[i].K) ++m,val=Mod(val+ C(n,m) );
108         }
109         int x=ask[i].id;
110         ans[x]=Mod(ans[x]+val);
111     }
112 
113     for (int i=1; i<=t; i++) ans[i]=(long long)ans[i]*Div[i]%M;
114     for (int i=1; i<=t; i++) printf("%d
",ans[i]);
115     return 0;
116 }
[转]CodePlus 2018 3月赛 博弈论与概率统计

[转]CodePlus 2018 3月赛博弈论与概率统计
