首页 > 代码库 > Sets 比赛时想错方向了。。。。 （大数不能处理负数啊）
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
2 03 22 1 22 1 310 0
Sample Output
22115975
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 else144 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 else159 {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 else178 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 else209 {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 else283 return false;284 }285 else286 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("\n");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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。