noone___'s blog
0%

12801202-AGC015

发表于 更新于 分类于
AGC015

D

给定正整数 $A,B \quad (1\leq A,B\leq 2^{60})$ ，令 $S=\{A,A+1,A+2,…,B-1,B\}$ ，求 $S$ 的所有非空子集的元素按位或的结果有多少不同取值

首先有 $A=B$ 时答案为 $1$

设 $AB$ 最高的不一样的位为第 $b$ 位，则 $A$ 的第 $b$ 位一定为 $0$ ， $B$ 的第 $b$ 位一定是 $1$

考虑比 $b$ 高的那些位，无论取 $S$ 中的哪些数，其比 $b$ 高的位结构相同，或的结果也相同，所以不必考虑这些位，只考虑前 $b$ 位

设 $U$ 在第 $b$ 位为 $0$ ，$b-1\sim 1$ 位为 $1$ ； $V$ 在第 $b$ 位为 $1$ ，$b-1\sim 1$ 位为 $0$

$S$ 子集或的结果有：

  • 第 $b$ 位为 $0$

    只能使用 $A\sim U$ 的元素，设 $T=\{A,A+1,…,U\}$ ，或的结果（或闭包）显然包含 $T$

    又由于 $a\mid b\geq \max(a,b)$ 所以或闭包中所有元素均 $\geq A$ ，且 $T$ 中所有数值可能为 $1$ 的位只有 $0,1,…,b-1$ 位，于是结果的每个数中，值为 $1$ 的为是这些位的子集，所以它们 $\leq T$

    综上， $T$ 就是 $T$ 的或闭包，共 $|T|$ 个

  • 第 $b$ 位为 $1$

    首先，$T\cup \{V\}$ 的或闭包中，考虑第 $b$ 位为 $1$ 的元素，和上面类似可知是 $\{V+A,V+A+1,…,V+U\}=[V+A,2V)$ 而它们的或闭包是 $[V,2V)$ ，即 $\left[2^b,2^{b+1}\right)$ 的子集，于是剩下的元素只有 $[V,V+A)$

    考虑「或闭包」在这个区间中的表现

    注意此时不能使用 $T$ 中的元素

    于是，只需要考虑 $V\sim B$ 中的元素，而这是原问题的一个子问题。从而，我们把 $V$ 和 $B$ 相同的位删掉 —— 即找到 $B$ 中除了 $b$ 外最高为 $1$ 的位，记为 $d$

    它们的或闭包就是 $\left[0,2^{d+1}\right)$ ，这部分的贡献就是 $\left[V,V+2^{d+1}\right)$

    综上，该部分答案就是 $\left[V,V+2^{d+1}\right)\cup [V+A,2V)$

1
2
3
4
5
6
7
8
9
10
11
12
int b, d; ll L, R;
inline ll doz(ll x){ return ~(x>>63)&x;}

int main(){
    scanf("%lld%lld",&L,&R);
    if(L==R) return puts("1"),0;
    b=__lg(L^R),L&=~(-2ll<<b),R&=~(-1ll<<b),d=R ? __lg(R)+1 : 0;
    printf("%lld\n",(2ll<<b)-L-doz(L-(1ll<<d)));
    getchar(),getchar();
    return 0;
}

E

数轴上有 $N$ 个点，每个点初始时在位置 $X_i$ ，以 $V_i$ 的速度向数轴正方向前进。 初始时刻，选择一些点为其染色，之后的行走过程中，染色的点会将其碰到的所有点都染上色，之后被染上色的点亦是如。此
在所有 $2^N$ 种初始染色方案中，问有多少种初始染色方案，能使得最终所有的点都被染色

按 $x_i$ 将所有点排序，第 $i$ 个点被选中后，对于 $jv_i 和 j>i且v_ji,v_j\leq \max_{k\leq i} v_k$ 的点都会被间接打上标记

考虑初始时最靠右的标记点 $i$ ，由于 $i$ 对右侧影响最强，故点 $j,j<i$ 被打标记当且仅当 $v_j\max{k\leq i} \ v_k$ 。只需要确保 $[1,i-1]$ 的点使 $j<i,v_j<\min_{k\geq i} \ v_k$ 的点都被打标记

设 $f_i$ 表示操纵 $[1,i-1]$ 的点使 $j<i ,v_j<\min_{k\geq i} \ v_k$ 的点都被打标记的方案数， 设 $j$ 是初始时 $[1,i-1]$ 内最靠右被打上标记的点，满足 $\max_{j<k<i\ ,\ v_k<\min_{t\geq i}\ v_t} \ v_k<\max_{1\leq k\leq j} \ v_k$

考虑用 $f_j$ 转移：合法的 $j$ 是一段右端点为 $i$ 的区间，考虑左端点：设 $mx$ 表示最大的 $mx$ 满足 $mx<i,v_{mx}<\min_{t\leq i} \ v_t$ 的 $v_{mx}$

