【BZOJ4475】 [Jsoi2015]子集选取
2024-09-08 05:12:53
题目描述
数据范围
\(1\leq N,K \leq 10^9\)
\(solution\)
集合S中每个元素互不影响,不妨依次考虑其中一个元素在三角形中的出现情况
问题转化为一个\(0/1\)的三角形\(\{A_{i,j}\}\),用\(0\)表示选了,\(1\)表示没选,那么如果\(A_{i,j}\)为\(1\),则\(A_{i,j}\)左边和上边都是\(1\)
考虑\(n\)比较小的情况,可以DP
\(f_i\)表示一个\(i*i\)的三角形的方案数
对于\(f_i\),第\(i\)行一定是一段\(1\)和一段\(0\)拼起来,枚举\(1\)的长度\(j\),前\(j\)列的元素都必须选\(1\),其他列除去第\(i\)行构成一个长为\((i-j-1)\)的三角形,填法为\(f_{i-j-1}\)种
最后加上是第\(i\)行全选\(1\)的情况,只有\(1\)种
\(f_i=1+\sum_{j=0}^{i-1}f_{i-j-1}=1+\sum_{j=0}^{i-1}f_j\)
\(f_0=1\)
不妨令\(S_i=\sum_{j=0}^if_j\)
原式\(f_i=1+S_{i-1}\)即\(S_{i-1}=f_i-1\)
则有
\(S_i-S_{i-1}=(f_{i+1}-1)-(f_i-1)\)
即 \(f_i=f_{i+1}-f_{i}\)
\(f_{i+1}=2*f_i\) 且\(f_0=1\)
得\(f_n=2^n\)
\(ans={f_n}^k=2^{nk}\)
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
const int MOD=1000000007;
int n,k;
inline int qpow(int x,int k){
int s=1;
while(k){
if(k&1) s=s*x%MOD;
k>>=1;
x=x*x%MOD;
}
return s;
}
signed main()
{
scanf("%lld%lld",&n,&k);
printf("%lld\n",qpow(2,n*k));
return 0;
}
最新文章
- 电脑技巧:Win8/Win10无法打开这个应用|无法使用内置管理员账户的完美解决方法
- POJ C程序设计进阶 编程题#6:流感传染
- 【原创】用Pwnage + Redsnow 制作完美越狱固件
- 01_JavaMail_04_带附件邮件的发送
- CentOS 6.3 源码安装LAMP(Linux+Apache+Mysql+Php)环境
- 剑指offer面试题3 二维数组中的查找(c)
- avg 的使用
- centos 安装sbt
- js之获取元素最终css属性
- Jetson tk1 hash sum mismatch
- postgresql-pg_prewarm数据预加载。
- metasploit学习之情报搜集
- Disk Genius 彻底清理硬盘空闲
- <;mvc:annotation-driven/>;的作用
- gentoo emerge unable to sync
- Qt——父对象、布局
- Metadata 的概念
- 【01】在 issue 中创建 list
- WebSocket客户端学习
- HDU oj A + B Problem II