首页 > 其他分享 >「杂题乱刷2」P11267

「杂题乱刷2」P11267

时间:2024-11-09 13:19:00浏览次数:1  
标签:nxt return ll 往后 x% 杂题 sum P11267

题目链接

P11267 【MX-S5-T1】王国边缘

解题思路

先考虑对于 \(1 \sim n\) 中的每一个点往后跳 \(1\) 次会跳的距离。

那么为什么只用处理 \(1 \sim n\) 这些点而不去处理其余的点往后跳的距离呢?

我们可以发现,由于字符串是无线循环的,所以对于位置模 \(n\) 的结果相同时,那么往后跳的距离也是相同的。

我们可以先将字符串断环成链倍长后做前缀和来处理 \(l \sim r\) 中的 \(1\) 的数量。

然后容易二分得出往后跳的距离。

然后我们就可以求出对于每个点 \(i\) 往后可以跳跃的距离。

然后问题询问的是往后跳 \(k\) 次的最终位置。

这是一个经典的倍增问题,直接倍增即可。

注意,在倍增过程中,可能答案会爆 long long

参考代码

记得加上快读。

ll n,m,k;
ll x,y;
string s;
ll corn=1;
ll mod=1e9+7;
ll sum[400010];
__int128 nxt[400010][70];
ll ask(ll x) // 1~x 有几个 1
{
    return sum[x%n]+sum[n]*(x/n);
}
ll query(ll l,ll r){// l~r 中有几个 1
    return ask(r)-ask(l-1);
}
ll f(__int128 x)
{
    if(x%n==0)
        return n;
    return x%n;
}
ll corn2=1;
void solve()
{
    _clear();
    cin>>n>>m>>k>>s;
    s=s+s;
    s=' '+s;
    forl(i,1,n)
        corn&=s[i]=='0',
        corn2&=s[i]=='1';
    if(corn)
    {
        while(k--)
            cin>>x>>y,
            cout<<(x+y)%mod<<endl;
        return ;
    }
    if(corn2)
    {
        while(k--)
            cin>>x>>y,
            cout<<(x+(y%mod)*(m%mod))%mod<<endl;
        return ;
    }
    forl(i,1,n*2)
        sum[i]=sum[i-1]+(s[i]=='1');
    forl(i,1,n)
    {
        ll L=i+1,R=i+m;
        while(L<R)
        {
            ll Mid=(L+R)/2;
            if(query(Mid+1,i+m)>=1)
                L=Mid+1;
            else
                R=Mid;
        }
        if(query(L,L)>=1)
            nxt[i][0]=L-i;
        else
            nxt[i][0]=1;
    }
    forl(j,1,62)
        forl(i,1,n)
            nxt[i][j]=(nxt[i][j-1]+nxt[f(i+nxt[i][j-1])][j-1]);
    while(k--)
    {
        cin>>x>>y;
        ll ans=x%mod;
        forr(i,62,0)
            if(y&(1ll<<i))
            {
                x%=n;
                if(x==0)
                    x=n;
                ans=(ans+nxt[x][i]%mod)%mod;
                x+=nxt[x][i]%n;
            }
        cout<<ans<<endl;
    }
}

标签:nxt,return,ll,往后,x%,杂题,sum,P11267
From: https://www.cnblogs.com/wangmarui/p/18536681

相关文章

  • 双连通分量学习笔记+杂题
    图论系列:前言:もしも明日がくるのならあなたと花を育てたいもしも明日がくるのならあなたと愛を語りたい走って笑って転んで相关题单:https://www.luogu.com.cn/training/641352一.割点与桥双连通分量是针对无向图来说的,有向图是强连通分量。在了解双连通分量之前需要先......
  • AGC 杂题
    AGC029CLexicographicconstraints有\(n\)个字符串,现在告知它们的长度\(a_i\),求使得\(\foralli\in[1,n),s_i<s_{i+1}\)的最小字符集大小。\(n\le2\times10^5,a_i\le10^9\)二分字符集大小\(|\Sigma|\),分类讨论,设起始字符为a:\(a_i<a_{i+1}\):显然\(s_{i+1}\leftarr......
  • ABC 杂题
    ABC186EThrone有\(n\)个圆形排列的椅子,一开始你在\(s+1\)上,每次可以向右移动\(k\)个位置,求移动到\(1\)的最小步数,或报告无解。\(2\len,k\le10^9\)很容易想到构造方程:\[s+qk\equiv0\pmodn\]\[q\equiv(n-s)k^{-1}\pmodn\]直接exgcd求逆元,算出在\([1,n-1]\)......
  • 杂题选做1
    杂题选做1[ARC112F]DieSiedler注意到如果存在某一个\(j\)满足这种牌的数量大于等于\(2j\),那么一定会兑换为\(j\bmodn+1\)的牌。所以我们考虑这个过程的逆过程,就是将一张牌\(j\)换成\((j-1)!2^{j-1}\)张\(1\)号牌,最终全部的牌都被转化为了\(1\)号牌,但是结果并......
  • 数据结构杂题乱记
    由于是杂题乱记所以题目大多数不会太难。目录P2572[SCOI2010]序列操作题目内容思路代码P2572[SCOI2010]序列操作题目内容给你一个\(01\)序列,支持\(5\)种操作:0lr区间赋值为\(0\);1lr区间赋值为\(1\);2lr区间取反,即\(0\)变\(1\)、\(1\)变\(0\);3lr询......
  • 杂题随笔 10.31 两道LIS相关的题
    https://www.luogu.com.cn/problem/AT_abc354_f题意:给定一个序列a,求出所有的i使得任意一个a的最长子序列包含i。解法:我们先求这个序列的LIS的长度maxx,然后再去正着求一遍最长上升子序列和反着求一遍最长下降子序列即可,如果拼起来等于maxx那么说明i这个点是满足要求的点。注意细......
  • Day65 小贪心 & 自选杂题
    哎怎么必可公益赛被爆破了,怎么lifan还加了几道我们的训练题目作为补偿。CF不知道死了多久了,一上午都没有打成duel!今天上午精神状态明显好了很多,可能和咖啡有点关系吧。按照时间顺序写题吧。AT_arc070_b可以进行撤销背包,也可以算前后缀背包,都是记录方案数。不难的。AT_a......
  • 强连通分量学习笔记+杂题
    图论系列:前言:僕は明快さ故にアイロニー優柔不断なフォローミー後悔後悔夜の果て相关题单:戳我一.强连通分量相关定义基本摘自oiwiki,相关定义还是需要了解。(实际就是搬了个oiwiki)强连通分量主要在研究有向图可达性,针对的图类型为有向弱联通图。1.强连通定义强连通:对......
  • 杂题随笔 2024.10.25 两道图论
    最近在写abc375这场,最后的F和G是两道很典的图论题。https://atcoder.jp/contests/abc375/tasks/abc375_f题意:大致就是说给你一张图,有两种操作:第一种操作是把第i条边删掉,第二种操作是询问u,v两点的最短路。解法:这种题目印象里好像是考过几次了,把在线询问的顺序转变,倒着做,把减边......
  • 2024.10.23-25 杂题
    2024.10.23-25杂题P7323[WC2021]括号路径如果存在\((a,b,w)\),\((c,b,w)\)。那么\((a,c)\)就是一条合法路径。所以把\(a,c\)放入一个集合。然后合并新的的时候把\(w\)一样的合并了就行。最后统计每个"块"的数量,答案就是\(\sum_{i=1}^{n}C_{cnt_i}^{2}\)复杂度\(O(......