拉格朗日插值优化DP
拉格朗日插值优化DP
模拟赛出现神秘插值,太难啦!!
回忆拉格朗日插值是用来做什么的
对于一个多项式\(F(x)\),如果已知它的次数为\(m - 1\),且已知\(m\)个点值,那么可以得到
\]
所以,如果我们知道要求的东西是一个次数比较友好的多项式且容易求出一些点值,那么就可以把答案插出来。
来看两道例题
CF995F Cowmpany Cowmpensation
题意:给你一棵树,要求给每个点分配\([1,d]\)内的权值,且儿子的权值不能超过父亲的权值,对\(10^9+7\)取模,\(D\leq 10^9\)
很容易得到一个\(\text{DP}\),设\(f_{u,i}\)表示u子树内u的权值大于等于\(i\)的答案,那么
\]
但是\(i\)的值域是\([1,D]\),根本做不了,怎么办?
拉格朗日插值登场。
假设\(u\)是一个叶子结点,那么\(f_{u,i} = D - i + 1\)是一个关于\(i\)的一次多项式
由于转移方程是简单的乘法和加法的形式,可以看出来\(f_{u,i}\)就是一个关于\(i\)的多项式,到这里我们需要考虑的就是这个多项式的次数是多少。
设\(g_u\)表示\(f_{u,i}\)的次数,那么根据上面的状态转移方程,可以得到
\]
根据多项式基础知识,一个多项式差分,次数减一;多个多项式相乘,子树相加,那么就有
\]
这里\(sz_u\)表示\(u\)子树的大小
所以答案就是一个关于\(d\)的\(n\)次多项式,求出\(n+1\)个点值后即可使用拉格朗日插值得到答案。
点我看代码 (-o⌒) ☆
#include <cstdio>
#include <vector>
#include <iostream>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const int N = 3010;
const LL P = 1e9 + 7;
int n, d, m;
int f[N][N << 1];
int y[N << 1];
vector <int> G[N];
void dfs(int u) {
for(int i = 1; i <= m; ++i) f[u][i] = 1;
for(auto v : G[u]) {
dfs(v);
for(int i = m; i ; --i)
f[u][i] = 1ll * f[u][i] * f[v][i] % P;
}
for(int i = m - 1; i ; --i) f[u][i] = (f[u][i] + f[u][i + 1]) % P;
}
LL fpow(LL x, int pnt = P - 2) {
LL res = 1;
for(; pnt; pnt >>= 1, x = x * x % P) if(pnt & 1) res = res * x % P;
return res;
}
int Lagrange(int x) {
if(1 <= x && x <= m) return y[x];
LL res = 0;
for(int i = 1; i <= m; ++i) {
LL p = y[i], q = 1;
for(int j = 1; j <= m; ++j)
if(i ^ j) p = p * (x - j) % P, q = q * (i - j) % P;
res = (res + p * fpow(q)) % P;
}
return res;
}
int main() {
read(n), read(d);
for(int i = 2, u; i <= n; ++i) {
read(u);
G[u].emplace_back(i);
}
m = n + 1;
dfs(1);
for(int i = 1; i <= m; ++i) y[m - i + 1] = f[1][i];
printf("%d\n",Lagrange(d));
}
[集训队互测 2012] calc
经典题
\(\text{DP}\)还是很容易,首先由于互不相等,先转化成\(a_i\)有序,然后设\(f_{i,j}\)表示已经填了\(i\)个数,值域为\([1,j]\),转移方程就是
\]
按照上面的方法,设\(g_i\)为关于\(j\)的多项式\(f_{i,j}\)的次数,那么有
\]
然后\(f_{n,i}\)的次数就是\(2n\),求\(2n+1\)个点就能把答案插出来了
点我看代码☆ ̄(>。☆)
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const int N = 510;
int k, n, m;
LL P, y[N << 1], f[N][N << 1];
LL fpow(LL x, int pnt = P - 2) {
LL res = 1;
for(; pnt; pnt >>= 1, x = x * x % P) if(pnt & 1) res = res * x % P;
return res;
}
LL Lagrange(int x) {
if(1 <= x && x <= m) return y[x];
LL res = 0;
for(int i = 1; i <= m; ++i) {
LL p = y[i], q = 1;
for(int j = 1; j <= m; ++j)
if(j != i) p = p * (k - j) % P, q = q * (i - j) % P;
if(p < 0) p += P; if(q < 0) q += P;
res = (res + p * fpow(q)) % P;
}
return res;
}
int main() {
read(k), read(n), read(P), m = (n << 1) + 1;
LL fac = 1; for(int i = 1; i <= n; ++i) fac = fac * i % P;
for(int i = 0; i <= m; ++i) f[0][i] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
f[i][j] = (f[i - 1][j - 1] * j + f[i][j - 1]) % P;
for(int i = 1; i <= m; ++i) y[i] = f[n][i];
printf("%d\n",fac * Lagrange(k) % P);
}
总结
拉格朗日插值优化\(\text{DP}\)是一种优化思路,在值域比较大,容易求点值的时候可以考虑,上面给出的例子比较简单,需要在遇到具体问题时具体考虑。
最新文章
- 基于Caffe的DeepID2实现(中)
- 不一样的dynamic解析json 万能方法
- kettle参数、变量详细讲解[转]
- ECMAScript数据类型
- [HNOI2010]BOUNCE 弹飞绵羊
- Groupon面经:Find paths in a binary tree summing to a target value
- docker container link
- 数据库开发 MySQL
- PHP图片裁剪函数(图像不变形)
- Spring装配Bean之组件扫描和自动装配
- OpenTK教程-0序言
- 深入理解 GIL:如何写出高性能及线程安全的 Python 代码
- leetcode — merge-sorted-array
- laravel学习笔记二
- jQuery常见用法
- STL——算法简介
- Eclipse Indigo 3.7.0 安装GIT插件
- 是否含有RTTI(运行时类型信息)是动态语言与静态语言的主要区别
- 使用IPMI控制/监控Linux服务器
- 【linux】文件目录说明
热门文章
- 二手车价格预测 | 构建AI模型并部署Web应用 ⛵
- C 语言 时间函数使用技巧(汇总)
- 自己做一个RTOS
- LuoguP3128 [USACO15DEC]最大流Max Flow (树上差分)
- python包合集-shutil
- 若依3.6.0使用Mybatis-plus分页失效以及完美替换Pagehelper
- 【NOI P模拟赛】校门外歪脖树上的鸽子(树链剖分)
- HDU2065 “红色病毒”问题 (指数型母函数经典板题)
- 【JAVA】学习路径36-写到硬盘FileOutputStream Write的三种方法
- 一文快速上手 Nacos 注册中心+配置中心!