結果

問題 No.171 スワップ文字列(Med)
ユーザー bal4ubal4u
提出日時 2019-04-13 22:43:01
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 1,000 ms
コード長 1,604 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 11:22:14
合計ジャッジ時間 1,062 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'ins':
main.c:10:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   10 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:17: note: in expansion of macro 'gc'
   17 |         do *s = gc();
      |                 ^~

ソースコード

diff # 

// yukicoder: No.171 スワップ文字列(Med)
// 2019.4.13 bal4u

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

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int ins(char *s)  // 文字列の入力　スペース以下の文字で入力終了
{
	char *p = s;
	do *s = gc();
	while (*s++ > ' ');
	*--s = 0;
	return s - p;
}

#define MAX 1005
#define MOD 573
char s[MAX]; int w;
int inv[MAX];
int p3, p191;    // 3^p3, 191^p191    MOD 573 = 3 * 191
int si = 1, bo = 1;

void fact(int n)
{
	int i, k;
	for (i = 2; i <= n; i++) {
		k = i;
		while (k % 191 == 0) k /= 191, p191++;
		while (k % 3 == 0) k /= 3, p3++;
		si = (si * k) % MOD;
	}
}

int extended_gcd(int a, int b, int *x, int *y)
{
	int d;
	if (b == 0) { *x = 1; *y = 0; return a; }
	d = extended_gcd(b, a % b, y, x);
	*y -= a / b * (*x);
	return d;
}

int inverse(int a)
{
	int x, y;
	if (inv[a]) return inv[a];
	extended_gcd(a, MOD, &x, &y);
	return inv[a] = (x + MOD) % MOD;
}

void factinv(int n)
{
	int i, k;
	for (i = 2; i <= n; i++) {
		k = i;
		while (k % 191 == 0) k /= 191, p191--;
		while (k % 3 == 0) k /= 3, p3--;
		bo = (bo * inverse(k)) % MOD;
	}
}

int cmp(const void *a, const void *b) { return *(char *)a - *(char *)b; }

int main()
{
	int i, k, ans;

	w = ins(s);
	fact(w);
	qsort(s, w, sizeof(char), cmp);
	i = 1; while (i <= w) {
		k = 1;
		while (s[i] == s[i - 1]) i++, k++;
		factinv(k);
		i++;
	}
	ans = (si * bo) % MOD;
	while (p3--) ans = (ans * 3) % MOD;
	while (p191--) ans = (ans * 191) % MOD;
	if (--ans < 0) ans += MOD;
	printf("%d\n", ans);
	return 0;
}
0