首页 > 其他分享 >20241004 动态规划选讲

20241004 动态规划选讲

时间:2024-11-08 15:21:13浏览次数:1  
标签:20241004 nn int 选讲 ans 权值 动态 节点 MOD

20241004 动态规划选讲

P6669 [清华集训2016] 组合数问题

使用 Lucas 定理:\(C_n^m\equiv C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{m}{p}\rfloor}C_{n\bmod p}^{m\bmod p}(\bmod p)\)。这等价于将 \(n,m\) 在 \(k\) 进制下的每一位的组合数相乘。要想使 \(k\ |\ C_n^m\),就要存在一位的组合数为 \(0\),也就是 \(n\) 的这一位小于 \(m\) 的这一位。数位 dp 就能求出方案。

#include<bits/stdc++.h>
#define int long long

using namespace std;

inline int read(){
	int w = 1, s = 0;
	char c = getchar();
	for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
	for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
	return s * w;
}

const int INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9 + 7;

int T, k, n, m, cnt, f[1000][2][2][2], a[1000], b[1000];

int dp(int dep, bool ok, bool in, bool jm){
	if (dep == cnt + 1) return ok;
	if (~f[dep][ok][in][jm]) return f[dep][ok][in][jm];
	int limi = in ? a[dep] : k - 1, limj = jm ? b[dep] : k - 1, res = 0;
	for (int i = 0; i <= limi; i++){
		for (int j = 0; j <= limj; j++){
			(res += dp(dep + 1, ok | (i < j), in & (i == a[dep]), jm & (j == b[dep]))) %= MOD;
		}
	}
	return f[dep][ok][in][jm] = res;
}

