QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141021#6678. Gem Island 2OvO_ZuoAC ✓676ms320564kbC++142.9kb2023-08-17 08:00:032023-08-17 08:00:04

Judging History

你现在查看的是测评时间为 2023-08-17 08:00:04 的历史记录

  • [2024-04-23 17:45:39]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:707ms
  • 内存:319760kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-08-17 08:00:04]
  • 评测
  • 测评结果:100
  • 用时:676ms
  • 内存:320564kb
  • [2023-08-17 08:00:03]
  • 提交

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],sum[N];
vector<int> prime;
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;
}
int C(int x,int y)
{
	if(x<y) return 0;
	return (ll)frac[x]*inv[y]%mo*inv[x-y]%mo;
}
bool vis[N];
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;
	sum[0]=C(n+m-1,n-1);
	sum[1]=C(n+m-2,n-1);
	for(i=2;i<=m;i++)
	{
		if(!vis[i]) prime.push_back(i);
		for(int t:prime)
		{
			if((ll)t*i>1ll*m) break;
			vis[t*i]=1;
			if(i%t==0) break;
		}
		sum[i]=C(n+m-1-i,n-1);
	}
	for(int t:prime)
		for(i=m/t;i>=1;i--) sum[i]=add(sum[i],sum[i*t]);
}
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=add(sum[0],sum[i]);
		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
哦 T了
第二个sigma预处理出质数,预处理求和,复杂度nloglogn
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

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

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

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

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

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

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

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

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

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

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

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

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

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

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

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

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

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

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

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

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 23ms
memory: 20032kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 564ms
memory: 320564kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

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

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

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

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

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

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 40ms
memory: 31176kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 45ms
memory: 33004kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 18ms
memory: 23408kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 646ms
memory: 318392kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 676ms
memory: 318180kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 673ms
memory: 317668kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

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

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 574ms
memory: 316504kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"