对于 $v_{mx}$ 可以作为 $j$ 左侧只需要考虑 $\max_{1\leq k\leq j} \ v_k>v_{mx}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int N=2e5+100;
const int mod=1e9+7,INF=1e9+7;

inline int add(const int x,const int y){ return x+y<mod ? x+y : x+y-mod;}
inline int dec(const int x,const int y){ return x<y ? x-y+mod : x-y;}

int n,f[N],sf[N];
struct node{
    int x,v;
    friend bool operator<(const node &a,const node &b){ return a.x<b.x;}
}a[N];
int id[N];
int premn[N],sufmn[N],premx[N];

inline bool cmp(int x,int y){ return a[x].v<a[y].v;}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].v);
    sort(a+1,a+n+1);
    premn[0]=sufmn[n+1]=INF;
    for(rei i=1;i<=n;++i) premn[i]=min(premn[i-1],a[i].v);
    for(rei i=1;i<=n;++i) premx[i]=max(premx[i-1],a[i].v);
    for(rei i=n;i>=1;--i) sufmn[i]=min(sufmn[i+1],a[i].v);
    for(rei i=1;i<=n;++i) id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(rei i=1,j=1,p1=0,p2=1;i<=n+1;++i){
        if(i!=1) if(a[i-1].v<sufmn[i]) if(!p1 || a[i-1].v>a[p1].v) p1=i-1;
        while(j<=n && a[ id[j] ].v<sufmn[i]){
            if(id[j]<i) if(!p1||a[ id[j] ].v>a[p1].v) p1=id[j];
            ++j;
        }
        while(p2<=n && a[p2].v<a[p1].v) ++p2;
        if(p1){
            rei p=min(p2,p1);
            f[i]=dec(sf[i-1],sf[p-1]);
            sf[i]=add(sf[i-1],f[i]);
        }
        else f[i]=add(sf[i-1],1);
        sf[i]=add(sf[i-1],f[i]);
    }
    printf("%d",f[n+1]);
    getchar(),getchar();
    return 0;
}

F

定义 $E(x,y)$ 是对 $x,y$ 进行 $\text{Euclid}$ 算法需要的步数。其中 $E(a,b)=E(b,a) \forall a,b\in \N$ ; $E(0,a)=0$ ; 若 $0<a\leq b$ ，则 $E(a,b)=E(b\mod a,a)+1$ 。 有多次询问，每次给定 $x,y\in \N^+$ 求出 $\displaystyle{M=\max_{1\leq x\leq X} \max_{1\leq y\leq Y} E(x,y)}$ 以及 $\displaystyle{C_M=\sum_{x=1}^X\sum_{y=1}^Y [E(x,y)=M]}$

只会打表找结论，具体的数学过程参见yhx的博客

  • 结论 $1$ :

    $f(Fib(x),Fib(x+1))=x$ ，且不存在 $i,j \forall i,j\in \N 使 f(i,j)\geq x,i<Fib(x),j<Fib(x+1)$

  • 结论 $2$ :
    定义一个二元组 $(x,y)$ 是好的，当且仅当 不存在 $(i,j)$ 满足 $if(x,y)$

    一个二元组 $(x,y)$ 是优秀的，当且仅当 $x,y\leq Fib(v+2)+Fib(v-1)$ ，其中 $v=f(x,y)$

    那么：一个好的二元组进行一次 $\text{Euclid}$ 后一定变为一个优秀二元组，反证法易得

预处理所有优秀二元组就好qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N=110;
const int mod=1e9+7;

vector<PII> t[N];
int n,m,q,f[N];

signed main(){
    t[1].push_back(mk(1,2)),t[1].push_back(mk(1,3)),t[1].push_back(mk(1,4));
    f[0]=f[1]=1;
    for(rei i=2;i<=100;++i) f[i]=f[i-1]+f[i-2];
    for(rei i=1;i<=100;++i)
        for(rei j=0,l=t[i].size()-1;j<=l;++j){
            rei x=t[i][j].second,y=t[i][j].first+x;
            while(y<=f[i+3]+f[i]) t[i+1].push_back(mk(x,y)),y+=x;
        }
    scanf("%d",&q);
    while(q--){
        scanf("%lld%lld",&n,&m); if(n>m) n^=m,m^=n,n^=m;
        rei pos=1,ans=0;
        while(f[pos+1]<=n && f[pos+2]<=m) ++pos;
        printf("%lld ",pos);
        if(pos==1){ printf("%d\n",n%mod*m%mod); continue;}
        for(rei j=0,l=t[pos-1].size()-1;j<=l;++j){
            rei x=t[pos-1] [j].first,y=t[pos-1][j].second;
            if(y<=n) ans=(ans+(m-x)/y)%mod;
            if(y<=m) ans=(ans+(n-x)/y)%mod;
        }
        printf("%d\n",ans);
    }
    getchar(),getchar();
    return 0;
}