12801202-AGC015

D

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

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

设 $A B$ 最高的不一样的位为第 $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, \dots, U}$ ，或的结果（或闭包）显然包含 $T$

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

综上， $T$ 就是 $T$ 的或闭包，共 $| T |$ 个
第 $b$ 位为 $1$

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

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

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

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

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

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

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$ 的区间，考虑左端点：设 $m x$ 表示最大的 $m x$ 满足 $m x < i, v_{m x} < min_{t \leq i} v_{t}$ 的 $v_{m x}$

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

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$ 进行 $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^{+}$ 求出 $M = max_{1 \leq x \leq X} max_{1 \leq y \leq Y} E (x, y)$ 以及 $C_{M} = \sum_{x = 1}^{X} \sum_{y = 1}^{Y} [E (x, y) = M]$

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

结论 $1$ :

$f (F i b (x), F i b (x + 1)) = x$ ，且不存在 $i, j \forall i, j \in \N 使 f (i, j) \geq x, i < F i b (x), j < F i b (x + 1)$
结论 $2$ :
定义一个二元组 $(x, y)$ 是好的，当且仅当不存在 $(i, j)$ 满足 $if(x,y)$

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

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

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

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;
}