2019icpc 南昌C And and Pair dp

题目链接
大意：给你一个超大数字n的二进制表示，询问有多少组数对（i，j），数对要满足，
0≤j≤i≤n;
i & n=i；
i & j=0；
首先对于我看到其他的什么数位dp，组合数学，我一个没懂。我说下 我自己是怎么dp的。
对题目分析
i&n = i，那么说明在二进制的情况下，相同的某一位数，n是1，那么i可以是1，也可以是0.（1&1 = 1， 1 & 0 = 0），n是0，那么i只能是0（0&0 = 0，如果i是1那个i&n不等于i）
i&j = 0，那么说明在二进制的情况下，相同的某一位数，i是1，那么j只可以是0，i是0，那么j可以是1或者0

有了上面的结论我们来设计状态，由于动态规划的方程就是要表达出我们所需要的状态，我是这样子设计的
f[k][0/1][0/1]，第一维表示现在枚举到第几位，第二维度表示在这一位的数对中的i数字，这一位表示是什么，第三维度表示的是j在这一位表示的是什么。
答案是怎么得来的呢？就是每一位的sum（f[k][1][0]）, （i的数字必须是1，j的数字必须是0，k表示了所有的长度），必须倒着枚举，因为从低位向高位枚举。下面是转移方程，可以看到我们只是算出了所有的合法可能性，（当i为0，j为1时虽然在这一位不合法，但是在以后当出现i为1，j为0时这个他又合法了，所以要算）,当n的所在位数是0，你这一位的i就不能填1，所以[1][0]这种就永远都不会有合法序列，不需要转移。
在总结一下下其实就是，我们只是单纯的在枚举所有的合法状态，把每一位产生的数对加上去而已，怎么设计出能表示合法状态的数组，方程这个其实你能表示就行，怎么写无关紧要。

          if (node[i] == '0') {
				//你只能填0；直接转移
				f[i][0][0] =  ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
			// f[i][1][0] = f[i + 1][0][0] + f[i + 1][0][1] + f[i + 1][1][0];
			}
			else {
				f[i][1][0] =  ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][0] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
			}
			ans += f[i][1][0];
			

最后的代码

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<time.h>
#include<string>
#include<cmath>
#include <ctime>
#include<bitset>
#include <cctype>
#define debug cout<<"*********degug**********";
#define index index_
#define int long long
#define RE register
#define yn yn_
using namespace std;
const long long max_ = 1e5 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
char node[max_];
int f[max_][3][3];
signed main() {
	int T = read();
	while (T--){
		//cin >> (node + 1);
		scanf("%s", node + 1);
		int len = strlen(node + 1),ans = 1;
		memset(f, 0, sizeof(f));
		if (node[len] == '1') {
			f[len][1][0] = 1;
			f[len][0][0] = 1;
			f[len][0][1] = 1;
		}
		else {
			f[len][0][1] = 1;
			f[len][0][0] = 1;
		}
		ans += f[len][1][0];
		for (int i = len - 1; i >= 1; i--) {
			if (node[i] == '0') {
				//你只能填0；直接转移
				f[i][0][0] =  ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
			// f[i][1][0] = f[i + 1][0][0] + f[i + 1][0][1] + f[i + 1][1][0];
			}
			else {
				f[i][1][0] =  ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][0] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
				f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
			}
			ans += f[i][1][0];
			ans %= mod;
		}
		cout << ans<<endl;
	}
	return 0;
}