Sets 比赛时想错方向了。。。。（大数不能处理负数啊）

Sets

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

SubmitStatus

Problem Description

给出N个数，现在需要将这些数分成若干个不相交的集合，同时给出M个限制集合，使得划分成的集合中，不能有任何一个集合包含给出的M个集合中的任意一个。求有多少种合法的集合划分方案

Input

多组数据，每组数据：

第一行N,M(1 <= N <= 100,0 <= M <= 10)

接下来M行，每行开始一个数TOT，表示这个禁止集合中的元素个数，接下来有TOT个数。(1 <= TOT <= N,且TOT个数都是1-N之间的正整数）

Output

每组数据，输出一行，你的答案

Sample Input

Sample Output

2
2
115975

Hint

第二个样例：

3个数的划分方案是 :

{1} {2} {3}

{1,2} {3}

{1,3} {2}

{1} {2,3}

{1,2,3}

因为划分方案中任意一组合法划分不能有一个集合包含 {1,2}或 {1,3}作为子集，所以"{1,2} {3}"，"{1,3} {2}"， "{1,2,3}"这3种划分方案不合法，合法方案为2

  1 #include <iostream>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <math.h>
  5 #include <stdio.h>
  6 using namespace std;
  7 
  8 #define MAXN 9999
  9 #define MAXSIZE 10
 10 #define DLEN 4
 11 
 12 class BigNum
 13 {
 14 private:
 15     int a[500];    //可以控制大数的位数
 16     int len;       //大数长度
 17 public:
 18     BigNum()
 19     {
 20         len = 1;    //构造函数
 21         memset(a,0,sizeof(a));
 22     }
 23     BigNum(const int);       //将一个int类型的变量转化为大数
 24     BigNum(const char*);     //将一个字符串类型的变量转化为大数
 25     BigNum(const BigNum &);  //拷贝构造函数
 26     BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算
 27 
 28     friend istream& operator>>(istream&,  BigNum&);   //重载输入运算符
 29     friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符
 30 
 31     BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
 32     BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算
 33     BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算
 34     BigNum operator/(const int   &) const;    //重载除法运算符，大数对一个整数进行相除运算
 35 
 36     BigNum operator^(const int  &) const;    //大数的n次方运算
 37     int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算
 38     bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较
 39     bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较
 40 
 41     void print();       //输出大数
 42 };
 43 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
 44 {
 45     int c,d = b;
 46     len = 0;
 47     memset(a,0,sizeof(a));
 48     while(d > MAXN)
 49     {
 50         c = d - (d / (MAXN + 1)) * (MAXN + 1);
 51         d = d / (MAXN + 1);
 52         a[len++] = c;
 53     }
 54     a[len++] = d;
 55 }
 56 BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
 57 {
 58     int t,k,index,l,i;
 59     memset(a,0,sizeof(a));
 60     l=strlen(s);
 61     len=l/DLEN;
 62     if(l%DLEN)
 63         len++;
 64     index=0;
 65     for(i=l-1; i>=0; i-=DLEN)
 66     {
 67         t=0;
 68         k=i-DLEN+1;
 69         if(k<0)
 70             k=0;
 71         for(int j=k; j<=i; j++)
 72             t=t*10+s[j]-'0';
 73         a[index++]=t;
 74     }
 75 }
 76 BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
 77 {
 78     int i;
 79     memset(a,0,sizeof(a));
 80     for(i = 0 ; i < len ; i++)
 81         a[i] = T.a[i];
 82 }
 83 BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
 84 {
 85     int i;
 86     len = n.len;
 87     memset(a,0,sizeof(a));
 88     for(i = 0 ; i < len ; i++)
 89         a[i] = n.a[i];
 90     return *this;
 91 }
 92 istream& operator>>(istream & in,  BigNum & b)   //重载输入运算符
 93 {
 94     char ch[MAXSIZE*4];
 95     int i = -1;
 96     in>>ch;
 97     int l=strlen(ch);
 98     int count=0,sum=0;
 99     for(i=l-1; i>=0;)
100     {
101         sum = 0;
102         int t=1;
103         for(int j=0; j<4&&i>=0; j++,i--,t*=10)
104         {
105             sum+=(ch[i]-'0')*t;
106         }
107         b.a[count]=sum;
108         count++;
109     }
110     b.len =count++;
111     return in;
112 
113 }
114 ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符
115 {
116     int i;
117     cout << b.a[b.len - 1];
118     for(i = b.len - 2 ; i >= 0 ; i--)
119     {
120         cout.width(DLEN);
121         cout.fill('0');
122         cout << b.a[i];
123     }
124     return out;
125 }
126 
127 BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
128 {
129     BigNum t(*this);
130     int i,big;      //位数
131     big = T.len > len ? T.len : len;
132     for(i = 0 ; i < big ; i++)
133     {
134         t.a[i] +=T.a[i];
135         if(t.a[i] > MAXN)
136         {
137             t.a[i + 1]++;
138             t.a[i] -=MAXN+1;
139         }
140     }
141     if(t.a[big] != 0)
142         t.len = big + 1;
143     else
144         t.len = big;
145     return t;
146 }
147 BigNum BigNum::operator-(const BigNum & T) const   //两个大数之间的相减运算
148 {
149     int i,j,big;
150     bool flag;
151     BigNum t1,t2;
152     if(*this>T)
153     {
154         t1=*this;
155         t2=T;
156         flag=0;
157     }
158     else
159     {
160         t1=T;
161         t2=*this;
162         flag=1;
163     }
164     big=t1.len;
165     for(i = 0 ; i < big ; i++)
166     {
167         if(t1.a[i] < t2.a[i])
168         {
169             j = i + 1;
170             while(t1.a[j] == 0)
171                 j++;
172             t1.a[j--]--;
173             while(j > i)
174                 t1.a[j--] += MAXN;
175             t1.a[i] += MAXN + 1 - t2.a[i];
176         }
177         else
178             t1.a[i] -= t2.a[i];
179     }
180     t1.len = big;
181     while(t1.a[len - 1] == 0 && t1.len > 1)
182     {
183         t1.len--;
184         big--;
185     }
186     if(flag)
187         t1.a[big-1]=0-t1.a[big-1];
188     return t1;
189 }
190 
191 BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算
192 {
193     BigNum ret;
194     int i,j,up;
195     int temp,temp1;
196     for(i = 0 ; i < len ; i++)
197     {
198         up = 0;
199         for(j = 0 ; j < T.len ; j++)
200         {
201             temp = a[i] * T.a[j] + ret.a[i + j] + up;
202             if(temp > MAXN)
203             {
204                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
205                 up = temp / (MAXN + 1);
206                 ret.a[i + j] = temp1;
207             }
208             else
209             {
210                 up = 0;
211                 ret.a[i + j] = temp;
212             }
213         }
214         if(up != 0)
215             ret.a[i + j] = up;
216     }
217     ret.len = i + j;
218     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
219         ret.len--;
220     return ret;
221 }
222 BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
223 {
224     BigNum ret;
225     int i,down = 0;
226     for(i = len - 1 ; i >= 0 ; i--)
227     {
228         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
229         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
230     }
231     ret.len = len;
232     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
233         ret.len--;
234     return ret;
235 }
236 int BigNum::operator %(const int & b) const    //大数对一个int类型的变量进行取模运算
237 {
238     int i,d=0;
239     for (i = len-1; i>=0; i--)
240     {
241         d = ((d * (MAXN+1))% b + a[i])% b;
242     }
243     return d;
244 }
245 BigNum BigNum::operator^(const int & n) const    //大数的n次方运算
246 {
247     BigNum t,ret(1);
248     int i;
249     if(n<0)
250         exit(-1);
251     if(n==0)
252         return 1;
253     if(n==1)
254         return *this;
255     int m=n;
256     while(m>1)
257     {
258         t=*this;
259         for( i=1; i<<1<=m; i<<=1)
260         {
261             t=t*t;
262         }
263         m-=i;
264         ret=ret*t;
265         if(m==1)
266             ret=ret*(*this);
267     }
268     return ret;
269 }
270 bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
271 {
272     int ln;
273     if(len > T.len)
274         return true;
275     else if(len == T.len)
276     {
277         ln = len - 1;
278         while(a[ln] == T.a[ln] && ln >= 0)
279             ln--;
280         if(ln >= 0 && a[ln] > T.a[ln])
281             return true;
282         else
283             return false;
284     }
285     else
286         return false;
287 }
288 bool BigNum::operator >(const int & t) const    //大数和一个int类型的变量的大小比较
289 {
290     BigNum b(t);
291     return *this>b;
292 }
293 
294 void BigNum::print()    //输出大数
295 {
296     int i;
297     cout << a[len - 1];
298     for(i = len - 2 ; i >= 0 ; i--)
299     {
300         cout.width(DLEN);
301         cout.fill('0');
302         cout << a[i];
303     }
304 }
305 BigNum dp[110][110];
306 void init()
307 {
308     int i,j;
309     dp[0][0]=1;
310     for(i=1; i<110; i++)
311     {
312         dp[i][0]=0;
313         for(j=1; j<=i; j++)
314             dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1];
315     }
316     for(i=1; i<110; i++)
317     {
318         for(j=1; j<=i; j++)
319             dp[i][0]=dp[i][0]+dp[i][j];
320     }
321     dp[0][0]=0;
322 }
323 int a[20][110],n,m;
324 int father[200];
325 BigNum ans,ans1;
326 int findfa(int x)
327 {
328     return father[x] == x ? x : father[x] = findfa(father[x]);
329 }
330 void solve(int x)
331 {
332     int i,j,y,z,nm=n;
333     bool bi=0;
334     for(i=1; i<=n; i++)father[i]=i;
335     for(i=0; i<m; i++)
336     {
337         if(x&(1<<i))
338         {
339             bi^=1;
340             if(a[i][0]==0)continue;
341             y=findfa(a[i][1]);
342             for(j=2; j<=a[i][0]; j++)
343             {
344                 z=findfa(a[i][j]);
345                 if(z!=y)
346                     father[z]=y,nm--;
347             }
348         }
349     }
350     if(bi)ans1=ans1+dp[nm][0];
351     else ans=ans+dp[nm][0];
352 }
353 void work()
354 {
355     int i,j,len=(1<<m);
356     ans1=ans=0;
357     for(i=0; i<len; i++)
358     {
359         solve(i);
360     }
361     ans=ans-ans1;
362     ans.print();
363     printf("
");
364 }
365 int main(void)
366 {
367     init();
368     int i,j;
369     while(~scanf("%d%d",&n,&m))
370     {
371         for(i=0; i<m; i++)
372         {
373             scanf("%d",&a[i][0]);
374             for(j=1; j<=a[i][0]; j++)
375                 scanf("%d",&a[i][j]);
376         }
377         work();
378     }
379 }

View Code

Sets 比赛时想错方向了。。。。 （大数不能处理负数啊）