Submission #68791976

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
enum {
  NOT_STARTED = 0,
  LENGTH_ODD,
  LENGTH_EVEN
};
int N;
char T[212345];
uint64_t memo[212345][3][2];
uint64_t calc(int pos, int status, int is_one) {
  uint64_t ans = (status == LENGTH_ODD && is_one) || (status == LENGTH_EVEN && !is_one);
  if (pos >= N) return ans;
  if (memo[pos][status][is_one]) return ~memo[pos][status][is_one];
  switch (status) {
    case NOT_STARTED:
      /* スタートしない */
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

enum {
	NOT_STARTED = 0,
	LENGTH_ODD,
	LENGTH_EVEN
};

int N;
char T[212345];

uint64_t memo[212345][3][2];

uint64_t calc(int pos, int status, int is_one) {
	uint64_t ans = (status == LENGTH_ODD && is_one) || (status == LENGTH_EVEN && !is_one);
	if (pos >= N) return ans;
	if (memo[pos][status][is_one]) return ~memo[pos][status][is_one];
	switch (status) {
		case NOT_STARTED:
			/* スタートしない */
			ans += calc(pos + 1, NOT_STARTED, 0);
			/* スタートする */
			ans += calc(pos + 1, LENGTH_ODD, T[pos] != '0');
			break;
		case LENGTH_ODD:
			ans += calc(pos + 1, LENGTH_EVEN, is_one ^ (T[pos] != '0'));
			break;
		case LENGTH_EVEN:
			ans += calc(pos + 1, LENGTH_ODD, is_one ^ (T[pos] != '0'));
			break;
	}
	return ~(memo[pos][status][is_one] = ~ans);
}

int main(void) {
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%212344s", T) != 1) return 1;
	printf("%" PRIu64 "\n", calc(0, NOT_STARTED, 0));
	return 0;
}

/*

XORなら結果は操作の順番によらない (結合法則)
→ XNORも多分そう (予想)

操作回数が奇数 (列の長さが偶数) → 結果はXORと逆
操作回数が偶数 (列の長さが奇数) → 結果はXORと同じ

メモ化探索をする (桁DP風……でもないか)
状態：「未スタート / 奇数 / 偶数」「XORが 0 / 1」
現在の状態がvalid → 結果に1を足す

未スタート → 未スタートのままにする or スタートする (奇数に)
奇数 / 偶数 → 偶数 / 奇数 にする

*/

Submission Info

Judge Result