Submission #70574656

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>
#define MOD_BY 998244353
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int sub(int a, int b) {
  return b == 0 ? a : add(a, MOD_BY - b);
}
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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MOD_BY 998244353

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

int sub(int a, int b) {
	return b == 0 ? a : add(a, MOD_BY - b);
}

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;
}

int bitcnt(int n) {
	n = (n & 0x55555555) + ((n & 0x2aaaaaaa) >> 1);
	n = (n & 0x33333333) + ((n & 0x4ccccccc) >> 2);
	n = (n & 0x0f0f0f0f) + ((n & 0x70f0f0f0) >> 4);
	n = (n & 0x00ff00ff) + ((n & 0x7f00ff00) >> 8);
	n = (n & 0x0000ffff) + ((n & 0x7fff0000) >> 16);
	return n;
}

int N, L;
char S[24][32];

int masks[24];
int pous[32];

int main(void) {
	int i, j;
	int ans = 0;
	if (scanf("%d%d", &N, &L) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%31s", S[i]) != 1) return 1;
		for (j = 0; S[i][j] != '\0'; j++) {
			int idx = S[i][j] - 'a';
			if (0 <= idx && idx < 26) masks[i] |= 1 << idx;
		}
	}
	for (i = 0; i < 32; i++) {
		pous[i] = pou(i, L);
	}
	for (i = 1; i < (1 << N); i++) {
		int mask = 0x7fffffff;
		for (j = 0; j < N; j++) {
			if ((i >> j) & 1) mask &= masks[j];
		}
		ans = (bitcnt(i) % 2 == 0 ? sub : add)(ans, pous[bitcnt(mask)]);
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result