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];
}
更多推荐
SRM 613
发布评论