Topcoder SRM 711 問題と解説

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16880

問題

Div1 Easy. ConsecutiveOnes

整数N,Kがあり、以下の性質を満たす最小のmを答えよ。
1. N ≦ m
2. mを２進数にすると少なくともK個連続した1がある

Div1 Med. OrderedProduct

素数を昇順で格納した配列Pがある。P[0]=2,P[1]=3,...
個数Nの配列Aが与えられる。
X = P[0]^A[0] * P[1]^A[1] * ... * P[N-1]^A[N-1]とする。
Xを因数分解して列とするときの組合せは何通りか(mod10^9+7)
例）X=12なら(2,6),(3,4),(4,3),(6,2)の4通り

以下、解説

解説

Div1 Easy. ConsecutiveOnes

桁数を見て、桁数がKを下回っていれば全部1の数を出力。
K個連続して1となる区間を全探索して、その中で最小の数を出力すれば良い。
連続して1となるように1を置くとそれよりも小さい桁は0にしても問題ない場合がある。
そのため、元々の数に対して、「K連続して1とした数」と「1の区間より小さい桁は0にした数」のそれぞれを考えて最小を取る。

typedef long long ll;
struct ConsecutiveOnes {
	ll get(ll n, int k) {
		int D[60];
		rep(i, 0, 60) D[i] = 0;

		int d = 0; ll m = n;
		while (0 < m) D[d] = m % 2, m /= 2, d++;

		if (d < k) {
			ll ans = 0;
			rep(i, 0, k) ans = ans * 2 + 1;
			return ans;
		}

		ll ans = 1LL << 60;
		rep(i, 0, d - k + 1) {
			int DD[60];
			rep(j, 0, 60) DD[j] = D[j];
			rep(j, 0, k) DD[i + j] = 1;
			ll a = 0;
			rep(j, 0, 60) a = a * 2 + DD[59 - j];
			if (n <= a) ans = min(ans, a);

			rep(j, 0, i) DD[j] = 0;
			a = 0;
			rep(j, 0, 60) a = a * 2 + DD[59 - j];
			if(n <= a) ans = min(ans, a);
		}
		return ans;
	}
};

Div1 Med. OrderedProduct

http://kmjp.hatenablog.jp/entry/2017/03/26/0930
kmjpさんの最強解説を読んだ
dp[i] := i個の数列の組合せ
各数についてi個の数列に分けるように重複組合せを考える。
これを考えるとi個の数列について列挙しているはずが、1個の数列,2個の数列,3個の数列,...,i-1個の数列も数え上げてしまっているので、それを引く。
あとはdp[1]～dp[sm]の総和が答え。

int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) {
	int ret = 1;
	while (b > 0) {
		if (b & 1) ret = 1LL * ret * a % mod;
		a = 1LL * a * a % mod; b >>= 1;
	}
	return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
int fac[201010], ifac[201010];
void initfac() {
	fac[0] = ifac[0] = 1;
	rep(i, 1, 201010) fac[i] = 1LL * i * fac[i - 1] % mod;
	rep(i, 1, 201010) ifac[i] = modinv(fac[i]);
}
int aCb(int a, int b) {
	if (b < 0 || a < b) return 0;
	return (1LL * fac[a] * ifac[a - b] % mod) * ifac[b] % mod;
}
int aHb(int a, int b) { return aCb(a + b - 1, b); }
//-----------------------------------------------------------------------------------
int dp[101010];
struct OrderedProduct {
	int count(vector <int> a) {
		initfac();

		int sm = 0;
		int n = a.size();
		rep(i, 0, n) sm += a[i];

		int ans = 0;
		rep(i, 1, sm + 1) {
			dp[i] = 1;
			for (int b : a) dp[i] = mul(dp[i], aHb(i, b));
			rep(j, 1, i) dp[i] = sub(dp[i], mul(dp[j], aCb(i, j)));
			ans = add(ans, dp[i]);
		}
		return ans;
	}
};