首页 > 其他分享 >[USACO23FEB] Problem Setting P 题解

[USACO23FEB] Problem Setting P 题解

时间:2024-11-08 21:43:21浏览次数:3  
标签:int 题解 ll init Setting res using Problem MOD

[USACO23FEB] Problem Setting P

题目说的很绕,意思就是所有验题人都认为题目难度顺序单增

发现 \(m\) 很小,很容易想到状压。把 H 看作 \(\tt1\),E 看作 \(\tt0\),则我们得到 \(m\) 个长度为 \(n\) 的 \(\tt01\) 串,这就是每道题的 “状态”。发现状态相同的题没有本质区别,所以我们对于每个状态都统计有多少个题目,记为 \(c_i\)。

而对于单增的限制条件,我们转化为:对于所有相邻的两道题 \(i\) 和 \(i+1\),设 \(s_i\) 为第 \(i\) 题的状态,则一定满足:\(s_i\subseteq s_{i+1}\)。

于是设 \(f_i\) 为当前选中最后一道题的状态为 \(i\) 的方案数。那么转移时,我们首先要找到上一道题的状态 \(j\),且这个 \(j\) 一定满足 \(j\subseteq i\)。注意若 \(j=i\),则一定有一种方案,这里需要预先加上 \(1\)。综上,统计:

\[v=1+\sum_{j\subset i}f_j \]

这就是能选的状态集合。至于当前 \(i\) 有多少种排列方式,这也是好计算的。相当于从 \(c_i\) 个中挑选任意个(不为 \(0\))并任意排列,统计公式为:

\[s=\sum_{k=1}^{c_i}(c_i)^{\underline k}=\sum_{k=0}^{c_i-1}\frac{c_i!}{k!} \]

最后的 \(f_i=vs\)。

