AtCoder Regular Contest 096

C.Everything on It

题目描述

点此看题

解法

先思考一个简化的问题，如果要求是 \(1,2...n\) 都在其中至少出现 \(1\) 次我们会怎么做？直接上容斥，我们枚举出现次数 \(=0\) 数的个数，然后其他的乱选即可。

上述方法是可扩展的，我们可以枚举出现次数 \(\leq 1\) 数的个数，那么可以写出式子：

\[\sum_{i=0}^n (-1)^i\cdot {n\choose i}\cdot2^{2^{n-i}}\cdot f(i) \]

其中 \(f(i)\) 表示钦定 \(i\) 个数出现次数 \(\leq 1\) 的方案数，关键的 \(\tt observation\) 是涉及到的集合数量不会超过 \(i\) 个，而且知道了集合数量方案数是会好算很多的。所以再处理一个 \(g(i,j)\) 表示用 \(j\) 个集合去覆盖 \(i\) 个数，每个数最多被覆盖一次的方案数，转移：

\[g(i,j)=g(i-1,j-1)+(j+1)\cdot g(i-1,j) \]

转移的含义是考虑当前的数 新增一个集合 \(/\) 填入以前的集合（\(j\) 种方案）\(/\) 不覆盖，那么 \(f(i)\) 就很容易表示了：

\[f(i)=\sum_{j=0}^i g(i,j)\cdot 2^{j(n-j)} \]

解释一下后面的 \(2^{j(n-j)}\)，实际上就是把未钦定的元素考虑进去，它们加入这些集合是任意的。

只能说这道题完全在我的能力范围以内，时间复杂度 \(O(n^2)\)

#include 
const int M = 3005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,g[M][M],C[M][M];
void add(int &x,int y) {x=(x+y)%m;}
int qkpow(int a,int b,int p)
{
	int r=1;
	while(b>0)
	{
		if(b&1) r=r*a%p;
		a=a*a%p;
		b>>=1;
	}
	return r;
}
signed main()
{
	n=read();m=read();g[0][0]=1;
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			add(C[i][j],C[i-1][j-1]+C[i-1][j]);
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
		{
			if(j) add(g[i][j],g[i-1][j-1]);
			add(g[i][j],(j+1)*g[i-1][j]);
		}
	for(int i=0;i<=n;i++)
	{
		int z=C[n][i]*qkpow(2,qkpow(2,n-i,m-1),m)%m;
		int f=0,x=qkpow(2,n-i,m);if(i&1) z=m-z;
		for(int j=0,y=1;j<=i;j++,y=y*x%m)
			add(f,g[i][j]*y);
		add(ans,f*z);
	}
	printf("%lld\n",(ans+m)%m);
}

D.Sweet Alchemy

题目描述

点此看题

解法

首先吐槽一下这场的题目真的清新，但是又具有一定的思维难度，大家多学学这场的出题人。

首先可以用差分将题目做一个基本的转化，设 \(b_i=c_i-c_{p_i}\)，那么有 \(0\leq b_i\leq d\)，所以可以将问题转化成：有 \(n\) 种物品，第 \(i\) 种物品的价值是子树 \(i\) 的大小，容量是子树 \(i\) 的 \(\sum m_v\)，除了第一种物品可以选任意多次外，其它物品最多取 \(d\) 次。

现在得到的问题是价值很小，种类很小，但是容量很大的多重背包问题。貌似没有什么好的思路，我们不妨倒回初学背包问题的时候，有一种经典性价比贪心，也就是按照 价值 \(w_i\) \(/\) 重量 \(v_i\) 从大到小排序，但是是错的。

正确的做法是我们对于每个物品只保留 \(\min(n,d)\) 个来跑背包，设 \(dp[i]\) 表示选取 \(i\) 个物品用掉的最小容量，可以用二进制分组优化，时间复杂度 \(O(n^4\log n)\)，对于剩下的物品，我们用性价比贪心即可。

感性理解上面的做法并不难，这里给出我自己的证明。

考虑排序后的物品性质，\(\forall i，不存在 \(i\) 未选取的数量 \(\geq n\)，\(j\) 选取的数量 \(\leq n\)，否则可以调整。

那么我们只需要考虑所有满足 \(\forall i，\(i\) 未选取的数量 \( 或者 \(j\) 选取的数量 \( 的情况即可。

发现如果某个物品 \(x\) 选取的数量 \(\geq n\)，它实际上会要求 \([1,x)\) 这个前缀未选取的数量 \(，那么如果我们把每个物品提出 \(n\) 个来跑背包（相当于决策所有情况），那么选取物品 \(x\) 就要求把 \([1,x)\) 这个前缀选取完，对应了我们的性价比贪心。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int M = 55;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,d,mx,a[M],dp[M*M*M];vector g[M];
struct node{int w,v;}s[M];
void dfs(int u)
{
	for(int v:g[u])
	{
		dfs(v);
		s[u].w+=s[v].w;
		s[u].v+=s[v].v;
	}
}
signed main()
{
	n=read();m=read();d=read();
	for(int i=1;i<=n;i++)
	{
		s[i].v=read();s[i].w=1;
		if(i>1) g[read()].push_back(i);
	}
	dfs(1);mx=n*n*n;k=min(n,d);
	memset(dp,0x3f,sizeof dp);dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int x=k;
		for(int j=0;(1<=w;l--)
				dp[l]=min(dp[l],dp[l-w]+v);
			x-=(1<=w;l--)
				dp[l]=min(dp[l],dp[l-w]+v);
		}
	}
	sort(s+1,s+1+n,[&](node x,node y)
	{return x.w*y.v>x.v*y.w;});
	int r=n,ans=0;while(s[r].w!=n) r--;
	for(int i=0;i<=mx;i++)
	{
		if(dp[i]>m) continue;
		int w=i,v=dp[i];
		for(int j=1;j