Submission #65499601

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 <string.h>
#define MOD_BY 998244353
#define INV_4 748683265
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return (int)((long long)a * b % MOD_BY);
}
int pou(int a, int b) {
  int r = 1;
  while (b > 0) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b >>= 1;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <string.h>

#define MOD_BY 998244353
#define INV_4 748683265

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int pou(int a, int b) {
	int r = 1;
	while (b > 0) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}

char N[114514];

int main(void) {
	int i;
	int mult, mult_delta;
	int ans, ans_delta;
	int len;
	if (scanf("%114513s", N) != 1) return 1;
	len = (int)strlen(N);

	if (len == 1 && N[0] == '1') {
		/* N == 1 */
		puts("1");
		return 0;
	}

	/* 1 << (N - 2) を求める */
	mult = 1;
	mult_delta = 2;
	for (i = len - 1; i >= 0; i--) {
		mult = mul(mult, pou(mult_delta, N[i] - '0'));
		mult_delta = pou(mult_delta, 10);
	}
	mult = mul(mult, INV_4);

	/* (1 << (N - 2)) * N を求める */
	ans = 0;
	ans_delta = mult;
	for (i = len - 1; i >= 0; i--) {
		ans = add(ans, mul(ans_delta, N[i] - '0'));
		ans_delta = mul(ans_delta, 10);
	}

	printf("%d\n", add(ans, mult));
	return 0;
}

/*

消灯しているところを点灯させても有利にならない……多分
よって、実質連続して点灯しているグループが何組あるか

int func(int left, int on) {
	int ans = 0;
	if (left <= 0) return 0;
	// 消灯
	ans += func(left - 1, 0);
	// 点灯
	ans += func(left - 1, 1);
	// 点灯：ここで新たにボタンを押す
	if (!on) ans += 1 << (left - 1);
	return ans;
}

[left][0] = [left-1][0] + [left-1][1]
[left][1] = [left-1][0] + [left-1][1] + (1 << (left - 1))

そこ始まりのボタンを押すパターン数
→ そこが点灯、1個左が消灯、それ以外は任意
→ 1 << (N - 2)

ただし、一番左については 1 << (N - 1)
これは (1 << (N - 2)) * 2 と表せる

よって、答えは (1 << (N - 2)) * N + (1 << (N - 2))

*/

Submission Info

Judge Result