BZOJ 1925地精部落题解
2024-09-06 03:12:53
一道神仙题,有很多思考的方式,这里选择最好理解的一种来讲
我们将序列分为两种,一种开头递增,一种开头递减,显然这两种序列的数目是一样的
现在我们只用考虑开头递增的情况
f[i][j]表示前i个数,最后一个数字在前i个数的排名在1~j之间的方案数
显然有f[i][j]=f[i][j-1],如果最后一个数下降f[i][j]可以由f[i-1][i-j]转移过来,
如果最后一个数上升,则可以由f[i-1][j-1]转移过来,考虑到每一次转移时没有考虑之前一次的状态最后是上升还是下降的
我们都转移过来会错,由于波动序列具有对称性且我们只考虑了开头递增的序列,所以我们只用从f[i-1][i-j]来转移就ok了
还有,记得加上滚动数组进行优化
# include<iostream>
# include<cstring>
# include<algorithm>
# include<cmath>
# include<cstdio>
using namespace std;
const int mn = ;
long long f[][mn];
int n,p;
int main()
{
scanf("%d%d",&n,&p);
f[][]=;
if(n==)
{
printf("");
return ;
}
int cnt=;
for(int i=;i<=n;i++)
{
cnt=-cnt;
for(int j=;j<=i;j++)
f[cnt][j]=(f[cnt][j-]+f[-cnt][i-j])%p;
}
printf("%lld",(f[cnt][n]*)%p);
return ;
}
最新文章
- 玩儿转物联网IoT - 在Beagle Bone Black上运行node.js 程序
- SQL Server需要监控哪些计数器
- 修改NavigationView中的Item的Icon大小
- DOM中的事件对象
- Released Mocked Streams for Apache Kafka
- 快速掌握Flyway
- ASP.NET WEBAPI 简单CURD综合测试(asp.net MVC,json.net,sql基础存储过程和视图,sqlhelper,json解析)
- C#输入的字符串只包含汉字
- 数据库SQL及相关
- usb2.0 规范学习笔记
- PHP用ajia代码写三级联动下拉
- 查询表达式和LINQ to Objects
- Android注解方式实现表单校验
- [Luogu 3768]简单的数学题
- 还需要注册的是我们还有一个是“交差集” cross join, 这种Join没有办法用文式图表示,因为其就是把表A和表B的数据进行一个N*M的组合,即笛卡尔积。表达式如下:
- zabbix自定义触发器进行监控
- Linux例行工作与系统管理(13)
- php扩展模块安装
- 2018.06.30 BZOJ4765: 普通计算姬(dfs序+分块+树状数组)
- taglib报错The content of element type ";taglib"; must match ";(tlib-version,...)