SGU 476 Coach's Trouble(高精度，dfs，容斥)

红太狼 2022-06-05 00:41 126阅读 0赞

#### 476. Coach's Trouble ####

Time limit per test: 0.5 second(s)   
Memory limit: 65536 kilobytes

input: standard   
output: standard

Berland is a modern country, and one could hardly find a man, who would believe evil spirits. Everybody knows that celebrating Halloween is just tribute to old tradition. However, a coach of Berland University student programming teams wants to divide students (3N in total) into teams of three to have as many demonic teams as possible at the moment of future Halloween contest. But he knows for some triples of students that they can't make a demonic team, as they haven't performed well in action in previous contests. He has a list of these  K  forbidden triples. The coach supposes that any three students can make a demonic team unless they do not form a triple contained in the list. And now he wants to know the number of such partitions that all teams are demonic.

**Input**

The first line of the input contains two integers  N  and  K , separated by one space (1 ≤  N  ≤ 1000, 0 ≤  K  ≤ 20). Next  K  lines contain three integers each  a   *i* ,  b   *i* ,  c   *i* (1 ≤  i  ≤  K , 1 ≤  a   *i* ,  b   *i* ,  c   *i*  ≤ 3N). All triples are unique, that is they all are diffent as sets, and  a   *i*  ≠q  b   *i* ,  a   *i*  ≠q  c   *i* ,  b   *i*  ≠q  c   *i* .

**Output**

The output should contain the only number without leading zeroes — the answer to the task.

**Example(s)**

<table style="color:rgb(0,0,0); font-family:Merriweather,serif; font-size:18px; border-collapse:collapse; border:1px solid black"> 
 <tbody> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample input</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample output</pre> </td> 
  </tr> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">2 0
</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">10</pre> </td> 
  </tr> 
 </tbody> 
</table>

<table style="color:rgb(0,0,0); font-family:Merriweather,serif; font-size:18px; border-collapse:collapse; border:1px solid black"> 
 <tbody> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample input</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">sample output</pre> </td> 
  </tr> 
  <tr> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">2 3
1 2 3
4 5 6
1 4 5
</pre> </td> 
   <td style="border-collapse:collapse; border:1px solid black"> <pre style="white-space:pre-wrap; word-wrap:break-word">8</pre> 
    <div> 
     <br> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

题意：

给你3N个学生，要把他们分成N支三人队伍，然后有K种限制情况，告诉你哪三个人不能在一起，问你有多少种组合方法。

思路：  
先通过组合数公式推出3N个人在没有限制情况下分成N组的方法数的递推式s\[i\]=(i\*3-1)\*(i\*3-2)/2\*s\[i-1\]，递推求出没有限制条件时的答案，然后我们用dfs对限制情况进行容斥，选择的话就把这个集合的所有元素打上标记，不选就不打，如果在dfs时遇到已经打过标记的元素就可以直接跳过，没有这个剪枝就会T，然后统计选择的集合数的个数各出现了多少次，奇减偶加，加减的值就是该值出现的次数乘上该值对剩余情况的影响值也就是s\[N-i\]，最后就是答案了，数值很大要使用高精度。

AC代码：

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1005;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b){LL res = 1;for (int i = 1; i <= b; i++)res *= a;return res;}
    
    struct team
    {
    	int a[3];
    };
    
    int num[25],vis[3005],N,K;
    team t[25];
    string s[1005],ans;
    
    const int L = 7000;
    string add(string a, string b)//只限两个非负整数相加    
    {
    	string ans;
    	int na[L] = { 0 }, nb[L] = { 0 };
    	int la = a.size(), lb = b.size();
    	for (int i = 0; i<la; i++) na[la - 1 - i] = a[i] - '0';
    	for (int i = 0; i<lb; i++) nb[lb - 1 - i] = b[i] - '0';
    	int lmax = la>lb ? la : lb;
    	for (int i = 0; i<lmax; i++) na[i] += nb[i], na[i + 1] += na[i] / 10, na[i] %= 10;
    	if (na[lmax]) lmax++;
    	for (int i = lmax - 1; i >= 0; i--) ans += na[i] + '0';
    	return ans;
    }
    string sub(string a, string b)//只限大的非负整数减小的非负整数    
    {
    	string ans;
    	int na[L] = { 0 }, nb[L] = { 0 };
    	int la = a.size(), lb = b.size();
    	for (int i = 0; i<la; i++) na[la - 1 - i] = a[i] - '0';
    	for (int i = 0; i<lb; i++) nb[lb - 1 - i] = b[i] - '0';
    	int lmax = la>lb ? la : lb;
    	for (int i = 0; i<lmax; i++)
    	{
    		na[i] -= nb[i];
    		if (na[i]<0) na[i] += 10, na[i + 1]--;
    	}
    	while (!na[--lmax] && lmax>0); lmax++;
    	for (int i = lmax - 1; i >= 0; i--) ans += na[i] + '0';
    	return ans;
    }
    string mul(string a, string b)//高精度乘法a,b,均为非负整数    
    {
    	string s;
    	int na[L], nb[L], nc[L], La = a.size(), Lb = b.size();//na存储被乘数，nb存储乘数，nc存储积    
    	fill(na, na + L, 0); fill(nb, nb + L, 0); fill(nc, nc + L, 0);//将na,nb,nc都置为0    
    	for (int i = La - 1; i >= 0; i--) na[La - i] = a[i] - '0';//将字符串表示的大整形数转成i整形数组表示的大整形数    
    	for (int i = Lb - 1; i >= 0; i--) nb[Lb - i] = b[i] - '0';
    	for (int i = 1; i <= La; i++)
    		for (int j = 1; j <= Lb; j++)
    			nc[i + j - 1] += na[i] * nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）    
    	for (int i = 1; i <= La + Lb; i++)
    		nc[i + 1] += nc[i] / 10, nc[i] %= 10;//统一处理进位    
    	if (nc[La + Lb]) s += nc[La + Lb] + '0';//判断第i+j位上的数字是不是0    
    	for (int i = La + Lb - 1; i >= 1; i--)
    		s += nc[i] + '0';//将整形数组转成字符串    
    	return s;
    }
    
    string trans(int x)//将int转化为string
    {
    	int k;
    	string a;
    	while (x)
    	{
    		k = x % 10;
    		a += ('0' + k);
    		x /= 10;
    	}
    	reverse(a.begin(), a.end());
    	return a;
    }
    
    void init()//初始化
    {
    	int k;
    	s[0] = "1";
    	for (int i = 1; i <= 1000; i++)
    	{
    		k = (i * 3 - 1)*(i * 3 - 2) / 2;
    		s[i] = mul(s[i - 1], trans(k));
    	}
    }
    
    void dfs(int cur, int total, int limit)
    {
    	num[total]++;
    	for (int i = cur; i <= limit; ++i)
    	{
    		int flag = 0;
    		if (vis[t[i].a[0]] == 0 && vis[t[i].a[1]] == 0 && vis[t[i].a[2]] == 0)//如果有选过的了可以直接跳过
    			flag = 1;
    		if (flag == 0)
    			continue;
    		for (int j = 0; j < 3; ++j)
    			vis[t[i].a[j]] = 1;//选过的元素标记为1
    		dfs(i + 1, total + 1, limit);
    		for (int j = 0; j < 3; ++j)
    			vis[t[i].a[j]] = 0;
    	}
    }
    
    int main()
    {
    	init();
    	while (scanf("%d%d", &N, &K) != EOF)
    	{
    		memset(vis, 0, sizeof vis);
    		memset(num, 0, sizeof num);
    		ans = add("1000", s[N]);//加上1000防止减出负数
    		for (int i = 1; i <= K; i++)
    			scanf("%d%d%d", &t[i].a[0], &t[i].a[1], &t[i].a[2]);
    		dfs(1, 0, K);
    		for (int i = 1; i <= min(N, K); i++)
    		{
    			if (i % 2 == 0)//奇减偶加
    				ans = add(ans, mul(s[N - i], trans(num[i])));
    			else
    				ans = sub(ans, mul(s[N - i], trans(num[i])));
    		}
    		ans = sub(ans, "1000");
    		cout << ans << endl;
    	}
    }