In mathematics you don't understand things, you just get used to them.

动态 书籍 杂项 关于 友链

标签 maths 下的文章

大约是翻译了一下官方题解？

@Description@

对于一个整数序列 $P=(P_{1},\dots,P_{m})$，定义 $f(P)$ 为一个序列 $Q$ 满足：

  • $Q_{i}=P_{i}+P_{i+1}$，其中 $i\in[1,m)$；
  • $f(P)=(P_{1},Q_{1},\dots,P_{m-1},Q_{m-1},P_{m})$。

给出正整数 $a,b,N$，其中 $a,b\leqslant N$，令序列 $A=(a,b)$，令序列 $B$ 为一下操作的结果：

  • 做 $N$ 次令 $A=f(A)$.
  • 删除 $A$ 中大于 $B$ 的数。

求 $B_{l,\dots r}$。

@Solution@

◆ The Coefficient Sequence

构造最终的 $A$ 序列的过程是这样的：

$$ a,b \\ a,a+b,b \\ a,2a+b,a+b,a+2b,b \\ a,3a+b,2a+b,3a+2b,a+b,2a+3b,a+2b,a+3b,b \\ \dots $$

可以发现有对称性。此时我们先不关心 $a,b$ 以及 $N$ 的大小，反之，我们来观察其序列系数，也就是把每个元素看成 $xa+yb$，其系数的 $(x,y)$，上例的序列系数即

$$ (1,0),(0,1) \\ (1,0),(1,1),(0,1) \\ (1,0),(2,1),(1,1),(1,2),(0,1) \\ (1,0),(3,1),(2,1),(3,2),(1,1),(2,3),(1,2),(1,3),(0,1) \\ \dots $$

以下我们称其为 Coefficient Sequence。

◆ The properties of the Coefficient Sequence

现在我们来观察 Coefficient Sequence 的性质。

Observation 1：在 Coefficient Sequence 中相邻的两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，都有： $x_{S}y_{T}-x_{T}y_{S}=1$。

使用数学归纳法（induction）即证。

Observation 2：对于两个 两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，如果他们满足 $x_{S}y_{T}-x_{T}y_{S}=1$，那么它们在 Coefficient Sequence 中相邻，即 Observation 1 是充要条件。

不会证，大概意会一下吧。

Observation 3：对于一个二元组 $(x,y)$，如果 $\gcd(x,y)=1$，那么 $(x,y)$ 会出现在 Coefficient Sequence 中。

比较显然，以至于官方题解没有给出证明。

Observation 4：在任意时刻，所有在 Coefficient Sequence 中的 $(x,y)$ 总是呈从左到右的关于值 $\frac{y}{x}$ 递增（令 $\frac{x}{0}=\infty$）。

◆ The sequence $B$ in other words

现在描述序列 $B$ 变得更加容易，现在我们这样描述它：

对于所有二元组 $(x,y)$ 满足 $x,y,s.t.x,y\in\mathbb{N},\gcd(x,y)=1,ax+by\leqslant N$，我们对其按 $\frac{y}{x}$ 排序后形成一个二元组序列 $\{(x_{i},y_{i})\}$，则 $B_{i}=ax_{i}+by_{i}$。

◆ Computing $B_{n}$

现在我们来考虑原问题的简化版，我们来计算 $B_{n}$。让我们把这个描述成一个计数问题（通过二分 $\frac{y}{x}$）：

给定正整数 $a,b,N$，以及一个有理数 $c$（二分的值），求二元组 $(x,y)\neq(0,0)$ 的数量，其中 $(x,y)$ 满足

  • $ax+by\leqslant N$；
  • $\gcd(x,y)=1$；
  • $\frac{y}{x}\leqslant c$。

我们令 $F(N)$ 为以上问题的答案，同时令 $G(N)$ 为去掉 $\gcd(x,y)=1$ 限制的答案。$G(N)$ 的式子可以很方便的写出来： $G(N)=\sum_{y=1}^{N}\max\{\lfloor\frac{N-by}{a}\rfloor-\lfloor\frac{y}{c}\rfloor+1,0\}$，同时我们还可以写出 $G(N)=\sum_{d=1}^{N}F(\lfloor\frac{N}{d}\rfloor)$。那么再根据 Möbius inversion formula，我们可以表示出 $F(N)=\sum_{d=1}^{N}\mu(d)G(\lfloor\frac{N}{d}\rfloor)$。于是计算该问题答案的复杂度就是 $\mathcal{O}(N)$。

