Codeforces 674F Bears and Juice - DEGwerのブログ

問題概要

n人の人がいる。箱がたくさんあり、そのうち1個があたり。
毎日、各人は箱のうちいくつかを見て、その中に当たりが入っていた場合消える。p人まで消してよい。
i: 1~qについて、日数がi日のときに当たりの箱を特定できるような箱の個数の最大値を求めよ。

解法

特定のk人が見た箱がx個あり、その中に当たりがあるとすると、k人が消えて当たりの箱の個数がx個になる。つまり、これは日数を1日、人数をk人減らし、箱の個数をx個にした状態と同じ。
よってDP[消えた人数][残り日数]: それ以降で特定できる箱の個数の最大値x としてDPができる。

このDPはO(p^2q)で間に合わないが、DPの遷移は残り日数によらず、次の日のDP配列の線形結合なので、同じ行列の累乗の形でかける。

さらにこの行列は上三角(消えた人の人数は減らないため)なので、求める答えはあるp次多項式に1~qを代入した値となる。
この多項式の小さいところでの値は普通にDPをすると求まるので、補間をする。この場合隣同士の差をp回とってやると定数関数になるので、imos法っぽくやるとO(pq)で全部の値が求められる。

全体でO(p^3+pq)となる。ゆっくり書いたらバグらなかったのでOK。DPしようと思うのが難しいと思う。(解説を昔5秒眺めたことがあってDPという情報だけ知っていた)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
pii num2(ll a)
{
	int ret = 0;
	for (;;)
	{
		if (a % 2 != 0)return make_pair(ret, a);
		a /= 2;
		ret++;
	}
}
ll mat[131][131];
ll rev[200];
ll now[131];
ll imos[131][131];
int main()
{
	ll num, gen, query;
	scanf("%I64d%I64d%I64d", &num, &gen, &query);
	gen = min(gen, num - 1);
	for (int i = 1; i < 200; i++)
	{
		if (i % 2 != 0)
		{
			for (ll j = 0;; j++)
			{
				if (((1LL << 32)*j + 1) % i == 0)
				{
					rev[i] = ((1LL << 32)*j + 1) / i;
					break;
				}
			}
		}
	}
	for (int i = 0; i <= gen; i++)
	{
		for (int j = i; j <= gen; j++)
		{
			ll n = num - i;
			ll p = j - i;
			int c = 0;
			ll now = 1;
			for (int k = 1; k <= p; k++)
			{
				pii z1 = num2(n - k + 1);
				pii z2 = num2(k);
				c += z1.first - z2.first;
				now *= z1.second*rev[z2.second] & ((1LL << 32) - 1);
				now &= ((1LL << 32) - 1);
			}
			mat[i][j] = now << (c % 32);
		}
	}
	fill(now, now + 131, 1);
	for (int i = 0; i <= gen; i++)
	{
		int n[131];
		fill(n, n + 131, 0);
		for (int j = 0; j <= gen; j++)
		{
			for (int k = 0; k <= gen; k++)
			{
				n[j] += mat[j][k] * now[k];
				n[j] &= ((1LL << 32) - 1);
			}
		}
		imos[0][i] = now[0];
		for (int j = 0; j <= gen; j++)now[j] = n[j];
	}
	for (int i = 0; i < gen; i++)
	{
		for (int j = 0; j < gen - i; j++)
		{
			imos[i + 1][j] = (imos[i][j + 1] - imos[i][j] + (1LL << 32))&((1LL << 32) - 1);
		}
	}
	ll t = imos[gen][0];
	ll ans[131];
	for (int i = 0; i <= gen; i++)ans[i] = imos[i][0];
	ll ret = 0;
	for (int i = 1; i <= query; i++)
	{
		ll n[131];
		fill(n, n + 131, 0);
		n[gen] = t;
		for (int j = gen - 1; j >= 0; j--)
		{
			n[j] = (ans[j + 1] + ans[j])&((1LL << 32) - 1);
		}
		for (int j = 0; j <= gen; j++)ans[j] = n[j];
		ret ^= (ans[0] * i)&((1LL << 32) - 1);
	}
	printf("%I64d\n", ret);
}