bjoi 2008 Gate Of Babylon 容斥原理

、
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 #define MAXN 20
 7 int n,T,m,p;
 8 int a[20];
 9 int factorial[100001],rev[100001];
10 void init()
11 {
12     int i;
13     factorial[0]=1;
14     for(i=1;i<p;i++)
15         factorial[i]=(long long)factorial[i-1]*i%p;
16     rev[1]=1;
17     for(i=2;i<p;i++)
18         rev[i]=((-(p/i)*(long long)rev[p%i])%p+p)%p;
19 }
20 int calc_p(int x)
21 {
22     int ret=0;
23     while(x)
24     {
25         ret+=x/p; x/=p;
26     }
27     return ret;
28 }
29 int my_pow(int x,int n)
30 {
31     int ans=1;
32     while(n)
33     {
34         if(n&1) ans=(long long)ans*x%p;
35         x=(long long)x*x%p;
36         n>>=1;
37     }
38     return ans;
39 }
40 int calc(int x)
41 {
42     int ans=1,ret=0;
43     while(x)
44     {
45         ret+=x/p; ans=(long long)ans*factorial[x%p]%p;
46         x/=p;
47     }
48     ans=(long long)my_pow(factorial[p-1],ret)*ans%p;
49     return ans;
50 }
51 
52 int combination(int n,int m)
53 {
54     if(n<m) return 0;
55     if(calc_p(n)!=calc_p(m)+calc_p(n-m))
56         return 0;
57     int s1=calc(n),s2=(long long)calc(m)*calc(n-m)%p;
58     return (long long)s1*rev[s2]%p;
59 }
60 int solve()
61 {
62     int ans=0;
63     m=m+n+1;
64     n++;
65     int top=(1<<T),i,j,cc,x;
66     for(i=0;i<top;i++)
67     {
68         cc=0;
69         x=m;
70         for(j=0;j<T;j++)
71         if(i&(1<<j)) 
72         {
73             cc++;
74             x-=a[j];
75         }
76         if(cc%2==0) ans+=combination(x-1,n-1);
77         else ans-=combination(x-1,n-1);
78         ans=(ans%p+p)%p;
79     }
80     return ans;
81 }
82 
83 int main()
84 {
85     scanf("%d%d%d%d",&n,&T,&m,&p);
86     init();
87     int i;
88     for(i=0;i<T;i++) scanf("%d",a+i), a[i]++;
89     printf("%d\n",solve());
90     return 0;
91     
92 }
思路：T很小容斥原理