結果

問題 No.117 組み合わせの数
ユーザー Ysmr_RyYsmr_Ry
提出日時 2015-01-05 02:16:32
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,224 bytes
コンパイル時間 641 ms
コンパイル使用メモリ 28,076 KB
実行使用メモリ 18,428 KB
最終ジャッジ日時 2023-09-03 22:01:01
合計ジャッジ時間 1,971 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

typedef long long ll;

const ll mod = 1000000007;

int T;

ll fact[1000001], factinv[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:fact[n]*factinv[n-r] % mod; }

ll comb( int n, int r )
{ return n<r?0:perm(n,r)*factinv[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;

	factinv[1000000] = divMod( 1, fact[1000000], mod );
	repd( i, 1000000-1 )
		factinv[i] = (factinv[i+1]*(i+1)) % 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