QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#90892	#5749. Directed Vertex Cacti	He_Ren	AC ✓	21ms	19352kb	C++14	913b	2023-03-26 02:21:06	2023-03-26 02:21:09

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-26 02:21:09]
评测

测评结果：AC
用时：21ms
内存：19352kb

查看

[2023-03-26 02:21:06]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e6 + 5;
const int mod = 1e9 + 9;

inline void add_mod(int &a,int b){ a+=b; if(a>=mod) a-=mod;}

inline ll pw(ll a,ll b)
{
	ll res = 1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod; b>>=1;
	}
	return res;
}

const int MAXF = MAXN;
ll fac[MAXF], inv[MAXF];
inline ll C(int n,int m){ return n<0||m<0||n<m? 0: fac[n] * inv[m] %mod * inv[n-m] %mod;}

int main(void)
{
	fac[0] = 1;
	for(int i=1; i<MAXF; ++i)
		fac[i] = fac[i-1] * i %mod;
	inv[MAXF-1] = pw(fac[MAXF-1], mod-2);
	for(int i=MAXF-2; i>=0; --i)
		inv[i] = inv[i+1] * (i+1) %mod;
	
	int n,m;
	scanf("%d%d",&n,&m);
	
	ll ans = fac[n];
	
	ll t = (ll)n * (n-1) / 2;
	for(int i=1; i<=m; ++i)
		ans = ans * (t%mod - i + 1 + mod) %mod;
	ans = ans * inv[m] %mod;
	
	printf("%lld\n",ans);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 11ms

memory: 19196kb

input:

3 1

output:

result:

ok 1 number(s): "18"

Test #2:

score: 0

Accepted

time: 15ms

memory: 19132kb

input:

4 4

output:

result:

ok 1 number(s): "360"

Test #3:

score: 0

Accepted

time: 21ms

memory: 19348kb

input:

39847 348708

output:

983575456

result:

ok 1 number(s): "983575456"

Test #4:

score: 0

Accepted

time: 11ms

memory: 19344kb

input:

1 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 15ms

memory: 19112kb

input:

3 2

output:

result:

ok 1 number(s): "18"

Test #6:

score: 0

Accepted

time: 8ms

memory: 19312kb

input:

3 3

output:

result:

ok 1 number(s): "6"

Test #7:

score: 0

Accepted

time: 12ms

memory: 19212kb

input:

3 4

output:

result:

ok 1 number(s): "0"

Test #8:

score: 0

Accepted

time: 7ms

memory: 19172kb

input:

3 1000000

output:

result:

ok 1 number(s): "0"

Test #9:

score: 0

Accepted

time: 9ms

memory: 19136kb

input:

4 1

output:

result:

ok 1 number(s): "144"

Test #10:

score: 0

Accepted

time: 17ms

memory: 19112kb

input:

4 2

output:

result:

ok 1 number(s): "360"

Test #11:

score: 0

Accepted

time: 7ms

memory: 19092kb

input:

4 3

output:

result:

ok 1 number(s): "480"

Test #12:

score: 0

Accepted

time: 11ms

memory: 19352kb

input:

4 5

output:

result:

ok 1 number(s): "144"

Test #13:

score: 0

Accepted

time: 9ms

memory: 19140kb

input:

4 6

output:

result:

ok 1 number(s): "24"

Test #14:

score: 0

Accepted

time: 12ms

memory: 19140kb

input:

5 1

output:

result:

ok 1 number(s): "1200"

Test #15:

score: 0

Accepted

time: 11ms

memory: 19204kb

input:

5 2

output:

result:

ok 1 number(s): "5400"

Test #16:

score: 0

Accepted

time: 4ms

memory: 19108kb

input:

5 3

output:

result:

ok 1 number(s): "14400"

Test #17:

score: 0

Accepted

time: 21ms

memory: 19176kb

input:

5 4

output:

result:

ok 1 number(s): "25200"

Test #18:

score: 0

Accepted

time: 7ms

memory: 19196kb

input:

5 5

output:

result:

ok 1 number(s): "30240"

Test #19:

score: 0

Accepted

time: 10ms

memory: 19348kb

input:

5 6

output:

result:

ok 1 number(s): "25200"

Test #20:

score: 0

Accepted

time: 14ms

memory: 19124kb

input:

5 7

output:

result:

ok 1 number(s): "14400"

Test #21:

score: 0

Accepted

time: 11ms

memory: 19200kb

input:

5 8

output:

result:

ok 1 number(s): "5400"

Test #22:

score: 0

Accepted

time: 4ms

memory: 19176kb

input:

5 9

output:

result:

ok 1 number(s): "1200"

Test #23:

score: 0

Accepted

time: 8ms

memory: 19172kb

input:

5 10

output:

result:

ok 1 number(s): "120"

Test #24:

score: 0

Accepted

time: 14ms

memory: 19192kb

input:

1000 1

output:

533396879

result:

ok 1 number(s): "533396879"

Test #25:

score: 0

Accepted

time: 9ms

memory: 19140kb

input:

1000 100

output:

199484478

result:

ok 1 number(s): "199484478"

Test #26:

score: 0

Accepted

time: 18ms

memory: 19132kb

input:

1000 10000

output:

656650652

result:

ok 1 number(s): "656650652"

Test #27:

score: 0

Accepted

time: 14ms

memory: 19140kb

input:

1000 1000000

output:

result:

ok 1 number(s): "0"

Test #28:

score: 0

Accepted

time: 19ms

memory: 19192kb

input:

535164 619302

output:

721871396

result:

ok 1 number(s): "721871396"

Test #29:

score: 0

Accepted

time: 14ms

memory: 19112kb

input:

1000000 1000000

output:

580712335

result:

ok 1 number(s): "580712335"

Test #30:

score: 0

Accepted

time: 5ms

memory: 19132kb

input:

1000000 234534

output:

546630669

result:

ok 1 number(s): "546630669"

Test #31:

score: 0

Accepted

time: 10ms

memory: 19128kb

input:

234523 1000000

output:

127869098

result:

ok 1 number(s): "127869098"

Test #32:

score: 0

Accepted

time: 13ms

memory: 19352kb

input:

44722 10000

output:

result:

ok 1 number(s): "0"