Acwing 第48场周赛题解

直接按照题意模拟即可。

核心代码：

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(7);

    int n,m;
    cin >> n >> m;

    for(int i=1;;i++){
        n--;
        if(i%m==0) n++;
        if(n==0){
            cout << i;
            return 0;
        }
    }

    return 0;
}

n太大，模拟肯定不行。

开始寻找规律，发现无论球在哪里，每操作 6 次都会变为原来的状态 ，所以先对6取模再进行模拟即可。

核心代码：

int a[3];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(7);

    int n,x;
    cin >> n >> x;
    a[x]=1;
    n%=6;
    for(int i=n;i>=1;i--){
        if(i&1) swap(a[0],a[1]);
        else swap(a[1],a[2]);
    }
    for(int i=0;i<3;i++){
        if(a[i]) cout << i;
    }

    return 0;
}

由题意可知 ，对任意 i ，j，若 a[ i ] = a[ j ] ，则任意 x ∈[ i , j] 内 b[ x ]都相等。

假设我们求出了这样的区间个数，减去包含 1 的区间（此区间内都为0），显然答案为 pow(2,X)%998244353 ,X 为区间个数。

接下来怎么求区间。

用哈希表来记录某个数字最后一次出现的下边，遇到后组成区间即可（只出现一次的也要组成区间），最后将相交的区间合并即可。

核心代码:

int n,a[maxn];
map mp;
vector s,res;
LL ksm(LL x,LL y){
    LL res = 1;
    for(;y;y>>=1){
        if(y&1)
            res = res*x%mod;
        x=x*x%mod;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(7);

    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    for(int i=1;i<=n;i++){
        if(mp[a[i]]){
            s.push_back({mp[a[i]],i});
            mp[a[i]]=i;
        }else mp[a[i]]=i,s.push_back({i,i});
    }
    sort(all(s));
    int l=-1,r=-1;
    for(int i=0;i
        if(l==-1){
            l=s[i].fi,r=s[i].se;
        }
        if(i+1=s[i+1].fi){
            r=max(r,s[i+1].se);
        }else{
            res.push_back({l,r});
            l=-1,r=-1;
        }
    }

    cout << ksm(2,(int)(res.size()-1)) ;

    return 0;
}