当前位置:网站首页>[2022 Guangdong saim] Lagrange interpolation (multivariate function extreme value divide and conquer NTT)
[2022 Guangdong saim] Lagrange interpolation (multivariate function extreme value divide and conquer NTT)
2022-07-06 08:19:00 【Messy wind】
The question
Seeking satisfaction ∑ i = 1 k x i 2 a i 2 = 1 \sum\limits_{i = 1} ^ {k}\dfrac{x_i ^ 2}{a_i ^ 2} = 1 i=1∑kai2xi2=1 Under the condition of , From the length to m m m Array of b b b Middle selection k k k It's made up of numbers a 1 , a 2 , ⋯ , a k a_1,a_2,\cdots,a_k a1,a2,⋯,ak, ∏ i = 1 k x i \prod\limits_{i = 1} ^{k} x_i i=1∏kxi The expectation of the maximum value of , k k k For the even .
( 1 ≤ k ≤ m ≤ 1 0 5 , 0 < b i < 1 0 9 ) (1 \le k \le m \le 10 ^ 5, 0 < b_i < 10 ^ 9) (1≤k≤m≤105,0<bi<109)
analysis :
First, the Lagrange multiplier method of conditional extremum of multivariate functions in advanced mathematics is used to solve the maximum value , set up
L ( x 1 , x 2 , ⋯ , x k , λ ) = ∏ i = 1 k x i + λ ( ∑ i = 1 k x i 2 a i 2 − 1 ) L(x_1,x_2,\cdots,x_k, \lambda) = \prod_{i = 1} ^{k} x_i + \lambda(\sum\limits_{i = 1} ^ {k}\dfrac{x_i ^ 2}{a_i ^ 2} - 1) L(x1,x2,⋯,xk,λ)=i=1∏kxi+λ(i=1∑kai2xi2−1)
Find the partial derivative of each variable , Let the partial derivative be 0 0 0 have to
∂ L ∂ x 1 = ∏ i = 1 k x i x 1 + 2 λ x 1 a 1 2 = 0 ∂ L ∂ x 2 = ∏ i = 1 k x i x 2 + 2 λ x 2 a 2 2 = 0 ⋯ ∂ L ∂ x k = ∏ i = 1 k x i x k + 2 λ x k a k 2 = 0 ∂ L ∂ λ = ∑ i = 1 k x i 2 a i 2 − 1 = 0 \frac{\partial L}{\partial x_1} = \frac{\prod\limits_{i = 1} ^{k} x_i}{x_1} + \frac{2\lambda x_1}{a_1 ^ 2} = 0 \\ \frac{\partial L}{\partial x_2} = \frac{\prod\limits_{i = 1} ^{k} x_i}{x_2} + \frac{2\lambda x_2}{a_2 ^ 2} = 0 \\ \cdots \\ \frac{\partial L}{\partial x_k} = \frac{\prod\limits_{i = 1} ^{k} x_i}{x_k} + \frac{2\lambda x_k}{a_k ^ 2} = 0 \\ \frac{\partial L}{\partial \lambda} = \sum_{i = 1} ^ {k}\dfrac{x_i ^ 2}{a_i ^ 2} - 1 = 0 ∂x1∂L=x1i=1∏kxi+a122λx1=0∂x2∂L=x2i=1∏kxi+a222λx2=0⋯∂xk∂L=xki=1∏kxi+ak22λxk=0∂λ∂L=i=1∑kai2xi2−1=0
Then simplify it a little , about 1 ≤ i ≤ k 1 \le i \le k 1≤i≤k There are
∏ i = 1 k x i = − 2 λ x i 2 a i 2 \prod_{i = 1} ^ {k}x_i = \frac{-2\lambda x_i ^ 2}{a_i ^ 2} i=1∏kxi=ai2−2λxi2
Through any two formulas 1 ≤ i , j ≤ k 1 \le i, j \le k 1≤i,j≤k Simultaneous elimination λ \lambda λ
a i 2 ∏ i = 1 k x i − 2 x i 2 = a j 2 ∏ i = 1 k x i − 2 x j 2 \frac{a_i ^ 2\prod\limits_{i = 1} ^ {k}x_i}{-2x_i ^ 2} = \frac{a_j ^ 2\prod\limits_{i = 1} ^ {k}x_i}{-2x_j ^ 2} −2xi2ai2i=1∏kxi=−2xj2aj2i=1∏kxi
Simplify to
x i a i = x j a j \frac{x_i}{a_i} = \frac{x_j}{a_j} aixi=ajxj
So if and only if x 1 a 1 = x 2 a 2 = ⋯ = x k a k \dfrac{x_1}{a_1} = \dfrac{x_2}{a_2}=\cdots=\dfrac{x_k}{a_k} a1x1=a2x2=⋯=akxk Maximum value when , And ∑ i = 1 k x i 2 a i 2 = 1 \sum\limits_{i = 1} ^ {k}\dfrac{x_i ^ 2}{a_i ^ 2} = 1 i=1∑kai2xi2=1, So for any 1 ≤ i ≤ k 1 \le i \le k 1≤i≤k There are x i a i = ± 1 k \dfrac{x_i}{a_i} = \pm \sqrt{\dfrac{1}{k}} aixi=±k1, that ∏ i = 1 k x i = k − k 2 ∏ i = 1 k a i \prod\limits_{i = 1} ^{k} x_i = k ^ {- \frac{k}{2}}\prod\limits_{i = 1} ^ {k} a_i i=1∏kxi=k−2ki=1∏kai, because k k k For the even , So it must be positive , And k 2 \dfrac{k}{2} 2k It must be an integer .
Seek from b b b Select... From the array k k k Sum of all products of numbers , Consider constructing a generating function
F ( x ) = ∏ i = 1 k ( 1 + b i x ) F(x) = \prod_{i = 1} ^ {k} (1 + b_ix) F(x)=i=1∏k(1+bix)
that [ x k ] F ( x ) [x ^ k]F(x) [xk]F(x) Is to choose k k k Sum of all products of numbers , All in all ( m k ) \dbinom{m}{k} (km) Seed selection , So the expectation is
k − k 2 × [ x k ] F ( x ) ( m k ) k ^ {-\frac{k}{2}} \times \frac{[x ^ k]F(x)}{\dbinom{m}{k}} k−2k×(km)[xk]F(x)
F ( x ) F(x) F(x) Divide and conquer available NTT \text{NTT} NTT Calculation , Total time complexity O ( n log 2 n ) O(n\log ^ 2n) O(nlog2n)
Code :
#include <bits/stdc++.h>
#define int long long
#define poly vector<int>
#define len(x) ((int)x.size())
using namespace std;
const int N = 3e5 + 5, G = 3, Ginv = 332748118, mod = 998244353;
int rev[N], lim;
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void polyinit(int n) {
for (lim = 1; lim < n; lim <<= 1);
for (int i = 0; i < lim; i ++) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? lim >> 1 : 0);
}
void NTT(poly &f, int op) {
for (int i = 0; i < lim; i ++) {
if (i < rev[i]) swap(f[i], f[rev[i]]);
}
for (int mid = 1; mid < lim; mid <<= 1) {
int Gn = qmi(op == 1 ? G : Ginv, (mod - 1) / (mid << 1));
for (int i = 0; i < lim; i += mid * 2) {
for (int j = 0, G0 = 1; j < mid; j ++, G0 = G0 * Gn % mod) {
int x = f[i + j], y = G0 * f[i + j + mid] % mod;
f[i + j] = (x + y) % mod, f[i + j + mid] = (x - y + mod) % mod;
}
}
}
if (op == -1) {
int inv = qmi(lim, mod - 2);
for (int i = 0; i < lim; i ++) f[i] = f[i] * inv % mod;
}
}
poly operator * (poly f, poly g) {
int n = len(f) + len(g) - 1;
polyinit(n), f.resize(lim), g.resize(lim);
NTT(f, 1), NTT(g, 1);
for (int i = 0; i < lim; i ++) f[i] = f[i] * g[i] % mod;
NTT(f, -1), f.resize(n);
return f;
}
vector<int> fact, infact;
void init(int n) {
fact.resize(n + 1), infact.resize(n + 1);
fact[0] = infact[0] = 1;
for (int i = 1; i <= n; i ++) {
fact[i] = fact[i - 1] * i % mod;
}
infact[n] = qmi(fact[n], mod - 2);
for (int i = n; i; i --) {
infact[i - 1] = infact[i] * i % mod;
}
}
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0ll;
return fact[n] * infact[n - m] % mod * infact[m] % mod;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
init(1e5);
int n, k;
cin >> n >> k;
vector<int> b(n + 1);
vector<poly> f(n + 1, poly(2));
for (int i = 1; i <= n; i ++) {
cin >> b[i];
f[i][0] = 1, f[i][1] = b[i];
}
function<poly(int, int)> dc = [&](int l, int r) {
if (l == r) return f[l];
int mid = l + r >> 1;
return dc(l, mid) * dc(mid + 1, r);
};
poly ans = dc(1, n);
int res = 1;
cout << qmi(qmi(k, k / 2), mod - 2) * ans[k] % mod * qmi(C(n, k), mod - 2) % mod << endl;
}
边栏推荐
- 化不掉的钟薛高,逃不出网红产品的生命周期
- Flash return file download
- LDAP应用篇(4)Jenkins接入
- Database basic commands
- National economic information center "APEC industry +": economic data released at the night of the Spring Festival | observation of stable strategy industry fund
- 使用 BR 恢复 S3 兼容存储上的备份数据
- Sanzi chess (C language)
- A Closer Look at How Fine-tuning Changes BERT
- 面向个性化需求的在线云数据库混合调优系统 | SIGMOD 2022入选论文解读
- Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
猜你喜欢
Asia Pacific Financial Media | art cube of "designer universe": Guangzhou community designers achieve "great improvement" in urban quality | observation of stable strategy industry fund
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
[research materials] 2021 Research Report on China's smart medical industry - Download attached
[untitled]
07- [istio] istio destinationrule (purpose rule)
National economic information center "APEC industry +": economic data released at the night of the Spring Festival | observation of stable strategy industry fund
Summary of phased use of sonic one-stop open source distributed cluster cloud real machine test platform
Configuring OSPF load sharing for Huawei devices
你想知道的ArrayList知识都在这
指针进阶---指针数组,数组指针
随机推荐
matplotlib. Widgets are easy to use
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
Understanding of law of large numbers and central limit theorem
Use Alibaba icon in uniapp
Database basic commands
1204 character deletion operation (2)
指针和数组笔试题解析
使用 TiUP 升级 TiDB
C语言自定义类型:结构体
Grayscale upgrade tidb operator
Huawei cloud OBS file upload and download tool class
leetcode刷题 (5.29) 哈希表
在 uniapp 中使用阿里图标
Permutation and combination function
Pyqt5 development tips - obtain Manhattan distance between coordinates
Remote storage access authorization
Let the bullets fly for a while
[secretly kill little partner pytorch20 days -day01- example of structured data modeling process]
Common functions for PHP to process strings
Data governance: metadata management