Submission #6404341


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template <class T>inline T updmax(T &a, T b) { return a = max(a, b); }
template <class T>inline T updmin(T &a, T b) { return a = min(a, b); }

template <unsigned long long mod> class modint {
public:
	unsigned long long v;
	modint(const long long x = 0) : v(x % mod) {}
	modint operator+(const modint rhs) { return modint(*this) += rhs; }
	modint operator-(const modint rhs) { return modint(*this) -= rhs; }
	modint operator*(const modint rhs) { return modint(*this) *= rhs; }
	modint operator/(const modint rhs) { return modint(*this) /= rhs; }
	modint operator-() { return modint(mod-this->v); }
	modint &operator+=(const modint rhs) {
		v += rhs.v;
		if (v >= mod)v -= mod;
		return *this;
	}
	modint &operator-=(const modint rhs) {
		if (v < rhs.v)v += mod;
		v -= rhs.v;
		return *this;
	}
	modint &operator*=(const modint rhs) {
		v = v * rhs.v % mod;
		return *this;
	}
	modint inverse(modint a) {
		unsigned long long exp = mod - 2;
		modint ret(1ULL);
		while (exp) {
			if (exp % 2) {
				ret *= a;
			}
			a *= a;
			exp >>= 1;
		}
		return ret;
	}
	modint &operator/=(modint rhs) {
		(*this) *= inverse(rhs);
		return *this;
	}
};

template<class T>
T fastpow(T a, long long p){
	T tmp = a;
	T ret = 1;
	while(p){
		if(p & 1)ret *= tmp;
		p >>= 1;
		tmp = tmp * tmp;
	}
	return ret;
}

const int MOD = 998244353;
using mint = modint<MOD>;

char s[200005];
mint dp[200005][3][3];

void dfs(set<string> &ss, string c){
	ss.insert(c);
	for(int i=0; i < c.length()-1; i++){
		if(c[i] == c[i+1])continue;
		for(int j=0; j < 3; j++){
			char ch = 'a' + j;
			if(c[i] != ch && c[i+1] != ch){
				char ch0 = ch, ch1 = ch;
				swap(c[i], ch0);
				swap(c[i+1], ch1);
				if(ss.end() == ss.find(c))dfs(ss, c);
				swap(c[i], ch0);
				swap(c[i+1], ch1);
			}
		}
	}
}

int main()
{
	scanf("%s", &s);
	int n = strlen(s);
	bool allsame = true, same = false;
	for(int i=0; i < n-1; i++){
		if(s[i] == s[i+1])same = true;
		else allsame = false;
	}
	if(allsame)printf("1\n");
	if(n <= 4){
		set<string> ss;
		dfs(ss, string(s));
		printf("%d\n", ss.size());
	}else{
		dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;
		for(int i=0; i < n-1; i++){
			for(int j=0; j < 3; j++){
				for(int k=0; k < 3; k++){
					for(int l=0; l < 3; l++){
						if(l != k)dp[i+1][(j+l)%3][l] += dp[i][j][k];
					}
				}
			}
		}
		int sum = 0;
		for(int i=0; i < n; i++)sum += s[i] - 'a';
		sum %= 3;
		mint ret = fastpow(mint{3}, n-1) - dp[n-1][sum][0] - dp[n-1][sum][1] - dp[n-1][sum][2] + (1 - same);
		printf("%lld\n", ret.v);
	}
	return 0;
}

Submission Info

Submission Time
Task F - Normalization
User UminchuR
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2686 Byte
Status WA
Exec Time 20 ms
Memory 14464 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:16: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[200005]’ [-Wformat=]
  scanf("%s", &s);
                ^
./Main.cpp:98:27: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::set<std::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
   printf("%d\n", ss.size());
                           ^
./Main.cpp:87:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", &s);
                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 66
WA × 12
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt, s4.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt WA 6 ms 14336 KB
02.txt AC 6 ms 14336 KB
03.txt AC 6 ms 14336 KB
04.txt AC 6 ms 14336 KB
05.txt AC 6 ms 14336 KB
06.txt AC 6 ms 14336 KB
07.txt AC 6 ms 14336 KB
08.txt AC 6 ms 14336 KB
09.txt AC 6 ms 14336 KB
10.txt AC 6 ms 14336 KB
11.txt AC 6 ms 14336 KB
12.txt AC 6 ms 14336 KB
13.txt AC 6 ms 14336 KB
14.txt WA 6 ms 14336 KB
15.txt AC 6 ms 14336 KB
16.txt AC 6 ms 14336 KB
17.txt AC 6 ms 14336 KB
18.txt AC 6 ms 14336 KB
19.txt AC 6 ms 14336 KB
20.txt AC 6 ms 14336 KB
21.txt AC 6 ms 14336 KB
22.txt AC 6 ms 14336 KB
23.txt AC 6 ms 14336 KB
24.txt AC 6 ms 14336 KB
25.txt AC 6 ms 14336 KB
26.txt AC 6 ms 14336 KB
27.txt WA 6 ms 14336 KB
28.txt WA 6 ms 14336 KB
29.txt AC 6 ms 14336 KB
30.txt AC 6 ms 14336 KB
31.txt AC 6 ms 14336 KB
32.txt WA 6 ms 14336 KB
33.txt AC 6 ms 14336 KB
34.txt AC 6 ms 14336 KB
35.txt AC 6 ms 14336 KB
36.txt WA 6 ms 14336 KB
37.txt AC 17 ms 14464 KB
38.txt AC 7 ms 14336 KB
39.txt AC 7 ms 14336 KB
40.txt AC 11 ms 14336 KB
41.txt AC 19 ms 14464 KB
42.txt AC 18 ms 14464 KB
43.txt AC 14 ms 14464 KB
44.txt AC 19 ms 14464 KB
45.txt AC 13 ms 14464 KB
46.txt AC 20 ms 14464 KB
47.txt AC 16 ms 14464 KB
48.txt AC 13 ms 14464 KB
49.txt AC 12 ms 14336 KB
50.txt AC 10 ms 14336 KB
51.txt AC 13 ms 14464 KB
52.txt AC 8 ms 14336 KB
53.txt AC 16 ms 14464 KB
54.txt AC 9 ms 14336 KB
55.txt AC 14 ms 14464 KB
56.txt AC 15 ms 14464 KB
57.txt AC 7 ms 14336 KB
58.txt AC 18 ms 14464 KB
59.txt AC 7 ms 14336 KB
60.txt AC 15 ms 14464 KB
61.txt WA 10 ms 14336 KB
62.txt WA 10 ms 14336 KB
63.txt WA 18 ms 14464 KB
64.txt WA 18 ms 14464 KB
65.txt WA 16 ms 14464 KB
66.txt WA 16 ms 14464 KB
67.txt AC 19 ms 14464 KB
68.txt AC 19 ms 14464 KB
69.txt AC 19 ms 14464 KB
70.txt AC 19 ms 14464 KB
71.txt AC 19 ms 14464 KB
72.txt AC 19 ms 14464 KB
73.txt AC 19 ms 14464 KB
74.txt AC 20 ms 14464 KB
s1.txt AC 6 ms 14336 KB
s2.txt AC 6 ms 14336 KB
s3.txt AC 6 ms 14336 KB
s4.txt AC 6 ms 14336 KB