QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143924#6137. Sub-cycle GraphPhantomThreshold#WA 181ms9460kbC++201.3kb2023-08-21 15:03:152023-08-21 15:03:16

Judging History

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

  • [2023-08-21 15:03:16]
  • 评测
  • 测评结果:WA
  • 用时:181ms
  • 内存:9460kb
  • [2023-08-21 15:03:15]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 510000;
const int mod  = 1e9+7;
const int inv2 = (mod+1)>>1;

int pw(int x,int k)
{
	int re=1;
	for(;k;k>>=1,x=(ll)x*x%mod) if(k&1)
		re=(ll)re*x%mod;
	return re;
}
int inv(int x){ return pw(x,mod-2); }

int fac[maxn],ifac[maxn],ipw2[maxn];
void pre()
{
	fac[0]=1; for(int i=1;i<maxn;i++) fac[i]=(ll)fac[i-1]*i%mod;
	ifac[maxn-1]=inv(fac[maxn-1]);
	for(int i=maxn-2;i>=0;i--) ifac[i]=(ll)ifac[i+1]*(i+1)%mod;
	ipw2[0]=1;
	for(int i=1;i<maxn;i++) ipw2[i]=(ll)ipw2[i-1]*inv2%mod;
}

int C(int i,int j)
{
	if(i<j || j<0 || i<0) return 0;
	return (ll)fac[i]*ifac[j]%mod*ifac[i-j]%mod;
}
int solve(int n,int m)
{
	if(m==0)
	{
		if(n==0) return 1;
		else return 0;
	}
	return (ll)C(n-1-1-2*(m-1)+1+m-2,m-1)*fac[n]%mod*ifac[m]%mod*ipw2[m]%mod;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	//freopen("tmp.in","r",stdin);
	
	pre();
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		int n,m; cin>>n>>m;
		if(m>n-1) 
		{
			cout<<0<<'\n';
			continue;
		}
		int k= n-m;
		
		ll ans=0;
		for(int p=0;p<=k;p++)
		{
		//	ll tans=ans;
			ans+=(ll)C(n,p)*solve( n-p,k-p )%mod;
		//	cerr<<p<<" : "<<ans-tans<<endl;
		}
		cout<<ans%mod<<'\n';
	}
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 9ms
memory: 9392kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

ok 3 number(s): "15 12 90"

Test #2:

score: -100
Wrong Answer
time: 181ms
memory: 9460kb

input:

17446
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11...

output:

1
3
3
0
1
6
15
12
0
1
10
45
90
60
0
1
15
105
375
630
360
0
1
21
210
1155
3465
5040
2520
0
1
28
378
2940
13545
35280
45360
20160
0
1
36
630
6552
42525
170100
393120
453600
181440
0
1
45
990
13230
114345
643545
2286900
4762800
4989600
1814400
0
1
55
1485
24750
273735
2047815
10239075
32848200
62370000...

result:

wrong answer 4th numbers differ - expected: '1', found: '0'