文档章节

牛牛与数组 (简单dp)

o
 osc_n6euf5h6
发布于 2019/03/19 20:23
字数 471
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目链接
这种题一看就是dp啊,dp[i][j]表示第i位放j的方案数,转移方程为dp[i][j]=dp[i-1][k]{k<=i||k%i!=0},当然我们可以三层循环来找,但数据显然会超时,那么我们只能在第二层循环中用中间变量记录一下可以省去一层循环,但是为倍数的情况必须要考虑,所以先预处理出所有的倍数,然后dp的过程中减去倍数的情况即可,总体复杂度O(n* k * sqrt(k)。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
const LL mod=1e9+7;
LL dp[11][100003];
vector<LL>p[100001];
LL n,k;
void P(){//预处理倍数
	for(int i=1;i<=k;i++){
		for(int j=2;1ll*j*i<=k;j++){
			p[i].pb(j*i);
		}
	}
}
LL a[111];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	P();
	for(int i=1;i<=k;i++)dp[1][i]=1;
	for(int i=1;i<=n;i++)dp[i][1]=1;
	for(int i=2;i<=n;i++){
		LL pr=0;
		for(int j=1;j<=k;j++)pr=(0ll+pr+dp[i-1][j])%mod;
		LL sum=dp[i-1][1];
		for(int j=2;j<=k;j++){
			LL mi=pr;
			dp[i][j]=(0ll+sum+dp[i-1][j])%mod;
			sum=(0ll+sum+dp[i-1][j])%mod;//为dp[i-1][1]到dp[i-1][j]的和
			mi-=sum;
			for(int x:p[j]){
				mi-=dp[i-1][x];//减去倍数
			}
			dp[i][j]+=mi;
		}
	}
	LL ans=0;
	for(int i=1;i<=k;i++)ans=(ans+dp[n][i])%mod;
		cout<<ans;
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
[ 题解 ] [ 动态规划 ] B. Teamwork

http://codeforces.com/group/NVaJtLaLjS/contest/238203/problem/B 题意: 农夫让牛来包装礼物,N只牛有各自的能力值。 相邻K只牛可以组成一个小组,小组内牛的能力全会提高到与小组内最高的...

osc_ik0wlz7f
2019/03/15
4
0
QAQorz的训练记录

感觉还是该从今天开始记下来 5.8日查询 870(查询系统) + 100(洛谷) + 100(牛客) = 1070题, 去重按1000题算 5.8 牛客寒训营 3F 双向搜索+处理前后缀积 牛客寒训营 5G 唯一分解, 埃氏筛法的理解...

osc_k0q149k0
2019/05/08
1
0
Cow Exhibition POJ - 2184

题目地址:https://vjudge.net/problem/POJ-2184 下面的解释是从一个大佬那搬来的,讲的很清楚 题意:给定一些奶牛,每个牛有s和f两个属性值,有正有负,要求选出一些牛, 使得这些牛的两种属...

SSummerZzz
2019/07/10
0
0
牛客2018.6模拟考编程题

emmm,今天的题目不知道怎么评价,感觉不难但是可能是太菜了,感觉时间不够and测试数据有点?emm异常。。 1.牛牛玩牌   题目如上,比较前三张的大小,模拟前者大于后者的可能数。样例没看懂...

osc_wqha5akl
2018/06/14
2
0
回顾二分与bfs(或者说是递推)和简单模拟

今天,阳光正好,适合敲代码,诸事皆宜。 先来两道简单的模拟题。 第一道 机器翻译 输出为5. 代码思路:很明显需要用到队列来存单词,在建立一个bool数组来存储队列中有没有这个单词,需不需...

清风紫雪
2019/07/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么从HBase的0.96版本开始,舍弃了-ROOT-文件?

HBase结构的读写流程 (1). HBase0.96版本之前: (2). HBase0.96开始: a. 当客户端获取到.meta文件的位置之后,会缓存.meta.文件的位置 b. 客户端还会缓存HRegion的位置 -ROOT-存在的意义: ...

其乐m
4分钟前
0
0
volatile关键字对 - What is the volatile keyword useful for

问题: At work today, I came across the volatile keyword in Java. 今天的工作中,我遇到了Java中的volatile关键字。 Not being very familiar with it, I found this explanation: 不太熟......

技术盛宴
10分钟前
15
0
golang 封装 mysql 和 redis 连接

Mysql封装 package dbimport ("fmt"_ "github.com/go-sql-driver/mysql""github.com/jmoiron/sqlx")var DB *sqlx.DBfunc init(){database, err := sqlx.Op......

开源中国最牛的人
10分钟前
4
0
pdfbox 读取文件报错 java.io.IOException: Page tree root must be a dictionary

pdfbox java.io.IOException: Page tree root must be a dictionary 示例代码 public static void main(String[] args) { try (InputStream sampleInputs = new ClassPathResource("s......

lemos
19分钟前
28
0
整理 Linux下列出目录内容的命令

在 Linux 中,有非常多的命令可以让我们用来执行各种各样的任务。当我们想要像使用文件浏览器一样列出一个目录下的内容时,大家第一时间想到的是 ls 命令。但只有 ls 命令能实现这个目的吗?...

良许Linux
20分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部