但是此时我们知道了 $B_{n}$ 的 $\frac{y_{n}}{x_{n}}$，怎么知道 $(x_{n},y_{n})$ 呢？我们可以再做一个二分。观察出这样一个规律：若令 $l=(1,0),r=(0,1)$，那么中间位置就是 $l+r$。于是我们可以再次做一个二分，利用 $\frac{y}{x}$ 单调来做 check。

顺带一提，这个还可以使用 类欧几里得 来计算。

◆ Computing $B_{l,\dots,r}$

可以发现这个东西可以知二求一，于是求出 $B_{l},B_{l+1}$ 就行了。当然也可以求出 $B_{l},B_{r}$ 然后做二分搜索。

Description

Link.

给出一个长度为 $n$ 的序列 $a$，求 $\sum_{i=1}^{n}[\forall j\in[1,i)\cup(i,n],a_{j}\nmid a_{i}]$。

Solution

首先特判序列中有 $1$ 的情况。

然后调和级数把每个数的倍数开桶记录。

最后扫一遍序列，看该元素在桶里面出现的次数不超过一就有贡献。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=0; char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=200100,M=1000000;
int a[N],bc[M];
signed main()
{
    int n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int cnt=0,ans=0;
    for(int i=1;i<=n;++i) (a[i]==1)&&(++cnt);
    if(cnt) return printf("%d\n",cnt>1?0:1),0;
    for(int i=1;i<=n;++i) for(int j=a[i];j<=M;j+=a[i]) ++bc[j];
    for(int i=1;i<=n;++i) (bc[a[i]]<=1)&&(++ans);
    printf("%d\n",ans);
    return 0;
}

我是傻逼。

「CF 1539A」Contest Start

Link.

答案是 $\sum_{i=1}^{n-1}\min\{i,\lfloor\frac{t}{x}\rfloor\}$，等差数列求和优化。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int main(){
    int T;
    ll n,x,t;
    for(sf(T);T;--T){
        sf(n),sf(x),sf(t);
        ll ans=0,d=t/x;
        --n;
        if(n>=d)ans=(n-d)*d+d*(d+1)/2;
        else ans=n*(n+1)/2;
        pf(ans);
    }
    return 0;
}

「CF 1539B」Love Song

Link.

暴力。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int cap[100010][26],n,q;
char ch[100010];
int main(){
    sf(n),sf(q);
    scanf("%s",ch+1);
    for(int i=1;i<=n;++i){
        memcpy(cap[i],cap[i-1],sizeof(int)*26);
        cap[i][ch[i]-'a']++;
    }
    for(int l,r;q;--q){
        sf(l),sf(r);
        ll ans=0;
        for(int i=0;i<26;++i)ans+=(i+1)*(cap[r][i]-cap[l-1][i]);
        pf(ans);
    }
    return 0;
}

「CF 1539C」Stable Groups

Link.

贪心。

对原序列差分，把差分值拿出来排序后把前几个填了。正确性显然。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int n;
ll a[200010],k,x,df[200010];
int main(){
    sf(n);sf(k);sf(x);for(int i=1;i<=n;++i)sf(a[i]);
    sort(a+1,a+n+1);
    for(int i=2;i<=n;++i)df[i]=a[i]-a[i-1];
    vector<ll> ald;
    for(int i=2;i<=n;++i){
        if(df[i]>x)ald.emplace_back(df[i]);
    }
    sort(all(ald));
    int del=0;
    for(int i=0;i<int(ald.size());++i){
        ll w=ald[i];
        if(w%x==0){
            if(k>=w/x-1)k-=w/x-1,++del;
            else break;
        }
        else{
            if(k>=w/x)k-=w/x,++del;
            else break;
        }
    }
    pf(int(ald.size())-del+1);
    return 0;
}

「CF 1539D」PriceFixed

Link.

以 $b$ 为关键字排序。

首先考虑把第一个元素「激活」，即填满 $b_{1}$ 个商品。

然后后面的元素有两种决策：

  1. 使用前面已经「激活」的商品来「激活」该商品后买完；
  2. 直接买 $a_{i}$ 个，注意分 $a_{i},b_{i}$ 大小讨论。

两种决策会使总买入商品数不一致，对后面有影响（？）。

