自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:22:27，当前版本为作者最后更新于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)$。

$\texttt{code:}$

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