题解 P6616 【环 Rings】

WYXkk · 2020-06-16 15:21:12 · 题解

由于被这题卡了好久，最后过了还拿到了最优解，于是来写波题解（

首先，我们不应该考虑如何把所示状态 拆下来，而应该考虑如何将它 装上去。

容易知道，这两者是完全等价的。

然后，我们先考虑一种极其特殊的情况：只有一个环在上面（即 \text{Subtask 3}）。

设这个环在 n 位置，其答案为 f_n。

易知：f_1=1,f_2=2，且对于 n\ge 3，f_n=2f_{n-1}+1。

（先 f_{n-1} 步单独上 n-1 环，然后一步上 n 环，然后 f_{n-1} 步下 {n-1} 环）

然后随便找个规律可得 f_n=\begin{cases}1,&n=1\\3\times2^{n-2}-1,&n\ge 2\end{cases}。

现在考虑一般的情况，例如 111011011。

既然要上第 9 环，那么必须得有只有第 8 环的时刻，于是 000000000 -> 010000000 -> 110000000，共用了 f_8+1=3\times2^6 步；

接下来，我们可以不管前两个环了，只需要让 0000000 -> 1011011 即可。

同上可知，既然要上 7 环，那么必须得有单独上 6 环，即 0000000 -> 0100000 -> 1100000，共用了 f_6+1=3\times2^4 步；

接下来 7 环就可以不管了，只需要让 100000 -> 011011 即可。

然后，因为要下 6 环，因此单独上 5 环，然后把 6 环下下来，即 100000 -> 110000 -> 010000，共用了 f_5+1=3\times2^3 步；

接下来 5,6 两环就可以不管了，只需要让 0000 -> 1011 即可。

我们应该先单上 3 环，然后上 4 环，然后单上 2 环，然后下 3 环，然后上 1 环。其中的逻辑和上面类似，不再赘述。

因此，我们可以得到如下策略：

从最高位开始，忽略所有已完成位，然后上次高位，完成最高位，以此类推。

回到原题，如何求出最优解的步数呢？

首先倒序输入，然后合并段。

UF(i,m,1) {rd(l[i]);rd(st[i]);}
int tot=0,st2=0;
F(i,1,m) {if(st[i]!=st2) ++tot,st2=st[i];l2[tot]+=l[i];}
n-=l2[0];

扫描所有 1 段，分别计算他们的贡献。每扫描完一段，忽略之（即将 n 减去已匹配的部分）

接下来就是大分类讨论了——（为了防止 Markdown 爆炸我加上了层数以便区分）

• (1)如果这是最后一段（即后面没有 0 了）：

  • (2)如果其长度为奇数 l：3\times2^{l-3}+3\times2^{l-5}+\cdots+3\times2^0+1=2^{l-1}
  • (2)如果其长度为偶数 l：3\times2^{l-3}+3\times2^{l-5}+\cdots+3\times2^1+1=2^{l-1}-1

• (1)如果这段后面还有长度 l^\prime 的 0 段：

  • (2)如果这段长度为奇数 l：3\times2^{n-3}+3\times2^{n-5}+\cdots+3\times2^{n-l}=2^{n-1}-2^{n-l}

  • (3)如果再后面没有了/只有一个 1 就到末尾：3\times2^{n-l-1}-1

  • (3)否则：3\times2^{n-l-2}+3\times2^{n-l-3}+...+3\times2^{n-l-l^\prime-2}=3\times(2^{n-l-1}-2^{n-l-l^\prime-2})

  (2)最后删去下一段 1 的开头一个 1。

  • (2)如果这段长度为偶数 l：3\times2^{n-3}+3\times2^{n-5}+...+3\times2^{n-l-1}=2^{n-1}-2^{n-l-1}

更新 n。（我一开始就漏了这一步调了 114514 年）

最后输出结果即可。复杂度 O(m)。

#define int ll
const int M=100005;
ll l[M],st[M];
ll l2[M],tot=0;
const ll p=1201201201;
ll qp(ll a,ll b){if(!b) return 1;ll w=qp(a,b>>1);w=w*w%p;return b&1?w*a%p:w;}
signed main()
{
    ll n=rd();
    int m=rd();
    F(i,1,m) {rd(l[i]);rd(st[i]);}
    int st2=0;
    UF(i,m,1) if(st[i]==st2) l2[tot]+=l[i];else {++tot;l2[tot]=l[i],st2=st[i];}
    int lst=0;
    ll ans=0;n-=l2[0];
    F(i,1,tot)
    {
        l2[i]-=lst;n-=lst;
        if(i==tot)
        {
            if(l2[i]&1)
            {
                ans+=qp(2,l2[i]-1);
                ans=(ans%p+p)%p;
            }
            else
            {
                if(l2[i]) ans+=qp(2,l2[i]-1)-1;
                ans=(ans%p+p)%p;
            }
            lst=0;
        }
        else
        {
            if(l2[i]&1)
            {
                ans+=qp(2,n-1)-qp(2,n-l2[i]);
                if(n-l2[i]-l2[i+1]-2>=0) ans+=3*(qp(2,n-l2[i]-1)-qp(2,n-l2[i]-l2[i+1]-2));
                else ans+=3*qp(2,n-l2[i]-1)-1;
                ans=(ans%p+p)%p;lst=1;
            }
            else
            {
                ans+=qp(2,n-1)-qp(2,n-l2[i]-1);
                ans=(ans%p+p)%p;lst=0;
            }
            n-=l2[i]+l2[i+1];++i;
        }
    }
    cout<<ans%p<<endl;
    return 0;
}