Problem J
Triple-Free Binary Strings
Input: Standard Input

Output: Standard Output

A binary string consists of ones and zeros. Given a binary string T, if  there is no binary string S such that SSS (concatenate three copies of S together) is a substring of T, we say T is triple-free.

A pattern consists of ones, zeros and asterisks, where an asterisk(*) can be replaced by either one or zero. For example, the pattern 0**1 contains strings 0001, 0011, 0101, 0111, but not 1001 or 0000.

Given a pattern P, how many triple-free binary strings does it contain?

Input
Each line of the input represents a test case, which contains the length of pattern, n(0
 
The input terminates when n=0.
 
Output
For each test case, print the case number and the answer, shown below. 
 
Sample Input                       Output for Sample Input




4 0**1
5 *****
10 **01**01**
0
 


Case 1: 2
Case 2: 16
Case 3: 9
 







題意：給定一個串，*可以代表0,1有多少字串，沒有3個連續相同的串。
思路：深搜加位運算，每次判斷當前串如果有重復3個
#include 
#include 

const int N = 35;

int n;
char str[N];

bool judge(int state, int len) {
	int m = (1<>len);
	int ss = (state&m);
	state = ((state&(~m))>>len);
	if (s == ss && ss == state) return true;
	return false;
}

int dfs(int state, int len) {
	int ans = 0, s = state;
	for (int i = 0; i <= len - 3; i ++) {
		if ((len - i) % 3 == 0 && judge(s, (len - i) / 3)) return 0;
		s = ((s&(~1))>>1);
	}
	if (len == n) return 1;
	if (str[len] == '0')
		ans += dfs(state, len + 1);
	else if (str[len] == '1')
		ans += dfs(state^(1<

字串就返回，然後數字可以用二進制數表示。

代碼：