Gate Of Babylon BZOJ 1272

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define N 50010 8 #define ll long long 9 struct Node{10 int l,r,f,F;11 }b[N];12 int a[N],c[N],i,j,n,l,r,s,m;13 ll S[2],Ans[N][2],g;14 inline bool Cmp(Node a,Node b){15 return a.f<b.f||(a.f==b.f&&a.r<b.r);16 }17 inline void Up(int x){18 S[0]+=c[x]++;S[1]++;19 }20 inline void Down(int x){21 S[0]-=--c[x];S[1]--;22 }23 inline void Work(int x){24 Ans[x][0]=S[0];Ans[x][1]=S[1]*(S[1]-1)>>1;25 }26 inline ll Gcd(ll x,ll y){return !y?x:Gcd(y,x%y);}27 int main()28 {29 scanf("%d%d",&n,&m);30 s=sqrt((double)n);31 for(i=1;i<=n;i++)scanf("%d",&a[i]);32 for(i=1;i<=m;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].f=(b[i].l-1)/s+1,b[i].F=i;33 sort(b+1,b+m+1,Cmp);34 for(i=l=1,r=0;i<=m;i++){35 while(b[i].l<l)Up(a[--l]);36 while(b[i].r>r)Up(a[++r]);37 while(b[i].l>l)Down(a[l++]);38 while(b[i].r<r)Down(a[r--]);39 Work(b[i].F);40 }41 for(i=1;i<=m;i++)42 if(!Ans[i][0])printf("0/1\n");else{43 g=Gcd(Ans[i][0],Ans[i][1]);44 printf("%lld/%lld\n",Ans[i][0]/g,Ans[i][1]/g);45 }46 return 0;47 }

题解:

bzoj2038

Lucas定理:C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

图片 1图片 2

2 1 10 13

 

【输入格式】

代码:

图片 3

莫队模板题。转移时O(1)维护一下总方案数与相同颜色方案数就可以了。

【数据范围】

考虑直接Dfs

那么再减去有三种超过限制的方案数

 1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 long long n, m, t, p; 9 inline int Get()10 {11 int x = 0;12 char c = getchar();13 while('0' > c || c > '9') c = getchar();14 while('0' <= c && c <= '9')15 {16 x = (x << 3) + (x << 1) + c - '0';17 c = getchar();18 }19 return x;20 }21 inline long long Pow(long long m, long long n)22 {23 long long res = 1;24 long long sum = m;25 while(n)26 {27 if(n & 1) res = (res * sum) % p;28 sum = (sum % p * sum % p) % p;29 n >>= 1;30 }31 return res;32 }33 long long ans;34 long long c[100233];35 long long su[100233];36 inline long long Zhs(long long a, long long b)37 {38 if(a < b) return 0;39 return ((su[a] % p) * Pow((su[b] % p) * (su[a - b] % p) % p, p - 2)) % p;40 }41 inline long long Lu(long long a, long long b)42 {43 if(a < b) return 0;44 long long res = 1;45 while(a && b)46 {47 res = (res * Zhs(a % p, b % p)) % p;48 a /= p;49 b /= p;50 }51 return res;52 }53 void Dfs(int x, long long o, long long w)54 {55 if(x == t + 1)56 {57 ans = ((ans + o * (Lu(m + n - w, m - w) % p)) % p + p) % p;58 return;59 }60 Dfs(x + 1, o, w);61 Dfs(x + 1, -o, w + c[x] + 1);62 }63 int main()64 {65 n = Get(), t = Get(), m = Get(), p = Get();66 for(int i = 1; i <= t; ++i) c[i] = Get();67 su[0] = 1;68 for(int i = 1; i <= p; ++i) su[i] = (su[i - 1] * i) % p;69 Dfs(1, 1, 0);70 printf("%lld", ans);71 }

解释一下:

 

我们先算出所有的方案数,减去每一种超级神器超过限制的方案

有两个超过限制的方案数中有三种同时超过限制的方案数

那么加上有两个超过限制的方案数

【样例说明】

【输出格式】

 图片 4

图片 5

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。