QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140694#6678. Gem Island 2OvO_ZuoTL 327ms238256kbC++142.5kb2023-08-16 17:05:152023-08-16 17:05:17

Judging History

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

  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-08-16 17:05:17]
  • 评测
  • 测评结果:TL
  • 用时:327ms
  • 内存:238256kb
  • [2023-08-16 17:05:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e7+5,mo=998244353;
int n,m,r,ans=0;
int frac[N],inv[N];
int add(int x,int y){ x+=y;return x>=mo?x-mo:x;}
int mi(int x,int y)
{
	int res=1;
	for(;y;y>>=1,x=(ll)x*x%mo)
		if(y&1) res=(ll)res*x%mo;
	return res;
}
void init()
{
	int i;
	frac[0]=1;
	for(i=1;i<=n+m;i++) frac[i]=(ll)frac[i-1]*i%mo;
	inv[n+m]=mi(frac[n+m],mo-2);
	for(i=n+m-1;i>=0;--i) inv[i]=(ll)inv[i+1]*(i+1)%mo;
}
int C(int x,int y)
{
	if(x<y) return 0;
	return (ll)frac[x]*inv[y]%mo*inv[x-y]%mo;
}
int main()
{
	scanf("%d%d%d",&n,&m,&r);
	int i,j;
	init();
	int tv=0;
	for(i=1;i<=m+1;i++)
		ans=add(ans,(ll)n*C(n+m-i,n-1)%mo);
	int tvv;
	for(i=2;i<=n;i++)
	{
		tv=0;
		for(j=0;j<=m;j+=i) tv=add(tv,C(n+m-1-j,n-1));
		tvv=tv;
		tv=(ll)tv*C(n,i)%mo*C(i-2,min(i,r)-1)%mo;
		if((i-min(i,r))%2) tv=mo-tv;
		ans=add(ans,tv);
	}
	ans=(ll)ans*mi(C(n+m-1,n-1),mo-2)%mo;
	printf("%d\n",ans);
	return 0;
}
/*
sigma(a[i]) = sigma(j=0~mx){sigma(i=1~n){ [j < a[i]] }}
枚举j,求期望有 x 个数满足 a[i] > j
ans += min(x,r)
设 f[i] 表示恰好有 i 个位置 >v 的方案数,g[i] 表示钦定有 i 个位置 >v 的方案数
g[i] = C(n,i) * C( m+n-1-(v-1)*i,n-1 )
g[i] = sigma(j>=i){ C(j,i)*f[j] }
f[i] = sigma(j>=i){ (-1)^(j-i) * C(j,i) * g[j] }
tans = sigma(i<=n){ f[i]/总方案数 * min(i,r) }
复杂度 n^3
组合意义令人痛苦,于是尝试代数推导
将g[i]代入最终的答案式中,得到(忽略总方案数)
tans = sigma(i<=n){ sigma(j>=i){ (-1)^(j-i) * C(j,i) *g[j] } * min(i,r) } 
	= sigma(j<=n){ g[j] * sigma(i<=j){ min(i,r) * C(j,i) * (-1)^(j-i) } }
g数组容易O(1)计算,考虑剩下部分
sigma(i<=n){ min(i,r) * C(n,i) *(-1)^(n-i) }
= sigma(1<=j<=r){ sigma(i>=j){ C(n,i) * (-1)^(n-i) } }
考虑第二个sigma
sigma(i>=j){ C(n,i) * (-1)^(n-i) } 
= sigma(i>=j){ C(n-1,i) * (-1)^(n-i) } + sigma(i>=j){ C(n-1,i-1) * (-1)^(n-i) }
= sigma(j<=i<=n-1){ C(n-1,i) * (-1)^(n-i) } + sigma(j-1<=i<=n-1){ C(n-1,i) * (-1)^(n-i-1) }
= C(n-1,i) * (-1)^(n-i-1)
代回原式,得
= sigma(0<=i<r){ C(n-1,i) * (-1)^(n-i-1) }
= sigma(i<r){ C(n-2,i) * (-1)^(n-i-1) } + sigma(i<r){ C(n-2,i-1) * (-1)^(n-i-1) }
= C(n-2,r-1) * (-1)^(n-r+2)

此时,仍需枚举 v
ans = sigma(v>0){ sigma(i<=n){ g(v)[i] * C(i-2,min(i,r)-1) * (-1)^(i-min(i,r)) } }
	= sigma(i=1~n){ C(n,i)*C(i-2,min(i,r)-1)*(-1)^(i-min(i,r)) * sigma(i|t){ C(n+m-1-t,n-1) } } 
预处理出组合数,只遍历 i 的倍数,复杂度 nlogn
*/

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5720kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5712kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5704kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5664kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5764kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5800kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 1ms
memory: 5652kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 0ms
memory: 5944kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 4ms
memory: 6396kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 34ms
memory: 23636kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 42ms
memory: 20256kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 32ms
memory: 19068kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 327ms
memory: 238256kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 2ms
memory: 6492kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 1ms
memory: 10384kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 3ms
memory: 6100kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 29ms
memory: 23604kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 101ms
memory: 22868kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 64ms
memory: 15412kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: -100
Time Limit Exceeded

input:

15000000 14999999 514

output:


result: