UVALive - 6469（容斥）

题意：Ｎ道题连线，问至少前ｋ道题目错误的可能有几种

思路：那就是所有连线可能的情况数（即ｎ！） 减去前k道题存在正确答案的情况数

根据容斥原理，奇数个集合为正，偶数个集合为负计算即可

代码如下：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll INF = 1e14 + 7;const int N = 1e5 + 10;int n, k;int main(){    int t, cas;    scanf("%d", &t);    while(t--)    {        scanf("%d%d%d", &cas, &n, &k);        ll ans = 1;        for(int i = 1; i <= n; i++) ans *= i;        ll cnt = 0;		for(int i = 1; i <= k; i++)		{			ll tmp = 1;			for(int j = k; j > k - i; j--)			{				tmp *= j;			}			for(int j = i; j > 1; j--)			{				tmp /= j;			}			for(int j = n - i; j >= (n - k + 1); j--) tmp *= j;			if(i % 2 == 0) cnt -= tmp;			else cnt += tmp;		}		for(int i = n - k; i > 1; i--) cnt *= i;		ans -= cnt;		PRintf("%d %lld/n", cas, ans);     }    return 0;}/*41 4 12 7 33 10 54 17 17*/