結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー bal4u
提出日時 2019-04-13 22:39:12
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,578 bytes
コンパイル時間 595 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 11:22:10
合計ジャッジ時間 973 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
	printf("%d\n", ans-1);
	return 0;
}
0