UOJ426. 【集训队作业2018】石像 [状压DP,min_25筛]
2024-08-22 11:58:33
思路
(以下思路是口胡,但正确性大概没有问题。)
刚学min_25筛的时候被麦老大劝来做这题?
结果发现这题是个垃圾二合一??
简单推一下式子可以得到答案就是这个:
\[\sum_{T=1}^m (f*\mu)(T)\sum_{\{a_i\le m/T \}} \prod_i [a_{x_i}\le a_{y_i}]
\]
\]
其中\(f(n)=(\sigma_0(n^3))^3\)。
通过手玩可以得到\((f*\mu)(p^c)=81c^2-27c+9,c\ne 0\),于是可以min_25求前缀和。
现在问题转化为:对于一个给定的上界,求满足限制的\(\{a_n\}\)有几个。
先缩点。考虑枚举\(\{a_n\}\)中不同的\(a\)有几个,然后状压DP:设\(f_S\)表示从小到大放,当前已经放了\(S\)的方案数。我们做\(n\)次转移,做完\(i\)次之后\(f_U\)就是至多\(i\)个不同的\(a\)的方案数。
转移可以枚举子集,但显然会TLE。考虑一个点能被放上去当且仅当小于它的全都放上去了,于是有一个根据拓扑序转移的方法:
f[0]=1;
rep(i,1,n)
{
repd(j,n,1)
{
int s=((1<<n)-1)^mp[j]^(1<<j-1);
for(int k=s; ; k=(k-1)&s)
{
f[k^mp[j]^(1<<j-1)]+=f[k^mp[j]];
if(!k) break;
}
}
cur[i]=f[(1<<n)-1];
}
(麦老大nb!)
其中\(n\)的拓扑序最大,\(mp_j\)记录\(j\)直接连向的点。
最后对\(cur\)二项式反演一下就没了。
代码
咕咕咕
最新文章
- dede织梦后台如何修改?如何增加删除菜单?(
- s3c2440 lcd 显示图片裸机程序
- C/C++中的abort、atexit、exit和_Exit
- 利用checkbox的到值,并且存到数据库修改的话要显示之前选择的
- 获取 CPU 序列号
- ArrayList 类和List<;T>;泛型类
- jsp页面中定时的方法
- linux make
- foreach 和for语句比较
- Android - 支持不同的设备
- [1] [转]软件架构之三层架构和MVC的关系
- 201521123051《java程序设计》 第一周学习总结
- Spring mybatis源码学习指引目录
- Effective Java 第三版——34. 使用枚举类型替代整型常量
- static:get()什么意思
- Web应用启动时,后台自动启动一个线程(转)
- 【Loj117】有源汇上下界最小流(网络流)
- Win10系列:C#应用控件基础23
- php多维数组排序
- pip 国内源 配置