最近学到的数学知识有一点多，需要整理整理
\(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 个球在剩下的集合中随意放置。