现在考场上那个傻逼在想 DP。

但是注意到这样搞的代价是没有差别的，$2-1=1$ 抵了。

那么就一定存在一种最优方案使得每种产品买恰好 $a_{i}$ 个，搞两个指针扫一下就行了。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
struct st{ll a,b;}a[100010];
int n;
int main(){
    sf(n);for(int i=1;i<=n;++i)sf(a[i].a),sf(a[i].b);
    sort(a+1,a+n+1,[](st x,st y){return x.b<y.b || (x.b==y.b && x.a<y.a);});
    ll nw=0,ans=0;
    for(int i=1,j=n;i<=j;){
        if(nw>=a[i].b){
            ans+=a[i].a;
            nw+=a[i].a;
            ++i;
        }
        else{
            if(a[j].a+nw>=a[i].b){
                ll temp=a[i].b-nw;
                ans+=2*temp;
                nw+=temp;
                a[j].a-=temp;
            }
            else{
                ans+=a[j].a*2;
                nw+=a[j].a;
                --j;
            }
        }
    }
    pf(ans);
    return 0;
}

「CF 1539E」Game with Cards

Link.

gap 略大。搞不动先咕着。

「CF 1539F」Strange Array

Link.

假的，懒得写了，具体看 Rainybunny 的评论吧。

$\ \ \ \ $F：发现对于某个 $a_{i}$，已知包含它的某个区间中，$\le a_{i}$ 与 $>a_{i}$ 的数的数量差就能得到它的特征值。不妨令“大于等于”为 $+1$，“小于”为 $-1$，线段树维护区间最大前缀和与最大后缀和，升序扫描 $a$ 值就能更新答案。$+1,-1$ 反过来再做一遍，最后是 $\mathcal O(n\log_{2}n)$ 的。
$\ \ \ \ $赛后瞬间补题的原因大概是细节有点多√

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
template<typename T,typename... Tt>void sf(T &x,Tt&... aa){sf(x),sf(aa...);}
int n,a[200010],stp,Segres;
vector<int> ps[200010];
struct node{int p,s,sm;node(int a=0,int b=0,int c=0){p=a;s=b;sm=c;}};
struct Segtree{
    const int n;
    vector<node> ns;
    Segtree(int n,int fl):n(n),ns(n*4+5){give(1,n,1,fl);}
    node mrg(node a,node b){
        node c;
        c.p=max(a.p,a.sm+b.p);
        c.s=max(b.s,b.sm+a.s);
        c.sm=a.sm+b.sm;
        return c;
    }
    void give(int l,int r,int p,int v){
        if(r-l==0){ns[p]=node(max(v,0),max(v,0),v);return;}
        int m=(l+r)/2;
        give(l,m,p*2,v),give(m+1,r,p*2+1,v);
        ns[p]=mrg(ns[p*2],ns[p*2+1]);
    }
    void ins(int l,int r,int p,int x,int v){
        if(r-l==0){ns[p]=node(max(v,0),max(v,0),v);return;}
        int m=(l+r)/2;
        if(m>=x)ins(l,m,p*2,x,v);
        else ins(m+1,r,p*2+1,x,v);
        ns[p]=mrg(ns[p*2],ns[p*2+1]);
    }
    void qpre(int l,int r,int p,int x){
        if(l>=x){stp=max(stp,Segres+ns[p].p);Segres+=ns[p].sm;return;}
        int m=(l+r)/2;
        if(m>=x)qpre(l,m,p*2,x);qpre(m+1,r,p*2+1,x);
    }
    void qsuf(int l,int r,int p,int x){
        if(r<=x){stp=max(stp,Segres+ns[p].s);Segres+=ns[p].sm;return;}
        int m=(l+r)/2;
        if(m<x)qsuf(m+1,r,p*2+1,x);qsuf(l,m,p*2,x);
    }
    void ins(int x,int y){ins(1,n,1,x,y);}
    int qpre(int x){Segres=stp=0;qpre(1,n,1,x);return stp;}
    int qsuf(int x){Segres=stp=0;qsuf(1,n,1,x);return stp;}
};
int main(){
    sf(n);for(int i=1;i<=n;++i)sf(a[i]),ps[a[i]].emplace_back(i);
    int value=1;
    vector<int> ans(n);
    for(int value=1;value>-2;value-=2){
        Segtree t(n,value);
        for(int i=1;i<=n;++i){
            if(value==-1)for(int x:ps[i])t.ins(x,-value);
            for(int x:ps[i]){
                int r0,r1;
                r1=t.qpre(x);
                r0=t.qsuf(x);
                if((r0+r1-1)&1)ans[x-1]=max(ans[x-1],(r0+r1-1)/2);
                else{
                    if(value==1)ans[x-1]=max(ans[x-1],(r0+r1-1)/2);
                    else ans[x-1]=max(ans[x-1],(r0+r1-2)/2);
                }
            }
            if(value==1)for(int x:ps[i])t.ins(x,-value);
        }
    }
    for(int x:ans)pf(x,' ');
    return 0;
}

