QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141021 | #6678. Gem Island 2 | OvO_Zuo | AC ✓ | 676ms | 320564kb | C++14 | 2.9kb | 2023-08-17 08:00:03 | 2023-08-17 08:00:04 |
Judging History
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"