题解：P10403 「XSOI-R1」跳跃游戏

· · 题解

upd：修改了一处笔误。

因为不符合任何一个条件的跳跃价值为 0，所以我们可以跳跃至任意位置，题意即求 \sum_{i=1}^{n} \sum_{j=i}^{n} score_{i,j}。

由于 \gcd 运算有结合律，所以我们可以用 st 表来维护区间 \gcd 的值，预处理 O(n\log n)，查询 O(1)。

因为两个得分条件不冲突，所以我们可以分开来考虑。假设我们固定一个端点 i，区间 \gcd 是单调不增的，因此我们可以二分找到 l 和 r，使对于 l \leq j \leq r，都有 \gcd(a_i,a_{i+1},...,a_j) = k，k 为这个条件中需要的值，即 2 或 3，统计答案时注意还有区间长度限制，等差数列直接算就好了，复杂度 O(n\log n)。

注意本题时间限制。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar('\n')
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define pdi pair<ll,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(register ll i = a ; i <= b ; ++ i )
#define Fo(a,i,b) for(register ll i = a ; i >= b ; -- i )
#define pb push_back
//#pragma GCC optimize(2)
using namespace std;
typedef int ll;
// typedef long long ll;
//typedef __int128 ll;
typedef double db;
inline void read(ll &opp){ll x=0,t=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){t=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}opp=x*t;return; }
inline void wr(ll x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}
const ll N=1e6+5,M=2e4+5,mod=1e9+7;
ll n,a[N],st[N][20];
long long sum;
inline ll ask(ll l,ll r){
    ll lg=log2(r-l+1);
    return __gcd(st[l][lg],st[r-(1<<lg)+1][lg]);
}
inline void check3(ll i)
{
    ll l=i,r=n;//3 5   3 6
    while(l<r){
        ll mid=l+r>>1;
        if(ask(i,mid)>3) l=mid+1;
        else r=mid;
    }
    ll beg=l;if(ask(i,beg)!=3) return;
    l=beg,r=n;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(ask(i,mid)==3) l=mid;
        else r=mid-1;
    }
    ll end=l;if(ask(i,end)!=3) return; 
    ll beg1=0,end1=0;
    if((beg-i+1)&1) beg1=beg-i+1;
    else if(end!=beg) beg1=beg-i+2;
    else if(end==beg) return;
    if((end-i+1)&1) end1=end-i+1;
    else end1=end-i;
    sum+=1ll*(beg1+end1)*((end1-beg1)/2ll+1ll)/2ll;
}
inline void check2(ll i)
{
    if(i==n) return;
    ll l=i,r=n;
    while(l<r){
        ll mid=l+r>>1;
        if(ask(i,mid)>2) l=mid+1;
        else r=mid; 
    }
    ll beg=l;if(ask(i,beg)!=2) return;
    l=beg,r=n;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(ask(i,mid)==2) l=mid;
        else r=mid-1;
    }
    ll end=l;if(ask(i,end)!=2) return;
    ll beg1=0,end1=0;
    if((beg-i)&1) beg1=beg-i+1;
    else if(beg!=end) beg1=beg-i+2;
    else if(beg==end) return;
    if((end-i)&1) end1=end-i+1;
    else end1=end-i;
    sum=sum+1ll*(beg1+end1)*((end1-beg1)/2ll+1ll)/2ll;
}
signed main(){
    read(n);fo(1,i,n) read(a[i]),st[i][0]=a[i];
    fo(1,j,20) fo(1,i,n) if(i+(1<<j)-1<=n) st[i][j]=__gcd(st[i][j-1],st[i+(1<<j-1)][j-1]);
    fo(1,i,n) check3(i),check2(i);
    cout << sum << endl;
    return 0;
}