这个方法的复杂度是 \(O(3^m)\) 的,瓶颈在于遍历子集。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
constexpr int MAXN=1e5+5,MAXM=1<<20,MOD=1e9+7;
int n,m,num[MAXN],c[MAXM],f[MAXN],ans;
int fac[MAXN],inv[MAXN];
int g[MAXM][21];
string s;
void add(int&x,int y){
	x=x+y>=MOD?x+y-MOD:x+y;
}
int power(ll a,int b){
	ll res=1;
	for(;b;a=a*a%MOD,b>>=1)if(b&1)res=res*a%MOD;
	return res;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%MOD;
	inv[n]=power(fac[n],MOD-2);
	for(int i=n-1;~i;--i) inv[i]=(ll)inv[i+1]*(i+1)%MOD; 
}
int calc(int ci){
	int res=0;
	for(int i=0;i<ci;++i)
		add(res,(ll)fac[ci]*inv[i]%MOD);
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	init();
	for(int i=1;i<=m;++i){
		cin>>s;
		for(int j=0;j<n;++j)
			if(s[j]=='H')
				num[j+1]|=1<<(i-1);
	}
	for(int i=1;i<=n;++i) ++c[num[i]];
	f[0]=calc(c[0]);
	for(int i=1;i<=m;++i) g[0][i]=f[0];
	ans=f[0];
	for(int i=1,B=1<<m,v;i<B;++i){
		v=1;
		for(int j=1;j<=m;++j)
			if(i&(1<<(j-1)))
				add(v,g[i^(1<<(j-1))][j]);
		f[i]=(ll)v*calc(c[i])%MOD;
		add(ans,f[i]);
		g[i][1]=f[i];
		for(int j=1;j<m;++j){
			g[i][j+1]=g[i][j];
			if(i&(1<<(j-1))) add(g[i][j+1],g[i^(1<<(j-1))][j]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

考虑满分做法。引入辅助数组 \(g_{i,j}\) 表示:找到所有的 \(f_k\) 并求和,这些 \(k\) 满足 \(k\subseteq i\) 且对 \(k\) 和 \(i\) 有不同意见的编号最大的验题人的编号为 \(j-1\)(\(j=0\) 时即为没有区别),公式表示下来就是:

\[g_{i,j}=\sum_{\substack{k\subseteq i\\[0.5ex]\max x\in\complement_ik=j-1}}f_k \]

所以原本的 \(O(3^m)\) 枚举子集的转移就被优化为了 \(O(m2^m)\) 转移,因为对于 \(f_i\) 的转移我们只需要枚举有不同意见的编号最大的验题人的编号就行了。

当然对于 \(g_{i,j}\) 的转移也有,首先 \(g_{i,0}=f_i\),然后:

  • 若 \(i\) 的 \(j-1\) 位为 \(\tt0\),则 \(g_{i,j}=g_{i,j-1}\);
  • 否则 \(g_{i,j}=g_{i,j-1}+g_{i\setminus\{\max x\in i\},j-1}\),其中 \(i\setminus\{\max x\in i\}\) 意思是 \(i\) 去掉最大的元素后组成的集合。
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
constexpr int MAXN=1e5+5,MAXM=1<<20,MOD=1e9+7;
int n,m,num[MAXN],c[MAXM],f[MAXN],ans;
int fac[MAXN],inv[MAXN];
int g[MAXM][21];
string s;
void add(int&x,int y){
	x=x+y>=MOD?x+y-MOD:x+y;
}
int power(ll a,int b){
	ll res=1;
	for(;b;a=a*a%MOD,b>>=1)if(b&1)res=res*a%MOD;
	return res;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%MOD;
	inv[n]=power(fac[n],MOD-2);
	for(int i=n-1;~i;--i) inv[i]=(ll)inv[i+1]*(i+1)%MOD; 
}
int calc(int ci){
	int res=0;
	for(int i=0;i<ci;++i)
		add(res,(ll)fac[ci]*inv[i]%MOD);
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	init();
	for(int i=1;i<=m;++i){
		cin>>s;
		for(int j=0;j<n;++j)
			if(s[j]=='H')
				num[j+1]|=1<<(i-1);
	}
	for(int i=1;i<=n;++i) ++c[num[i]];
	f[0]=calc(c[0]);
	for(int i=1;i<=m;++i) g[0][i]=f[0];
	ans=f[0];
	for(int i=1,B=1<<m,v;i<B;++i){
		v=1;
		for(int j=1;j<=m;++j)
			if(i&(1<<(j-1)))
				add(v,g[i^(1<<(j-1))][j]);
		f[i]=(ll)v*calc(c[i])%MOD;
		add(ans,f[i]);
		g[i][1]=f[i];
		for(int j=1;j<m;++j){
			g[i][j+1]=g[i][j];
			if(i&(1<<(j-1))) add(g[i][j+1],g[i^(1<<(j-1))][j]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

标签:int,题解,ll,init,Setting,res,using,Problem,MOD
From: https://www.cnblogs.com/laoshan-plus/p/18535926

相关文章

  • P11253 [GDKOI2023 普及组] 小学生数学题 题解
    题目传送门前置知识积性函数|乘法逆元解法观察到\(f(i)=\frac{1}{i^{k}}\bmodp\)是完全积性函数,线性筛预处理即可。需要适当的取模优化。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsignedlonglong#definesortstab......
  • 【题解】CF1997
    A首先,插入的字符必须和左右两边的字符都不一样其次,对于插入位置的选择,显然最好插在两个一样的字符中间,如果没有一样的字符,插在最前面即可B观察样例发现题目中要求的位置就在样例中手玩一下,尝试改变样例里那个形状,发现改变任何一个格子都不满足题意,所以得出结论:题目要求的......
  • [USACO23JAN] Subtree Activation P 题解
    这种问题一看满足条件就知道,一般不用想着怎么模拟题意。考虑转化问题。假如节点\(u\)满足了条件一,也就是仅有子树节点全部开启。那么我们把转化具象为:进行\(\text{siz}_u\)次操作直接清空;进行\(\text{siz}_{\text{fa}(u)}-\text{siz}_u\)次操作使\(\text{fa}(u)\)满足......
  • 【题解】「NOIP2024模拟赛24 T2」子序列们
    【题解】「NOIP2024模拟赛24T2」子序列们https://www.becoder.com.cn/contest/5715/problem/2\(\mathcal{Description}\)给定一个0/1串\(a\),你需要生成一个长度为\(n\)的序列\(b\),其中\(b_i\)为\(a\)的一个子序列,且满足:\(|b_i|=n-i+1\);\(\foralli\in(1,n]\),\(b......
  • 题解:P11266 【模板】完全体·堆
    也算是对pb_ds库中的优先队列各种操作的科普?一些碎碎念提醒:你可以不看这部分,这部分算是作者探索未知功能的过程平常写优先队列的时候一般用不到对值进行修改或者删除的操作,所以我在看这到题的时候在想怎么才能实现题目中的操作,因为我不知道有什么成员函数可以直接获取具体哪......
  • Hive3.1.2搭建文档包含详细步骤及相关截图以及常见问题解决
    hive-3.1.2分布式搭建文档1、下载,上传,解压,配置环境变量#1、解压(解压到上级目录)tar-zxvfapache-hive-3.1.2-bin.tar.gz-C..#2、重名名mvapache-hive-3.1.2-binhive-3.1.2#3、配置环境变量vim/etc/profile#4、在最后增加配置exportHIVE_HOME=/usr/local/......
  • P1525 NOIP2010 提高组 关押罪犯 题解
    Link:P1525NOIP2010提高组关押罪犯-洛谷分析首先题目给出了罪犯与罪犯之间的矛盾关系,这让我们可以想到图或并查集。然后,题目又说了要把罪犯分入两个监狱,也就是把罪犯看作点,要把这些点分入两个集合,这很自然地可以想到二分图。再然后,市长只会去看列表中的第一个事件的影响力......
  • 题解
    最近模拟赛抽象题太多了,让他们聚一聚T1多校A层冲刺NOIP2024模拟赛18T3DBA暴力比较显然,直接数位dp就好,记搜的复杂度是\(O(n^4)\)的,用递推加前缀和优化可以优化为\(O(n^3)\),但我还是不理解\(O(n^3)\)凭啥能\(拿97pts\),虽然和正解没啥关系,但还是放一下记搜的代码:点击查看代码......
  • CF1995 题解
    B有n种物品,每种物品价格为$a_i$,数量为$c_i$。要求选取物品的方案,满足价格极差不超过1,价格总和不超过m。最大化价格总和。$n\le10^5,m\le10^{18},a_i,c_i\le10^9,a_i\neqa_j$显然只有\(x\)和\(x,x+1\)两种选择情况。\(x\)直接贪心选即可,考虑\(x,x+1\)。发......
  • ICPC23沈阳区域赛 D. Dark LaTeX vs. Light LaTeX 题解
    D.DarkLaTeXvs.LightLaTeXThe2023ICPCAsiaShenyangRegionalContest(The2ndUniversalCup.Stage13:Shenyang)给两个字符串\(s,t\),长度分别为\(n,m\),现在分别取\(s,t\)的子串\(s',t'\),合成一个新的长度为偶数的字符串\(str=s'+t'\),记\(str\)的长度为......