Excrt 与拉格朗日乘子法

最近学到的数学知识有一点多,需要整理整理

\(Excrt\)

应该是NOIp的基础内容,但我现在还没有掌握扎实,整理下来

给定n个同余方程

\(\begin{cases}x \equiv r_1 \ \ mod \ \ m_1\\x \equiv r_2 \ \ mod \ \ m_2\\ \vdots \\x\equiv r_n \ \ mod \ \ m_n \end{cases}\)

假设我们解出了第一个方程,设其为ans,我们知道第一个方程通解为\(x = ans + k \times m_1 , k \in \mathbb{Z}\)

那我们现在的目标就是求第一个方程与第二个方程同时满足的x

考虑带入第一个方程的通解带入第二个方程

\(ans+k\times m_ 1\equiv r_2 \pmod{m_2}\)

移项可得

\(k\times m_1\equiv r_2 +ans \pmod{m_2}\)

问题转化为求解

\[k\times m_1 + y \times m_2 = r_2 - ans \]

这样算出来的\(k = c + \frac{m_2}{\gcd(m_1,m_2)}\times t,t\in\mathbb{Z}\)

将k带入原方程 \(ans' = ans + m_1 \times k\)

连个方程合并后的模数\(M = \operatorname{lcm}(m_1,m_2)\)

于是我可以将该方程与下一个方程继续合并。

若求解的过程中解出的\(\gcd(m_1,m_2)\)不能整除\(r_2 -ans\)则方程无解

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1ll<<30

const int p=1e5 + 5;

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}
int n;
int ai[p] , bi[p];

inline int mul(int a,int b,int mod)
{
	int res = 0;
	while(b)
	{
		if(b&1) res = (res + a) % mod;
		a = a + a;
		a%=mod;
		b>>=1;
	}
	return res;
}

inline int gcd(int a,int b)
{
	if(b == 0) return a;
	else return gcd(b,a%b);
}

inline int exgcd(int a,int b,int &x,int &y)
{
	if(b == 0)
	{
		x = 1 , y = 0;
		return a;
	}
	int g = exgcd(b,a%b,x,y);
	int t = x;
	x = y , y = (t - (a/b) * y);
	return g;
}

inline void excrt()
{
	int ans = ai[1];
	int M  = bi[1];
	int x,y;
	for(int i=2;i<=n;i++)
	{
		int b = ((ai[i] - ans)%bi[i] + bi[i]) %bi[i];
		int g = exgcd(M,bi[i] , x, y);//这里应该判一下无解
		x = mul(x , b/g , bi[i]);
		ans += M * x;
		M *= bi[i] / g;
		ans = (ans + M ) % M;
	}
	cout<<(ans + M)%M;
}
signed  main()
{
	read(n);
	
	for(int i=1;i<=n;i++)
	{
		read(bi[i]);
		read(ai[i]);	
	}	 
	excrt();
	return 0 ;
 }

拉格朗日乘子法

偶然发现的黑科技,能够解决多元函数求极值问题

在数学和OI方面都是有力的工具

内容

给定一个二元函数\(f(x,y)\)和限制条件\(\phi(x,y)\),要求在满足\(\phi(x,y)=0\)的情况下,求\(f(x,y)的最值。\)

设一个三元函数\(F(x,y,\lambda) =f(x,y)+\lambda\times\phi(x,y)\)

对F求偏导,令每一个偏导数等于0,联立求解方程即可

解出未知数再带回原式即可

拉格朗日插值

构造函数

\[L_n(x) = \sum_{i=0}^{n}y_iℓ_i \]

\[ℓ_i(x) = \prod_{i\neq j}^{n} \frac{x-x_j}{x_i-x_j} \]

易知,对与已经给出的\(n+1\)个点对\((x_i,y_i)\),每个\(x_i\)在\(L_n(x)\)中唯一对应一个\(y_i\)

然后\(O(n^2)\)的时间内可以求出\(f(x)\)的值

当然可以更快

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1ll<<30

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

const int mod = 998244353;
const int np = 5e3 + 10;

int x[np] , y[np];
int n;

