雅礼学习10.2
上午考试解题报告
各题状况（爆零）
T1
想了10多分钟，暴力只有一个极大复杂度的想法，显然不可过，但还是写了，然后就全TLE也是。。。意料之中
T2
暴力很好写，但是错误理解了Tim给的部分分的意思：先给了一个(a_ile 10^9)，然后部分分里面没有提到(a_i)的情况，我就忽略了(a_i)的大小对答案统计的影响。。。
换句话说，我当时要是写了离散化，就是(43)分到手。
T3
题目要求的输出可以分成三个问题，第一个问题正确 的话可以得到这个点的(25%)的分数，前两个问题正确的话可以得到该点(50%)的分数，三个问题全对可以获得全部的分数
但是。。。因为出题人的(SPJ)写的有点问题，即使只求了第一个问题，后面的两个问题也需要输出点什么来满足(SPJ)的判断方式。
出题人在给的(PDF)里面点到了这个注意事项，但是是在整个(PDF)的最后一页最后一行。。。
各题题目与考场代码
T1
/*
* 考虑把所有的建筑先都变成一样高
* 然后往回推，暴力统计所有的情况
*/
#include <cstdio>
#include <algorithm>
inline int read()
{
int n=0,w=1;register char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
return n*w;
}
inline int min(int x,int y)
{return x<y?x:y;}
inline int max(int x,int y)
{return x>y?x:y;}
inline int abs(int x)
{return x<0?-x:x;}
const int N=1000001;
int n,c,ans=2147483647,h[N],a[N];
void dfs()
{
int emp=(a[1]-h[1])*(a[1]-h[1]);
for(int i=2;i<=n;++i)
{
emp+=abs(a[i]-a[i-1])*c;
emp+=(a[i]-h[i])*(a[i]-h[i]);
}
ans=min(ans,emp);
for(int i=1;i<=n;++i)
if(a[i]!=h[i])
{
--a[i];
dfs();
++a[i];
}
}
int main()
{
freopen("construct.in","r",stdin);
freopen("construct.out","w",stdout);
int maxn=0;
n=read(),c=read();
for(int i=1;i<=n;++i)
maxn=max(maxn,h[i]=read());
for(int i=1;i<=n;++i)
a[i]=maxn;
dfs();
printf("%d",ans);
fclose(stdin);fclose(stdout);
return 0;
}
T2
/*
* 23分应该可以模拟搞过去
* 蔬菜种类数不超过200的部分应该可以前缀和搞过去？
*/
#include <cstdio>
inline int read()
{
int n=0,w=1;register char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
return n*w;
}
inline int max(int x,int y)
{return x>y?x:y;}
const int N=201;
int r,c,q,ans,maxn,map[N][N],newmap[N][N][N];
inline void work()
{
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
{
for(int x=1;x<N;++x)
newmap[x][i][j]=newmap[x][i-1][j]+newmap[x][i][j-1]-newmap[x][i-1][j-1];
++newmap[map[i][j]][i][j];
}
int x,y,xx,yy,ans,emp;
while(q--)
{
ans=0;
x=read(),y=read(),xx=read(),yy=read();
for(int i=1;i<N;++i)
{
emp=newmap[i][xx][yy]-newmap[i][xx][y-1]-newmap[i][x-1][yy]+newmap[i][x-1][y-1];
ans+=emp*emp;
}
printf("%d
",ans);
}
}
inline void solve()
{
int x,y,xx,yy,emp;
while(q--)
{
ans=0;
x=read(),y=read(),xx=read(),yy=read();
for(int k=1;k<=maxn;++k)
{
emp=0;
for(int i=x;i<=xx;++i)
for(int j=y;j<=yy;++j)
if(map[i][j]==k)
++emp;
ans+=emp*emp;
}
printf("%d
",ans);
}
}
int main()
{
freopen("vegetable.in","r",stdin);
freopen("vegetable.out","w",stdout);
r=read(),c=read(),q=read();
for(int x,i=1;i<=r;++i)
for(int j=1;j<=c;++j)
{
map[i][j]=read();
maxn=max(maxn,map[i][j]);
}
if(q<=1000)
solve();
else
if(maxn<=200)
work();
fclose(stdin);fclose(stdout);
return 0;
}
T3
/*
* 第二个问题不会。。。
* 只能拿25%*20了
*/
#include <cstring>
#include <cstdio>
inline int read()
{
int n=0,w=1;register char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();
return n*w;
}
inline int min(int x,int y)
{return x<y?x:y;}
inline int max(int x,int y)
{return x>y?x:y;}
/*
const int N=300001;
struct Edge{
int v,nxt;
}edge[N<<1];
int n,tot,maxn,ans,head[N];//,ansedge[N],top,anspoint[4];
bool mark[N<<1];
inline void add(int u,int v)
{edge[++tot]=(Edge){v,head[u]};head[u]=tot;}
void dfs(int now,int step,int fa)
{
maxn=max(maxn,step);
for(int v,i=head[now];i;i=edge[i].nxt)
if((v=edge[i].v)!=fa && !mark[i])
dfs(v,step+1,now);
}
*/
const int N=3001;
int n,maxn,ans=2147483647;
bool map[N][N],vis[N];
void dfs(int now,int step,int fa)
{
vis[now]=true;
maxn=max(maxn,step);
for(int i=1;i<=n;++i)
if(map[now][i] && !vis[i])
dfs(i,step+1,now);
}
int main()
{
freopen("league1.in","r",stdin);
// freopen("league.out","w",stdout);
n=read();
for(int u,v,i=1;i<n;++i)
{
u=read(),v=read();
map[u][v]=map[v][u]=true;
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
if(!map[i][j])continue;
map[i][j]=map[j][i]=false;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
if(map[i][j])continue;
map[i][j]=map[j][i]=true;
maxn=0;
dfs(1,0,0);
for(int i=2;i<=n;++i)
if(!vis[i])
goto E;
for(int i=2;i<=n;++i)
{
dfs(i,0,0);
memset(vis,false,sizeof vis);
}
ans=min(ans,maxn);
E: map[i][j]=map[j][i]=false;
}
map[i][j]=map[j][i]=true;
}
/* for(int u,v,i=1;i<n;++i)
{
u=read(),v=read();
add(u,v),add(v,u);
}
for(int i=1;i<=tot;++i)
{
mark[i]=mark[i+1]=true;
for(int j=1;j<=n;++j)
for(int k=j+1;k<=n;++k)
{
add(j,k),
*/
/* for(int i=1;i<=tot;++++i)
{
mark[i]=true;
for(int j=1;j<=n;++j)
for(int k=j+1;k<=n;++k)
{
add(j,k),add(k,j);
maxn=0;
for(int l=1;l<=n;++l)
dfs(l,0,0);
if(ans>maxn)
{
ans=maxn;
ansedge[top=1]=i;
anspoint[0]=edge[i].v;
anspoint[1]=edge[i^1].v;
anspoint[2]=j;
anspoint[3]=k;
}
head[k]=edge[tot--].nxt;
head[j]=edge[tot--].nxt;
}
mark[i]=false;
}*/
printf("%d",ans);
fclose(stdin);fclose(stdout);
return 0;
}
正解思路及代码
T1
记(f_i)表示考虑前(i)个建筑，并且第(i)个建筑的高度不变的答案，每次转移的时候枚举上一个不变的建筑编号，中间的一段一定变成相同的高度，并且高度小于等于两端的高度
假设从(f_j)转移并且中间高度是(t)，那么(f_i=sum_{k=j+1}^{i-1}(t-h_k)^2+c(h[j]+h[i]-2t))
这样中间的高度可以(O(1))求二次函数的对称轴
考虑优化转移，因为中间的高度小于两端，所以最多有(h_jgt h_i)的(j)能够转移，可以维护关于高度的单调栈，那么有效的转移次数就是(O(N))
#include <bits/stdc++.h>
using std::pair;
using std::vector;
using std::string;
typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
const int oo = 0x3f3f3f3f;
string procStatus() {
std::ifstream t("/proc/self/status");
return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template <typename T> T read(T& x) {
int f = 1; x = 0;
char ch = getchar();
for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x *= f;
}
const int N = 1000000;
int n, C;
int h[N + 5];
ll s[2][N + 5], dp[N + 5];
ll solve(int x, int y, int mx) {
ll a = y - x - 1;
ll b = -2 * (s[0][y-1] - s[0][x]) - (x != 0) * C - (y != n+1) * C;
ll c = s[1][y-1] - s[1][x] + 1ll * (x != 0) * h[x] * C + 1ll * (y != n+1) * h[y] * C;
ll t;
t = (ll) std::round(-1. * b / 2 / a);
chkmax<ll>(t, mx);
if(x != 0) chkmin(t, (ll) h[x]);
if(y <= n) chkmin(t, (ll) h[y]);
return a * t * t + b * t + c;
}
int main() {
freopen("construct.in", "r", stdin);
freopen("construct.out", "w", stdout);
read(n), read(C);
for(int i = 1; i <= n; ++i) {
read(h[i]);
s[0][i] = s[0][i-1] + h[i];
s[1][i] = s[1][i-1] + 1ll * h[i] * h[i];
}
static int stk[N + 5], top;
h[0] = h[n + 1] = oo;
stk[top ++] = 0;
for(int i = 1; i <= n+1; ++i) {
dp[i] = dp[i-1] + ((i == 1 || i == n+1) ? 0 : 1ll * C * std::abs(h[i] - h[i-1]));
while(top > 0 && h[stk[top-1]] <= h[i]) {
if(top > 1)
chkmin(dp[i], dp[stk[top-2]] + solve(stk[top-2], i, h[stk[top-1]]));
-- top;
}
stk[top ++] = i;
}
printf("%lld
", dp[n+1]);
return 0;
}
T2
当蔬菜的出现次数比较多的时候可以对每种蔬菜维护二维前缀和并且根据定义计算答案
当蔬菜的出现次数比较少的时候考虑平方的转化，相当于计算有多少个点被询问区域包含，实际上等价于四维偏序
综合分析两种算法的复杂度并且选取合适的出现次数分界值(k)，最终复杂度为(O(frac{n^2}{k}(n^2+q)+(n^2k+q)log^3 n))，那么根据这个式子可知(k=sqrt{frac{n^2+q}{log^3 n}})的时候最优
#include <bits/stdc++.h>
using std::pair;
using std::vector;
using std::string;
typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
const int oo = 0x3f3f3f3f;
string procStatus() {
std::ifstream t("/proc/self/status");
return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template <typename T> T read(T& x) {
int f = 1; x = 0;
char ch = getchar();
for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x *= f;
}
const int K = 40;
const int N = 200;
const int Q = 100000;
int n, m, q;
struct BIT {
#define lowbit(x) (x & -x)
int c[N + 5][N + 5][N + 5];
void add(int x, int y, int z) {
for(int i = x; i <= m; i += lowbit(i))
for(int j = y; j <= n; j += lowbit(j))
for(int k = z; k <= m; k += lowbit(k)) ++ c[i][j][k];
}
int query(int x, int y, int z) {
int res = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
for(int k = z; k > 0; k -= lowbit(k)) res += c[i][j][k];
return res;
}
} bit;
struct query {
int x1, y1, x2, y2, id;
void input(int _id) {
id = _id;
read(x1), read(y1);
read(x2), read(y2);
}
bool operator < (const query& rhs) const {
return x1 > rhs.x1;
}
};
vector <int> d;
vector <query> mod;
vector <pii> p[Q + 5];
query que[Q + 5];
int ans[Q + 5], cnt[N*N + 5];
int a[N + 5][N + 5], b[N + 5][N + 5];
inline int pw2(int x) { return x * x; }
void calc(int col) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) b[i][j] = b[i][j-1] + (a[i][j] == col);
for(int j = 1; j <= m; ++j) b[i][j] = b[i][j] + b[i-1][j];
}
for(int i = 1; i <= q; ++i) {
int x1 = que[i].x1, y1 = que[i].y1;
int x2 = que[i].x2, y2 = que[i].y2;
ans[que[i].id] += pw2(b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] +
b[x1-1][y1-1]);
}
}
void input() {
read(n), read(m); read(q);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) d.pb(read(a[i][j]));
for(int i = 1; i <= q; ++i) que[i].input(i);
}
void solve() {
std::sort(d.begin(), d.end());
d.erase(std::unique(d.begin(), d.end()), d.end());
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
a[i][j] = std::lower_bound(d.begin(), d.end(),
a[i][j]) - d.begin();
++ cnt[a[i][j]];
p[a[i][j]].pb(mp(i, j));
}
for(int i = 0; i < (int) d.size(); ++i) {
if(cnt[i] >= K) {
calc(i);
} else {
for(auto x : p[i])
for(auto y : p[i]) {
query temp;
temp.x1 = x.fst, temp.y1 = x.snd;
temp.x2 = y.fst, temp.y2 = y.snd;
if(temp.x1 > temp.x2) std::swap(temp.x1, temp.x2);
if(temp.y1 > temp.y2) std::swap(temp.y1, temp.y2);
mod.pb(temp);
}
}
}
std::sort(que + 1, que + q + 1);
std::sort(mod.begin(), mod.end());
for(int i = 1, j = 0; i <= q; ++i) {
while(j < (int) mod.size() && mod[j].x1 >= que[i].x1) {
bit.add(m - mod[j].y1 + 1, mod[j].x2, mod[j].y2);
++ j;
}
ans[que[i].id] += bit.query(m - que[i].y1 + 1, que[i].x2, que[i].y2);
}
for(int i = 1; i <= q; ++i) printf("%d
", ans[i]);
}
int main() {
freopen("vegetable.in", "r", stdin);
freopen("vegetable.out", "w", stdout);
input();
solve();
return 0;
}
T3
显然危险程度就是树的直径，断开边之后会得到两个联通块，假设两个联通块的直径分别为(l_1,l_2)，根据直径的性质，连接两个联通块之后新的直径长度最小是(max{l_1,l_2,lceil frac{l_1}{2} ceil+lceilfrac{l_2}{2} ceil+1})
然后考虑维护，由于合并两个联通块之后新的直径的两个端点一定会在原来的直径端点的并中产生，可以处理每一个子树的直径端点，每次考虑(i)到(f_{a_i})的边时只需要分别求出两个块的直径端点即可，在每个点上维护子树前缀联通块和后缀联通块的直径端点即可快速合并
#include <bits/stdc++.h>
using std::pair;
using std::vector;
using std::string;
typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
template <typename T> bool chkmax(T& a, T b)
{ return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b)
{ return a > b ? a = b, 1 : 0; }
const int oo = 0x3f3f3f3f;
string procStatus() {
std::ifstream t("/proc/self/status");
return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template <typename T> T read(T& x) {
int f = 1; x = 0;
char ch = getchar();
for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x *= f;
}
const int N = 300000;
struct diameter { int x, y, d; };
int sz[N + 5];
int fa[N + 5][21], dep[N + 5];
int st[N + 5], to[(N << 1) + 5], nxt[(N << 1) + 5], e = 1;
inline void addedge(int u, int v) { to[++ e] = v; nxt[e] = st[u]; st[u] = e; }
int get_up(int x, int d) {
for(int i = 0; d > 0; ++i, d >>= 1)
if(d & 1) x = fa[x][i];
return x;
}
int get_lca(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
for(int i = 0, d = dep[x] - dep[y]; d > 0; ++i, d >>= 1)
if(d & 1) x = fa[x][i];
if(x == y) return x;
for(int i = 20; i >= 0; --i)
if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline int get_dis(int x, int y, int lca = 0) {
if(lca) return dep[x] + dep[y] - 2*dep[lca];
return dep[x] + dep[y] - 2*dep[get_lca(x, y)];
}
inline int get_mid(int x, int y) {
int r = get_lca(x, y), dis = get_dis(x, y) >> 1;
return (dep[x] - dep[r] >= dis) ? get_up(x, dis) : get_up(y, dis);
}
inline void merge(diameter& a, diameter b) {
int len = a.d, x = a.x, y = a.y;
if(chkmax(len, b.d)) a.x = b.x, a.y = b.y;
if(chkmax(len, get_dis(x, b.x))) a.x = x, a.y = b.x;
if(chkmax(len, get_dis(x, b.y))) a.x = x, a.y = b.y;
if(chkmax(len, get_dis(y, b.x))) a.x = y, a.y = b.x;
if(chkmax(len, get_dis(y, b.y))) a.x = y, a.y = b.y;
a.d = len;
}
diameter sub[N + 5];
void dfs(int u, int f = 0) {
fa[u][0] = f;
dep[u] = dep[f] + 1;
sub[u] = (diameter) { u, u, 0 };
for(int i = 1; i < 21; ++i) fa[u][i] = fa[fa[u][i-1]][i-1];
sz[u] = 1;
for(int i = st[u]; i; i = nxt[i]) {
int v = to[i];
if(v == f) continue;
dfs(v, u); sz[u] ++;
merge(sub[u], sub[v]);
}
}
int ans = oo;
int length[N + 5];
int sx, sy, tx0, tx1, ty0, ty1;
pair<diameter, int> *pre[N + 5];
void dfs1(int u, diameter lst, int f = 0) {
if(f > 0) {
int len = std::max(std::max(lst.d,
(lst.d + 1) / 2 + (sub[u].d + 1) / 2 + 1), sub[u].d);
if(chkmin(ans, length[u-1] = len)) {
sx = u, sy = f;
tx0 = lst.x, tx1 = lst.y;
ty0 = sub[u].x, ty1 = sub[u].y;
}
}
int c = 0;
pre[u] = new pair<diameter, int> [sz[u] + 5];
pre[u][c ++] = mp(lst, -1);
for(int i = st[u]; i; i = nxt[i]) {
int v = to[i];
if(v == f) continue;
diameter x = pre[u][c-1].fst;
merge(x, sub[v]); pre[u][c ++] = mp(x, v);
}
diameter suf = lst, temp;
merge(suf, (diameter) { u, u, 0 });
for(int i = c - 1; i > 0; --i) {
int v = pre[u][i].snd;
merge(temp = suf, pre[u][i-1].fst);
dfs1(v, temp, u); merge(suf, sub[v]);
}
}
int n;
int main() {
freopen("league.in", "r", stdin);
freopen("league.out", "w", stdout);
read(n);
for(int i = 1; i < n; ++i) {
static int u, v;
read(u), read(v);
addedge(u, v); addedge(v, u);
}
dfs(1);
dfs1(1, (diameter) { 1, 1, 0 });
vector<int> plan;
for(int i = 1; i < n; ++i) if(length[i] == ans) plan.pb(i);
printf("%d
", ans);
printf("%lu ", plan.size()); for(auto v : plan) printf("%d ", v);
printf("
%d %d %d %d
", sx, sy, get_mid(tx0, tx1), get_mid(ty0, ty1));
return 0;
}
下午讲课内容：OI中的数学方法
GCD
(gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1)
证明：
不妨假设(agt b)，那么一定有(a=b imes k+t(k,tin N_+))
那么(gcd(x^{bk+t}-1,x^b-1)=gcd(x^{bk} imes x^t-1,x^b-1)=gcd((x^b)^k imes x^t-1,x^b-1))
(gcd(fib_a,fib_b)=fit_{gcd(a,b)})
欧拉定理及其拓展
若有(gcd(a,p)=1)，那么(a^varphi(p)equiv 1pmod p)
一般情况：(a^tequiv a^{min(t,tmod varphi(p)+varphi(p))}pmod p)
同余方程
形如(xequiv a_ipmod {p_i})
由此拓展出中国剩余定理
中国剩余定理
若(p_i)两两互质，则存在通解
[P=prod_i p_i
]
[P_i=frac{P}{p_i}
]
[T_i=P_i^{-1}mod p_i
]
[xequivsum_i a_iT_iP_i
]
其拓展形式：
考虑合并两个方程：
[egin{aligned}
x &equiv a_1 pmod{p_1} \
x &equiv a_2 pmod{p_2} \
x &= a_1 + k_1p_1 = a_2 + k_2p_2 \
end{aligned}
]
令(t=gcd(p_1,p_2))，则有
[egin{aligned}
k_1frac{p_1}{t}&equiv frac{a_2 - a_1}{t} pmod{frac{p_2}{t}}\
k_1 &equiv frac{a_2 - a_1}{t} imes (frac{p_1}{t})^{-1} pmod{frac{p_2}{t}} \
x &equiv a_1 + p_1 left(frac{a_2 - a_1}{t} imes (frac{p_1}{t})^{-1} mod frac{p_2}{t}
ight) pmod{frac{p_1p_2}{t}}
end{aligned}
]
积性函数
令(n = p_1^{e_1}p_2^{e_2} cdots p_k^{e_k})：
- (epsilon(n) = [n = 1])
- (mathrm{Id}(n) = n)
- (varphi(n) = nprod_{i=1}^{k} (1 - frac{1}{p_i}))
- (mathrm{d}(n) = sum_{d|n} 1)
- (sigma(n) = sum_{d|n} d)
- (lambda(n) = (-1)^k)
Dirichlet卷积
[(f*g)(n) = sum_{d|n} f(d) g(frac{n}{d})
]
. . .
-
(mu * 1 = epsilon)
-
(mathrm{Id} = varphi * 1 Rightarrow varphi = mathrm{Id} * mu)
-
(mathrm{d} = 1 * 1 Rightarrow 1 = mu * mathrm{d})
-
(sigma = mathrm{Id} * 1 Rightarrow mathrm{Id} = mu * sigma Rightarrow sigma = varphi * mathrm{d})
-
(d(ij) = sum_{x|i}sum_{y|j} [gcd(x, y) = 1])
-
(sigma(ij) = sum_{x|i}sum_{y|j} [gcd(x, y) = 1] frac{iy}{x})
狄利克雷卷积满足交换律, 结合律, 两个积性函数的卷积也是积性的
组合数的计算
通过一个例题来讲解
计算:$${n choose m} mod p$$
-
(n, m le 5000)
-
(n, m le 10^6, p) 是质数
-
(n, m le 10^{18}, p le 10^6, p) 是质数
-
(n, m le 10^{18}, p le 10^6).
第一个部分分：暴力
第二个部分分：预处理阶乘然后算
第三个部分分：Lucas定理
第四个部分分：扩展Lucas定理
基本组合恒等式
[egin{aligned}
& sum_{i=0}^{n} {n choose i} = 2 ^ n \
& sum_{i=0}^{n} {i choose x} = {n+1 choose x+1} \
& sum_{i=0}^{n} {k+i choose i} = {k+n+1 choose n} \
& sum_{i=0}^{m} {m choose i} {n-m choose m-i} = {n choose m}
end{aligned}
]
第一类Stirling数
-
定义: (egin{bmatrix} n \ m end{bmatrix}) 表示将(n) 个物品分为 (m) 个无序非空环的方案数
-
递推式:$$egin{bmatrix} n m end{bmatrix} = egin{bmatrix} n-1 m-1 end{bmatrix} + (n-1)egin{bmatrix} n-1 m end{bmatrix}$$
-
生成函数:
[egin{aligned}
& x^{overline{n}} = sum_{i=0}^{n} egin{bmatrix} n \ i end{bmatrix} x^i \
& x^{underline{n}}= sum_{i=0}^{n} (-1)^{n-i} egin{bmatrix} n \ i end{bmatrix} x^i
end{aligned}
]
第二类Stirling数
-
定义: (n race m) 表示将 (n) 个物品分成 (m) 个无序非空集合的方案数
-
[{n race m} = {n-1 race m-1} + m{n-1 race m} ]
-
生成函数:
[egin{aligned}
& x^n = sum_{i=0}^{n} {n race i} x^{underline{i}} \
& m!{n race m} = sum_{i=0}^{m} (-1)^{m-i} {m choose i} i^n
end{aligned}
]
多项式的差分序列
定义 (Delta^{k} f(n)) 为 (f(n)) 的 (k) 阶差分序列, 并且:
[Delta^{k} f(n) =
egin{cases}
f(n), & mathrm{k = 0} \
Delta^{k-1} f(n+1) - Delta^{k-1} f(n), & mathrm{otherwise}
end{cases}
]
容易发现差分序列的具有线性性, 特别地, 多项式:
[f(x) = {0, 0, 0, cdots, 1} mid x in [0, n]
]
差分序列的第一列是 ({0, 0, 0, cdots, 1}) , 事实上这个多项式就是
[frac{1}{n!} prod_{i=0}^{n-1} (x - i) = {x choose n}
]
多项式插值
已知一个 (n) 次多项式的 (n+1) 个点值, 求这个多项式的系数表示
牛顿插值
求出多项式的 (n) 阶差分序列第一列 ({c_i}), 可以将多项式表示成:
[f(x) = sum_{i=0}^{n} c_i {x choose i}
]
拉格朗日插值
考虑构造一个经过所有给定点的多项式:
[egin{aligned}
g_i(x) = prod_{j=0, j
eq i}^{n} frac{x - x_j}{x_i - x_j} \
f(x) = sum_{i=0}^{n} y_ig_i(x)
end{aligned}
]
自然数幂和
求$$f_k(n) = sum_{i=0}^{n} i^k$$
解：
直接用第二类斯特林数展开:
[egin{aligned}
f_k(n) &= sum_{i=0}^{n} sum_{j=0}^{k} {k race j} i^{underline{j}} \
&= sum_{j=0}^{k} {k race j} j! sum_{i=0}^{n} {i choose j} \
&= sum_{j=0}^{k} {k race j} j! {n + 1 choose j + 1}
end{aligned}
]
或者用拉格朗日插值
通过上一个方法我们知道 (f_k(n)) 是一个关于 (n) 的 (k+1) 次多项式,
于是直接拉格朗日插值即可, 并且由于系数的特殊性质, 可以做到 (O(k))
另外：
Bernoulli数
定义 (B_i) 为伯努利数, 满足:
[sum_{i=0}^{m} B_i {m+1 choose i} = [m = 0]
]
那么有:
[f_k(n-1) = frac{1}{k+1} sum_{i=0}^{k} B_i n^{k + 1 - i} {k + 1 choose i}
]
容斥与反演
-
(mathrm{Min-Max}) 容斥:$$max(S) = sum_{T subseteq S, T eq varnothing} min(T) ^ {(-1) ^ {|T|-1}}$$
-
拓展形式:$$mathrm{lcm}(S) = prod_{T subseteq S, T eq varnothing} gcd(T) ^ {(-1) ^ {|T|-1}}$$
-
二项式反演：
[egin{aligned} f(n) &= sum_{i=0}^{n} {n choose i} g(i)\ Leftrightarrow g(n) &= sum_{i=0}^{n} (-1)^{n-i} {n choose i} f(i) end{aligned} ] -
Stirling反演：
[egin{aligned} f(n) &= sum_{i=0}^{n} {n race i} g(i) \ Leftrightarrow g(n) &= sum_{i=0}^{n} (-1)^{n-i} egin{bmatrix} n \ i end{bmatrix} f(i) end{aligned} ]
例题
BZOJ4833
已知：
[egin{aligned}
f(n) &=
egin{cases}
0, & extrm{n = 0} \
1, & extrm{n = 1} \
2f(n-1) + f(n-2), & extrm{otherwise} \
end{cases} \
g(n) &= mathrm{lcm}(f(1), f(2), cdots, f(n))
end{aligned}
]
求：$$sum_{i=1}^{n} g(i) imes i$$
(n le 10^6)
解：
首先有 (gcd(f(i), f(j)) = f(gcd(i, j)))
根据 (mathrm{Min-Max}) 容斥有:
[egin{aligned}
g(n) &= prod_{T subseteq S, T
eq varnothing} gcd(T)^{(-1)^{|T|+1}} \
&= prod_{T subseteq S, T
eq varnothing} f(gcd(T))^{(-1)^{|T|+1}}
end{aligned}
]
[egin{aligned}
f(n) &= prod_{d|n} h(d) \
Rightarrow g(n) &= prod_{d=1}^{n} h(d)^{sum_{T subseteq S, T
eq varnothing} [d mid gcd(T)] (-1)^{|T|+1}} \
&= prod_{d=1}^{n} h(d)
end{aligned}
]
Square
给出一个 (n imes m) 大小的矩形,
每个位置可以填上 ([1,c]) 中的任意一个数,
要求填好后任意两行互不等价且任意两列互不等价,
两行或两列等价当且仅当对应位置完全相同, 求方案数
(n, m le 5000)
解：
首先我们有一个很简单的方式使得列之间互不等价, 对于任意一列，总方案数是 (c^n), 那么使得列与列之间互不相同的方案数为 ((c^n)^{underline{m}})
接下来的问题只与行数有关,
定义 (g(n)) 表示 (n) 行不保证每行互不等价的方案数，(f(n)) 表示 (n) 行保证任意两行互不等价的方案数, 有：
[egin{aligned}
g(n) &= (c^n)^{underline{m}} \
&= sum_{i=0}^{n} {n race i} f(i) \
f(n) &= sum_{i=0}^{n} (-1)^{n-i} egin{bmatrix} n \ i end{bmatrix} g(i)
end{aligned}
]
Sequence
给出一个长度为 (n) 的序列 ({a_i}) 以及一个数 (p), 现在有 (m) 次操作，每次操作将 ([l, r]) 区间内的 (a_i) 变成 (c^{a_i}), 或者询问 ([l, r]) 之间所有 (a_i) 的和对 (p) 取模的结果
(n, m le 5 imes 10^4, p le 2^{14})
解：
对于修改操作可以利用拓展欧拉定理, 维护一个 (log(p)) 层的结构表示每一个 (a_i) 的值
由于经过只有最后的 (log(p)) 次操作是有效的，所以任意的两个相邻位置在经过 (log(p)) 次操作后会变得等价，在最外层维护一个 std::set 记录等价的区间, 然后用线段树做询问