ABC 310 E NAND repeatedly

题意
太懒了，直接给链接吧，题意挺好懂的。https://atcoder.jp/contests/abc310/tasks/abc310_e

思路
NAND运算，根据题意，我们可以总结出以下两点：

1. 当前结果如果遇到1，那么结果反转(0->1,1->0)
2. 当前结果如果遇到0，那么结果赋值为1

我们手模一下这个样例1：

• 00110（初始）
• 01011（i==1）
• ×0101（i==2）
• ××101（i==3）
• ×××11（i==4）
• ××××0（i==5）
  答案9=3+2+2+2。
  我们横着看好像没有发现什么，但是纵向来看就有结论了。当当前的i为1时，前一列的结果全部反转，并且添上一个1;当当前的i为0时，前一列的结果全部赋值为1，并且添上一个0。这样我们就很容易的写出dp了：
  定义dp[i][j]为到达第i个数时，这一列结果为j的个数，j只可取0或1，有如下状态转移方程:
• dp[i][1]=dp[i-1][0]+1,dp[i][0]=dp[i-1][1]； (a[i]==1)
• dp[i][1]=dp[i-1][0]+dp[i-1][1],dp[i][0]=1； (a[i]==0)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int a[maxn],dp[maxn][2];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]=='1') a[i]=1;
		else a[i]=0;
	}
	if(a[1]) dp[1][1]=1;
	else dp[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		if(a[i]) 
		{
			dp[i][1]=dp[i-1][0]+1;
			dp[i][0]=dp[i-1][1];
		}
		else 
		{
			dp[i][1]=dp[i-1][0]+dp[i-1][1];
			dp[i][0]=1;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=ans+dp[i][1];
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
	
	return 0;
 }