inline int power(int a,int b)
{
	int res =1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		a = a * a;
		a%=mod;
		b>>=1; 
	}
	return res;
}

inline int inv(int x)
{
	return power(x , mod - 2);
}

inline void lagrange(int kth)
{
	int ans =0 ;
	for(int i=1;i<=n;i++)
	{
		int ell_up = y[i];//加在这
		int ell_down =1 ;
		for(int j=1;j<=n;j++)
		{
			if(i == j) continue;
			
			ell_up = ell_up * (kth - x[j]) % mod;
			ell_down = ell_down * (x[i] - x[j]) % mod;				
			
		}
		ans = (ans + (ell_up * inv(ell_down) % mod)) % mod;//把y[i]加在这会乘爆,我就因为这个wa了一万次
		ans %=mod;
	}
	ans = (ans + mod) % mod;
	printf("%lld",ans);
}

signed  main()
{
	int k;
	read(n);read(k);
	for(int i=1;i<=n;i++)
	{
		read(x[i]);
		read(y[i]);
	}
	lagrange(k);
 }

很明显\(O(n^2)\)太慢了,但是考虑到NOIp不会专门考察多项式。大概只会出在一些阴间数学题里面,需要暴力求出前几项然后插值第 \(k\) 项。所以连续型插值对我们来说是必需掌握的

考虑对拉格朗日基函数进行优化

\[ℓ_i(x) = \prod_{i\neq j}^{n} \frac{x-x_j}{x_i-x_j} \]

上式等价于

\[ℓ_i(x) = \prod_{i\neq j}^{n} \frac{x-j}{i-j} \]

直接上结论

\[pre(i)=pre(i-1)\times(x-i) \]

\[suf(i)=suf(i+1)\times(x-i) \]

\[ℓ_i(x) = \frac{pre(i-1)\times suf(i+1)}{(i-1)!\times(-1)^{n-i}\times(n-i)!} \]

额,我们就可以插值出 \(f(k)\)

CF622F The Sum of the k-th Powers

证明是\(k+2\)次多项式就略过了(反正是给我自己看,而且我会

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1ll<<30

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

const int mod = 1e9 + 7;
const int np = 1e6 + 5;

inline int power(int a,int b)
{
	int res =1 ;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		a = a * a;
		a%=mod;
		b >>= 1;
	}
	return res;
}

int suf[np] , pre[np] , fac[np];

inline int inv(int x)
{
	return power(x , mod -2 );
}

signed  main()
{
	
	int n;
	int k;
	read(n);
	read(k);
	
	pre[0] = suf[k + 3] = fac[0] = 1;
	for(int i=1;i<=k + 2;i++) pre[i] = pre[i - 1] * (n - i) % mod;
	for(int i=k + 2;i>=1;i--) suf[i] = suf[i + 1] * (n - i) % mod;
	for(int i=1;i<=k + 2;i++) fac[i] = fac[i-1] * i % mod;
	int ans =0 , y= 0;
	for(int i=1;i<=k + 2;i++)
	{
		y += power(i,k);
		y%=mod;
		int ell_up = pre[i - 1] * suf[i + 1] % mod;
		int ell_down = fac[i-1]  * fac[k + 2- i]%mod * (((k+ 2 - i) & 1)?-1:1)% mod;
		(ans += (ell_up * y % mod * inv(ell_down) % mod)) %= mod;
	}

	printf("%lld",(ans + mod)%mod);
 }


第二类斯特林数

\(\begin{Bmatrix}n\\m\end{Bmatrix}\)为第二类斯特林数,组合意义是:n个元素放到m个集合中的方案数

递推公式:
\(\begin{Bmatrix}n\\m\end{Bmatrix} =m\begin{Bmatrix}n-1\\m\end{Bmatrix} +\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\)

组合意义易证

通项公式:

\[\begin{Bmatrix}n\\m\end{Bmatrix} =\frac{1}{m!}\sum_{i=0}^{m}\dbinom{m}{i}(m-i)^n \]

考虑容斥

m 个集合中有 i 个空置不用, n 个球在剩下的集合中随意放置。

上一篇:Bootstrap 工具类


下一篇:模拟62 考试总结