【CF1152F】Neko Rules the Catniverse(动态规划)
规划 The 动态 rules
2023-09-11 14:14:40 时间
【CF1152F】Neko Rules the Catniverse(动态规划)
题面
题解
我们先考虑一个需要扫一遍所有位置的做法。
那么状态一定是\(f[i]\)然后什么什么表示考虑到当前第\(i\)个位置的答案。
看看我们还需要记录什么,首先肯定要记录的是当前已经选了几个,所以多了一维\(j\)。
然后考虑现在这个能不能选。
首先如果这个元素放在某个元素之前,后面一定是合法的,因为当前位置一定是全局的最大值,所以只需要考虑它可以放在谁之前就行了。
而限制是\(x\le y+m\),那么我们暴力压状态记录前\(m\)个是否被选择。
那么首先这个元素放在第一个一定是可以的,然后这个元素如果不放在第一个就要放在某一个的后面,那么就只有可能放在最后\(m\)个存在元素的后面,那么判断一下就行啦。
然后发现转移是一模一样的,所以直接矩乘就行了。
#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 1000000007
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int b[13][1<<4],bel[1<<4],n,K,m,N,ans;
struct Matrix
{
int s[210][210];
void clear(){for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)s[i][j]=0;}
void init(){clear();for(int i=1;i<=N;++i)s[i][i]=1;}
int*operator[](int x){return s[x];}
}A,Tr;
Matrix operator*(Matrix &a,Matrix &b)
{
Matrix c;c.clear();
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
for(int k=1;k<=N;++k)
c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;
return c;
}
int main()
{
n=read();K=read();m=read();
for(int i=1;i<1<<m;++i)bel[i]=bel[i>>1]+(i&1);
for(int j=0;j<=K;++j)
for(int S=0;S<1<<m;++S)b[j][S]=++N;
for(int j=0;j<=K;++j)
for(int S=0;S<1<<m;++S)
{
int T=(S<<1)&((1<<m)-1);
add(Tr[b[j][S]][b[j][T]],1);
if(j<K)add(Tr[b[j][S]][b[j+1][T|1]],bel[S]+1);
}
A[1][1]=1;
while(n){if(n&1)A=A*Tr;Tr=Tr*Tr;n>>=1;}
for(int i=0;i<1<<m;++i)add(ans,A[1][b[K][i]]);
printf("%d\n",ans);
return 0;
}
相关文章
- PRVF-5436 : The NTP daemon running on one or more nodes lacks the slewing option "-x"
- 【CF1132F】Clear the String(动态规划)
- 【BZOJ1093】[ZJOI2007]最大半联通子图(Tarjan,动态规划)
- 【arc093f】Dark Horse(容斥原理,动态规划,状态压缩)
- 【BZOJ5311/CF321E】贞鱼/Ciel and Gondolas(动态规划,凸优化,决策单调性)
- 【CF613D】Kingdom and its Cities(虚树,动态规划)
- golang错误:The process cannot access the file because it is being used by another process
- 【软件测试】软件测试工程师趋势,发展规划路线前景与方向(最全面)
- (《机器学习》完整版系列)第4章 线性模型——4.1 决策树算法(不是规划论中的决策树,深度优先或广度优先)
- Flutter 调用百度地图APP实现位置搜索、路线规划
- 算法笔记之动态规划
- 【BZOJ2699】更新 动态规划
- 【BZOJ2090/2089】[Poi2010]Monotonicity 2 动态规划+线段树
- 测试开发工程师程序员为什么会忧虑自己的未来?最黄金年龄规划 IDP
- The connection to the server localhost:8080 was refused - did you specify the right host or port?
- HDU 6346 整数规划 (最佳完美匹配)
- 继承“HibernateDaoSupport”后,报“The hierarchy of the type AccoutDaoImpl is inconsistent”的解决方案
- 【解决方案】ERROR: lib/bridge_generated.dart:837:9: Error: The parameter ‘ptr‘ of the method ‘FlutterRustB
- The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path
- 程序员2020年新书推荐之 《Coders: The Making of a New Tribe and the Remaking of the World》
- MYSQL导入csv类型的数据出现The MySQL server is running with the --secure-file-priv option
- mysql导出数据报错The MySQL server is running with the --secure-file-priv option so it cannot execute this statement
- Weblogic发布小问题——The root element weblogic-web-app is missing in the descriptor file
- LeetCode139之单词拆分(相关话题:动态规划)
- suseoj 1209: 独立任务最优调度问题(动态规划)
- suseoj The wheat of the prime minister
- nyoj 18-The Triangle(动态规划)
- 最优化课程笔记07——约束问题的非线性规划方法(重点:拉格朗日乘子法和惩罚函数法)
- 最优化作业第6章——无约束多维非线性规划方法
- The type name 'IComponentConnector' could not be found in the namespace 'System.Windows.Markup'
- Mysql 1290 - The MySQL server is running with the --secure-file-priv option