• [转]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 }
  • 相关阅读:
    面试再问HashMap,求你把这篇文章发给他!
    Maven Nexus私库搭建及使用,你还不会吗?
    两年摸爬滚打 Spring Boot,总结了这 16 条最佳实践
    @Controller,@Service,@Repository,@Component你搞懂了吗?
    mysql 输出当前月所有日期与对应的星期
    mysql创建每月执行一次的event
    一个关于explain出来为all的说明及优化
    怎么快速了解自己的MySQL服务器
    Mysql查找所有项目开始时间比之前项目结束时间小的项目ID
    Device eth0 does not seem to be present,delaying initialization解决方法
  • 原文地址:https://www.cnblogs.com/aseer/p/8780564.html
一二三 - 开发者的网上家园