Submission #72431968

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 <stdlib.h>
#include <string.h>
#include <inttypes.h>
char str[22];
#ifdef OLD_CODE
uint64_t memo[22][1 << 22][2];
uint64_t calc(int pos, int used, int sati) {
  uint64_t ans = 0;
  int char_used = 0;
  int i;
  if (str[pos] == '\0') return 1;
  if (memo[pos][used][sati]) return ~memo[pos][used][sati];
  for (i = 0; str[i] != '\0'; i++) {
    int char_idx = str[i] - 'A';
    if (!((used >> i) & 1) && !((char_used >> char_idx) & 1) && (!sati || str[i] <= str[pos])) {
      char_used |= 1 << char_idx;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

char str[22];

#ifdef OLD_CODE
uint64_t memo[22][1 << 22][2];

uint64_t calc(int pos, int used, int sati) {
	uint64_t ans = 0;
	int char_used = 0;
	int i;
	if (str[pos] == '\0') return 1;
	if (memo[pos][used][sati]) return ~memo[pos][used][sati];

	for (i = 0; str[i] != '\0'; i++) {
		int char_idx = str[i] - 'A';
		if (!((used >> i) & 1) && !((char_used >> char_idx) & 1) && (!sati || str[i] <= str[pos])) {
			char_used |= 1 << char_idx;
			ans += calc(pos + 1, used | (1 << i), sati && str[i] == str[pos]);
		}
	}

	return ~(memo[pos][used][sati] = ~ans);
}
#else
uint64_t data[2][1 << 22][2];

int pc(int x) {
	x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
	x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
	x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
	x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
	x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
	return x;
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	int pa = pc(a), pb = pc(b);
	if (pa != pb) return (pa < pb) - (pa > pb); /* 立っているビット数の降順 */
	return (a > b) - (a < b);
}

int usedlist[1 << 22];
#endif

int main(void) {
#ifndef OLD_CODE
	int pos, used, sati;
	int len, nused, pused;
#endif
	if (scanf("%21s", str) != 1) return 1;
#ifdef OLD_CODE
	printf("%" PRIu64 "\n", calc(0, 0, 1));
#else
	len = (int)strlen(str);
	nused = 1 << len;
	for (used = 0; used < nused; used++) {
		usedlist[used] = used;
	}
	qsort(usedlist, nused, sizeof(*usedlist), cmp);
	for (used = 0; used < nused; used++) {
		for (sati = 0; sati <= 1; sati++) {
			data[len % 2][used][sati] = 1;
		}
	}
	pused = 1;
	for (pos = len - 1; pos >= 0; pos--) {
		for (; pused < nused && pc(usedlist[pused]) == pos; pused++) {
			used = usedlist[pused];
			for (sati = 0; sati <= 1; sati++) {
				uint64_t ans = 0;
				int char_used = 0;
				int i;
				for (i = 0; i < len; i++) {
					int char_idx = str[i] - 'A';
					if (!((used >> i) & 1) && !((char_used >> char_idx) & 1) && (!sati || str[i] <= str[pos])) {
						char_used |= 1 << char_idx;
						ans += data[(pos + 1) % 2][used | (1 << i)][sati && str[i] == str[pos]];
					}
				}
				data[pos % 2][used][sati] = ans;
			}
		}
	}
	printf("%" PRIu64 "\n", data[0][0][1]);
#endif
	return 0;
}

/*

桁DPの要領で、指定の文字列を超えないアナグラムが何個あるかを求める

ZYXWVUTSRQPONMLKJIHG

*/

Submission Info

Judge Result