AtCoder Beginner Contest 310 E题 NAND repeatedly

标签：动态规划
题意：给定一个长度为$n$的$01$字符串$A_i$，给定规则：$0⊼0=1,0⊼1=1,1⊼0=1,1⊼1=0$。

求${\sum }_{i=1}^n{\sum }_{j=i}^{n}f(i,j)$（$1<=i<=j<=n$）,$f(i,j)=\{\begin{array}{cc}{A}_i& (i=j)\\ f(i,j-1)⊼A_j& (i<j)\end{array}$。
题解：显然我们可以通过$O(n^2)$时间复杂度完成这道题要求，但是$n<=10^6$会超时。
$dp[i][0/1]$：前$i$个数字累计$nand（⊼）$为$0/1$的方案数。分以下两种情况考虑：

1. 当前数字是$0$，$dp[i][1]$累计是$1$的情况可以从前面$i-1$累计是$0$和$1$的情况转移过来，因为当前数字是$0$，不管和$0$和$1$$nand（⊼）$都是$1$；$dp[i][0]$累计是$0$的情况初始化成$1$。
2. 当前数字是$1$，$dp[i][1]$累计是$1$的情况只能从前面$i-1$累计是$0$的情况转移过来，并且计数增加$1$（算上自己本身的），因为$1⊼1=0$；$dp[i][0]$累计是$0$的情况从前面$i-1$累计是$1$的情况转移过来。

最后把每个位置的$dp[i][1]$累加一下即可。
代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
typedef long long ll;
ll dp[N][2];int main() {ll n, ans = 0;string s;cin >> n >> s;for (int i = 1; i <= n; i++) {if (s[i-1] == '0') {dp[i][1] = dp[i-1][0] + dp[i-1][1];dp[i][0] = 1;} else {dp[i][1] = dp[i-1][0] + 1;dp[i][0] = dp[i-1][1];}ans += dp[i][1];}cout << ans << endl;return 0;
}