結果

問題 No.117 組み合わせの数
ユーザー Ysmr_RyYsmr_Ry
提出日時 2015-01-05 02:05:15
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,059 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 27,740 KB
実行使用メモリ 10,644 KB
最終ジャッジ日時 2023-09-03 21:59:52
合計ジャッジ時間 1,382 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstring>
#include<cctype>
#define rep(i,a) for(int i=0;i<(a);++i)

typedef long long ll;

const ll mod = 1000000007;

int T;

ll fact[1000001];

ll extgcd( ll a, ll b, ll &x, ll &y )
{
	int d = b;

	if( b )
	{
		d = extgcd( b, a%b, y, x );
		y -= a/b*x;
	}
	else
		x = 1, y = 0;

	return d;
}

ll divMod( ll a, ll b, ll m )
{
	ll x, y;
	extgcd( b, m, x, y );

	return ((a*x)%m+m)%m;
}

ll perm( int n, int r )
{ return n<r?0:divMod( fact[n], fact[n-r], mod ); }

ll comb( int n, int r )
{ return n<r?0:divMod( perm(n,r), fact[r], mod ); }

ll homo( int n, int r )
{ return comb( n+r-1, r ); }

int read( char S[], int &p )
{
	int q = 0, len = strlen(S);

	while( p < len && isdigit( S[p] ) )
	{
		q *= 10;
		q += S[p]-'0';
		++p;
	}

	return q;
}

int main()
{
	fact[0] = 1;
	rep( i, 1000000 )
		fact[i+1] = (i+1)*fact[i] % mod;

	scanf( "%d", &T );
	rep( i, T )
	{
		char S[21];
		scanf( "%s", S );

		int p = 2;
		int n = read(S, p), r = read(S, ++p);

		printf( "%lld\n", (*S=='C'?comb:*S=='P'?perm:homo)(n, r) );
	}

	return 0;
}
0