結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー bal4u
提出日時 2019-04-13 22:43:01
言語 C(gnu17)
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -std=gnu17 -Wno-error=implicit-function-declaration -Wno-error=implicit-int -Wno-error=incompatible-pointer-types -Wno-error=int-conversion -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,604 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 281 ms
コンパイル使用メモリ 40,320 KB
最終ジャッジ日時 2026-02-22 02:56:31
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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