signed main(){
	T = read(), k = read();
	while (T--){
		n = read(), m = read();
		int tmp = max(n, m), nn = n, mm = m; cnt = 0;
		while (tmp) cnt++, tmp /= k;
		for (int i = cnt; i; i--) a[i] = n % k, n /= k;
		for (int i = cnt; i; i--) b[i] = m % k, m /= k;
		memset(f, -1, sizeof(f));
        int ans = dp(1, false, true, true);
        if (mm > nn) ans = (ans - ((nn + 1) % MOD) * ((2 * mm - nn) % MOD) % MOD * ((MOD + 1) / 2) % MOD + MOD) % MOD;
        else ans = (ans - (mm % MOD) * ((mm + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD + MOD) % MOD;
		cout << ans << endl;
	}
	return 0;
}

P3959 [NOIP2017 提高组] 宝藏

转化一下题意,就是要求出一颗生成树,使得每个点的深度乘上它到父亲的边权的总和最小。注意到 \(n\) 很小,考虑状压 dp。设 \(f_{i,s}\) 表示目前已在生成树中的点集为 \(s\),最大深度为 \(i\) 的最小代价。转移时直接枚举树中下一层选哪些点,这样是 \(O(3^nn)\) 的,再 \(O(n)\) 计算贡献,总复杂度 \(O(3^nn^2)\),常数较小,可以通过。

如何 \(O(n)\) 计算贡献?\(O(2^nn^2)\) 预处理 \(a_{i,s}\) 表示 \(i\) 与点集 \(s\) 相连的边权中的最小值,dp 转移时直接使用即可。

AGC009E Eternal Average

转化一下题意:一颗每个非叶节点都有 \(k\) 个儿子的树,叶节点有 \(n+m\) 个,其中 \(n\) 个权值为 \(0\),\(m\) 个权值为 \(1\),每个非叶节点的权值为儿子权值的平均数,求根节点权值的方案数。

考虑一个深度为 \(dep\) (根的深度为 \(1\))的权值为 \(1\) 的叶节点会对根节点的权值造成什么贡献,发现是 \(\frac{1}{k^{dep}}\)。注意到树的层数不超过 \(t=\frac{n+m-1}{k-1}\),那么将所有点的权值乘以 \(k^t\) 也不会影响答案,这时一个叶子的贡献就为 \(k^{t-dep}\)。

由此可以想到,将根的权值看作一个允许前导 \(0\) 的 \(t\) 为非零 \(k\) 进制数,那么一个叶子的贡献就是在这个数的从低到高第 \(t-dep+1\) 位加上一。暂时不考虑产生进位的情况。可以发现在节点无标号的情况下,这个 \(k\) 进制数和 \(k\) 叉树是一一对应的。那么用一个背包统计有多少种这样的 \(k\) 进制数。考虑存在进位会发生什么,就等价于 \(k\) 个权值为 \(1\) 的叶子变成上一层的一个权值为 \(1\) 的叶子,节点个数减少 \(k-1\)。此时,树的最大深度也会减一,也就是 \(k\) 进制数的位数。那么统计答案时,直接枚举产生了几次进位累加即可。\(n,m\) 同阶,则时间复杂度 \(O(n^2)\)。

int t = (n + m - 1) / (k - 1);
f[0][0] = 1;
for (int i = 0; i < t; i++)
    for (int j = 0; j <= m; j++)
        for (int v = 0; v < k; v++) (f[i + 1][j + v] += f[i][j]) %= MOD;
for (int i = m; i >= 1; i -= k - 1, t--) (ans += f[t][i]) %= MOD;

标签:20241004,nn,int,选讲,ans,权值,动态,节点,MOD
From: https://www.cnblogs.com/luyuyang/p/18535167

相关文章

  • 代码随想录 -- 动态规划 -- 分割等和子集
    416.分割等和子集-力扣(LeetCode)思路:题目中表述:将数组nums分割成两个子集,使得两个子集的元素和相等。可以转化为:有一个背包,如果存在部分元素组合可以令容量为nums的和的一半的背包容纳的最大价值也为nums的和的一半,那么剩下的元素和也是nums的一半,则符合题意。dp[j]含义:......
  • 动态按钮Demo
    概要在网页中,动态按钮不仅能够提升用户体验,还能增强界面的互动性。本文将教会你如何利用前端技术实现动态按钮,以及它们在提升网站交互性方面的重要性。如下效果图:整体架构流程动态按钮的实现涉及到HTML、CSS和JavaScript的协同工作。HTML负责结构的搭建,CSS负责样式的......
  • 代码随想录算法训练营第三十九天|Day39 动态规划
    198.打家劫舍视频讲解:https://www.bilibili.com/video/BV1Te411N7SXhttps://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html思路#definemax(a,b)((a)>(b)?(a):(b))introb(int*nums,intnumsSize){if(numsSize==0){re......
  • 代码随想录算法训练营第四十天|Day40 动态规划
    121.买卖股票的最佳时机视频讲解:https://www.bilibili.com/video/BV1Xe4y1u77qhttps://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html思路#definemax(a,b)((a)>(b)?(a):(b))#definemin......
  • 利用FreeSql.Generator自动根据数据库表动态生成实体类
    安装dotnettoolinstall-gFreeSql.Generator示例FreeSql.Generator-Razor1-NameOptions0,0,0,1-NameSpaceLinCms.Core.Entities-DB"MySql,DataSource=127.0.0.1;Port=3306;UserID=root;Password=123456;InitialCatalog=lincms;Charset=utf8;SslMode=none;M......
  • (算法)零钱兑换II————<动态规划>
    1.题⽬链接:518.零钱兑换II2.题⽬描述: 3.解法(动态规划):算法思路:先将问题「转化」成我们熟悉的题型。i.在⼀些物品中「挑选」⼀些出来,然后在满⾜某个「限定条件」下,解决⼀些问题,⼤概率是背包模型;ii.由于每⼀个物品都是⽆限多个的,因此是⼀个「完全背包」问题。接......
  • (算法)零钱兑换————<动态规划>
    1.题⽬链接:322.零钱兑换2.题⽬描述:3.解法(动态规划):算法思路:先将问题「转化」成我们熟悉的题型。i.在⼀些物品中「挑选」⼀些出来,然后在满⾜某个「限定条件」下,解决⼀些问题,⼤概率是「背包」模型;ii.由于每⼀个物品都是⽆限多个的,因此是⼀个「完全背包」问题。接......
  • 带你用HTML+CSS+JS实现动态滚动骰子投掷效果!
    今天带大家用HTML+CSS+JS实现动态骰子投掷效果,下面来看看实现的效果:点击开始投掷,骰子开始滚动。点击停止投掷,骰子面会随机定在一个点数 那么如何实现呢?请听我细细讲解:一、骰子面的样式与布局1、样式:1、其中每一面大量的运用了flex布局来实现了骰面上圆点的位置。2......
  • MyBatis Plus之注解实现动态SQL
     参考下面的sql语句即可实现@Select("<script>"+"selectgp.TEWRTYR,gp.FJFNM,gs.CVNNN,u.VCNBMBNV,gp.RAEER,gr.BVNCCVN\n"+"fromUPPBHTu\n"+"leftjoinGP_testgp\n"+......
  • 【算法】动态规划
    一、算法概念动态规划算法是一种解决多阶段决策问题的方法。它将一个问题分解为多个子问题,并逐个求解子问题的最优解,最后得到原问题的最优解。二、基本思想动态规划算法的核心思想是通过存储中间结果来避免重复计算。在解决问题的过程中,会利用已经求解过的子问题的最优解......