SRM 613

SRM 613"/>

SRM 613

因为博客被奇怪的封掉了两天，于是。。。现在才写

easy：

排序，然后枚举分界位置，分界左边向右走，分界右边向左走

medium：

因为The difference high - low will be less than or equal to 100,000.

所以如果选了两个不同的，gcd肯定小于100000

枚举i=1~100000，算出gcd是i的倍数的方案数（pow(i倍数的个数,k)-i倍数的个数）  剪掉那个是全部选一样的数

然后容斥一下，减掉重复的即可。

然后全部选一样的数再单独讨论一下即可

hard：

首先要注意到的left[i]+right[i]<=M,也就是我们可以吧left和right看成独立的没有关联的

1、left

那么从左向右dp，如果只有left[]，那么dp[i][j]，表示前i列，已经放了但是还没分配的left是j行。

如果i列有r个left结束，那么那么我们之前选的j个都可以给这r个在此处结束的，乘个组合数C(j,r)，j-=r。

2、right

也是从左向右dp，如果只有right[]，那么dp[i][k]，表示前i列，还有k个需要放的

如果第i列有r个right开始，那么k直接加上r。如果再此列放一个right的，那么k--，乘以k表示选择哪一个

因为left，right没有关系，两个dp直接合并一下dp[i][j][k]，注意的一点是，如果当前i列，我们不放left，也不放right，我们可以选择不放，也可以选择放不包含在left和right的中间的空处，即乘以 （空+1）

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>using namespace std;class TaroCheckers {
public:int getNumber(vector<int> , vector<int> , int);
};long long pmod = 1000000007;
long long c[205][205];
int a[205], b[205], kong[205];
long long dp[205][55][55];
long long ba[205];
void pre() {int i, j;for (i = 0; i < 205; ++i) {c[i][0] = c[i][i] = 1;for (j = 1; j < i; ++j) {c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % pmod;}}ba[0] = 1;for (i = 1; i < 205; ++i)ba[i] = ba[i - 1] * i % pmod;
}
int TaroCheckers::getNumber(vector<int> left, vector<int> right, int n) {int i, j, k;int ii, jj, kk;long long cost;int m = left.size();pre();memset(dp, 0, sizeof(dp));dp[0][0][0] = 1;memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for (i = 0; i < m; ++i) {a[left[i] - 1]++;b[n - right[i]]++;}for (i = 0; i < n; ++i) {kong[i] = 0;for (j = 0; j < m; ++j) {if (left[j] - 1 < i && n - right[j] > i)kong[i]++;}}for (i = 0; i < n; ++i) {for (j = 0; j <= m; ++j) {for (k = 0; k <= m; ++k) {if (dp[i][j][k] == 0)continue;//给前面cost = 1;kk = k + b[i];ii = i + 1;jj = j + 1;if (jj >= a[i]) {cost *= c[jj][a[i]] * ba[a[i]] % pmod;cost %= pmod;jj -= a[i];if (jj < 55) {dp[ii][jj][kk] += dp[i][j][k] * cost;dp[ii][jj][kk] %= pmod;}}//给后面cost = 1;kk = k + b[i];ii = i + 1;jj = j;if (jj >= a[i]) {cost *= c[jj][a[i]] * ba[a[i]] % pmod;cost %= pmod;cost *= kk;kk--;jj -= a[i];if (jj < 55) {dp[ii][jj][kk] += dp[i][j][k] * cost;dp[ii][jj][kk] %= pmod;}}//都不给cost = 1;kk = k + b[i];ii = i + 1;jj = j;if (jj >= a[i]) {cost *= c[jj][a[i]] * ba[a[i]] % pmod;cost %= pmod;cost *= kong[i] + 1;cost %= pmod;jj -= a[i];if (jj < 55) {dp[ii][jj][kk] += dp[i][j][k] * cost;dp[ii][jj][kk] %= pmod;}}}}}return dp[n][0][0];
}