当前位置:网站首页>[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;
}
边栏推荐
- leetcode刷题 (5.29) 哈希表
- 使用 BR 恢复 S3 兼容存储上的备份数据
- On why we should program for all
- Use dumping to back up tidb cluster data to S3 compatible storage
- NFT smart contract release, blind box, public offering technology practice -- contract
- Summary of MySQL index failure scenarios
- hcip--mpls
- 2. File operation - write
- 你想知道的ArrayList知识都在这
- Image fusion -- challenges, opportunities and Countermeasures
猜你喜欢
A Closer Look at How Fine-tuning Changes BERT
08- [istio] istio gateway, virtual service and the relationship between them
Golang DNS 随便写写
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
Easy to use tcp-udp_ Debug tool download and use
Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
面向个性化需求的在线云数据库混合调优系统 | SIGMOD 2022入选论文解读
Ruffian Heng embedded bimonthly, issue 49
化不掉的钟薛高,逃不出网红产品的生命周期
【T31ZL智能视频应用处理器资料】
随机推荐
Easy to use tcp-udp_ Debug tool download and use
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Database basic commands
[research materials] 2021 China online high growth white paper - Download attached
Analysis of pointer and array written test questions
On the day of resignation, jd.com deleted the database and ran away, and the programmer was sentenced
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
Golang DNS write casually
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
Restore backup data on S3 compatible storage with br
Convolution, pooling, activation function, initialization, normalization, regularization, learning rate - Summary of deep learning foundation
使用 TiUP 升级 TiDB
The State Economic Information Center "APEC industry +" Western Silicon Valley will invest 2trillion yuan in Chengdu Chongqing economic circle, which will surpass the observation of Shanghai | stable
指针进阶---指针数组,数组指针
ESP系列引脚说明图汇总
Yyds dry goods inventory three JS source code interpretation eventdispatcher
08- [istio] istio gateway, virtual service and the relationship between them
Migrate data from a tidb cluster to another tidb cluster
你想知道的ArrayList知识都在这
Summary of MySQL index failure scenarios