UVA 10458 - Cricket Ranking

题目链接

题意：给定k个区间，要求用这些数字范围去组合成n，问有几种组合方式

思路：容斥原理，容斥是这样做：已知n个组成s，不限值个数的话，用隔板法求出情况为C(s + n - 1, n - 1)，但是这部分包含了超过了，那么就利用二进制枚举出哪些是超过的，实现把s减去f(i) + 1这样就保证这个位置是超过的，减去这部分后，有多减的在加回来，这就满足了容斥原理的公式，个数为奇数的时候减去，偶数的时候加回

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; typedef long long ll; const int MAXN = 1005; struct bign { int len; ll num[MAXN]; bign () { len = 0; memset(num, 0, sizeof(num)); } bign (ll number) {*this = number;} bign (const char* number) {*this = number;} void DelZero (); void Put (); void operator = (ll number); void operator = (char* number); bool operator < (const bign& b) const; bool operator > (const bign& b) const { return b < *this; } bool operator <= (const bign& b) const { return !(b < *this); } bool operator >= (const bign& b) const { return !(*this < b); } bool operator != (const bign& b) const { return b < *this || *this < b;} bool operator == (const bign& b) const { return !(b != *this); } void operator ++ (); void operator -- (); bign operator + (const int& b); bign operator + (const bign& b); bign operator - (const int& b); bign operator - (const bign& b); bign operator * (const ll& b); bign operator * (const bign& b); bign operator / (const ll& b); //bign operator / (const bign& b); int operator % (const int& b); }; /*Code*/ int k; long long n, f[10]; int bitcount(int x) { return x == 0 ? 0 : bitcount(x>>1) + (x&1); } bign C(long long n, long long m) { bign ans = 1; for (long long i = 0; i < m; i++) ans = ans * (n - i) / (i + 1); return ans; } int main() { while (~scanf("%d%lld", &k, &n)) { long long l, r; for (int i = 0; i < k; i++) { scanf("%lld%lld", &l, &r); f[i] = r - l; n -= l; } bign ans1 = 0LL, ans2 = 0LL; for (int i = 0; i < (1<
     
      = 0; i--) printf("%lld", num[i]); } void bign::operator = (char* number) { len = strlen (number); for (int i = 0; i < len; i++) num[i] = number[len-i-1] - '0'; DelZero (); } void bign::operator = (ll number) { len = 0; while (number) { num[len++] = number%10; number /= 10; } DelZero (); } bool bign::operator < (const bign& b) const { if (len != b.len) return len < b.len; for (int i = len-1; i >= 0; i--) if (num[i] != b.num[i]) return num[i] < b.num[i]; return false; } void bign::operator ++ () { int s = 1; for (int i = 0; i < len; i++) { s = s + num[i]; num[i] = s % 10; s /= 10; if (!s) break; } while (s) { num[len++] = s%10; s /= 10; } } void bign::operator -- () { if (num[0] == 0 && len == 1) return; int s = -1; for (int i = 0; i < len; i++) { s = s + num[i]; num[i] = (s + 10) % 10; if (s >= 0) break; } DelZero (); } bign bign::operator + (const int& b) { bign a = b; return *this + a; } bign bign::operator + (const bign& b) { int bignSum = 0; bign ans; for (int i = 0; i < len || i < b.len; i++) { if (i < len) bignSum += num[i]; if (i < b.len) bignSum += b.num[i]; ans.num[ans.len++] = bignSum % 10; bignSum /= 10; } while (bignSum) { ans.num[ans.len++] = bignSum % 10; bignSum /= 10; } return ans; } bign bign::operator - (const int& b) { bign a = b; return *this - a; } bign bign::operator - (const bign& b) { ll bignSub = 0; bign ans; for (int i = 0; i < len || i < b.len; i++) { bignSub += num[i]; if (i < b.len) bignSub -= b.num[i]; ans.num[ans.len++] = (bignSub + 10) % 10; if (bignSub < 0) bignSub = -1; else bignSub = 0; } ans.DelZero(); return ans; } bign bign::operator * (const ll& b) { ll bignSum = 0; bign ans; ans.len = len; for (int i = 0; i < len; i++) { bignSum += num[i] * b; ans.num[i] = bignSum % 10; bignSum /= 10; } while (bignSum) { ans.num[ans.len++] = bignSum % 10; bignSum /= 10; } return ans; } bign bign::operator * (const bign& b) { bign ans; ans.len = 0; for (int i = 0; i < len; i++){ int bignSum = 0; for (int j = 0; j < b.len; j++){ bignSum += num[i] * b.num[j] + ans.num[i+j]; ans.num[i+j] = bignSum % 10; bignSum /= 10; } ans.len = i + b.len; while (bignSum){ ans.num[ans.len++] = bignSum % 10; bignSum /= 10; } } return ans; } bign bign::operator / (const ll& b) { bign ans; ll s = 0; for (int i = len-1; i >= 0; i--) { s = s * 10 + num[i]; ans.num[i] = s/b; s %= b; } ans.len = len; ans.DelZero(); return ans; } int bign::operator % (const int& b) { bign ans; int s = 0; for (int i = len-1; i >= 0; i--) { s = s * 10 + num[i]; ans.num[i] = s/b; s %= b; } return s; }