Description

Link.

求

$$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(i\cdot j,i\cdot k,j\cdot k)\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)$$

Solution

考虑把 $i,j,k$ 分别唯一分解，显然 $ij,jk,ik$ 并没有增加唯一分解后使用的质数数量，仅仅改变了指数。再考虑 $\gcd$ 的本质就是唯一分解后对指数取 $\min$ 的乘积结果。钦定研究一个质因数，设 $i,j,k$ 该质因数的指数分别为 $a,b,c$，则 $\gcd$ 上该位的指数为 $\min(a,b,c)$，我们做这样一个容斥：$\min(a+b,b+c,a+c)=\min(a,b)+\min(a,c)+\min(b,c)-\min(a,b,c)$。证明不妨设 $a<b<c$ 即证。

那么有：

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}(ij,ik,jk)(i,j,k)\left(\frac{(i,j)}{(i,k)(j,k)}+\frac{(i,k)}{(i,j)(j,k)}+\frac{(j,k)}{(i,j)(i,k)}\right) \\ \begin{aligned} &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}\frac{(i,j)(i,k)(j,k)}{(i,j,k)}(i,j,k)\frac{(i,j)^{2}+(i,k)^{2}+(j,k)^{2}}{(i,j)(i,k)(j,k)} \\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}(i,j)^{2}+(i,k)^{2}+(j,k)^{2} \\ \end{aligned} $$

注意到三个部分并无本质不同，我们设 $F(n,m,p)=p\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^{2}$，答案即 $F(n,m,p)+F(n,p,m)+F(m,p,n)$。接下来推导 $F$，同时钦定 $n<m$：

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^{2} \\ \begin{aligned} &=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}d^{2}[(i,j)=1] \\ &=\sum_{d=1}^{n}d^{2}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{t\mid(i,j)}\mu(t) \\ &=\sum_{T=1}^{n}\sum_{d\mid T}d^{2}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\mu(\frac{T}{d}) \\ \end{aligned} $$

令 $f(x)=\sum_{d|x}d^{2}\mu(\frac{x}{d})$，显然是个积性函数，$f(p)=p^{2}-1$，不需要 $k$ 次方就能做了欸。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
con(int) MOD=1e9+7;
int T,n,m,p;
ll mu[20000010],f[20000010],tag[20000010],prime[20000010],cnt;
void makePrime(int l)
{
    mu[1]=f[1]=1;
    for(ll i=2;i<=l;++i)
    {
        if(!tag[i])    prime[++cnt]=i,f[i]=(i*i%MOD-1+MOD)%MOD;
        for(int j=1;j<=cnt && prime[j]*i<=l;++j)
        {
            tag[i*prime[j]]=1;
            if(i%prime[j])    f[i*prime[j]]=f[i]*f[prime[j]]%MOD;
            else
            {
                f[i*prime[j]]=f[i]*prime[j]%MOD*prime[j]%MOD;
                break;
            }
        }
    }
    for(int i=1;i<=l;++i)    f[i]+=f[i-1],f[i]%=MOD;
}
ll cal(int n,int m,int p)
{
    if(n>m)    n^=m^=n^=m;
    ll res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=std::min(n/(n/l),m/(m/l));
        res+=(f[r]-f[l-1]+MOD)*(n/l)%MOD*(m/l)%MOD;
        res%=MOD;
    }
    return (res*p%MOD+MOD)%MOD;
}
int main()
{
    makePrime(2e7);
    for(sf(T);T;--T)    sf(n),sf(m),sf(p),pf(((cal(n,m,p)+cal(n,p,m)%MOD)+cal(m,p,n))%MOD);
    return 0;
}
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. ...
  10. 10