QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#141021 | #6678. Gem Island 2 | OvO_Zuo | AC ✓ | 707ms | 319760kb | C++14 | 2.9kb | 2023-08-17 08:00:03 | 2024-04-23 17:45:39 |
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9988kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 1ms
memory: 10068kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 1ms
memory: 10064kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9924kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 0ms
memory: 9924kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10116kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 1ms
memory: 9924kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 1ms
memory: 9928kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 4ms
memory: 12112kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 34ms
memory: 24448kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 31ms
memory: 26448kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 29ms
memory: 22392kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 575ms
memory: 318240kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 5ms
memory: 12344kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 0ms
memory: 14356kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 0ms
memory: 10244kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 33ms
memory: 32932kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 43ms
memory: 31364kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 28ms
memory: 24596kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 707ms
memory: 318376kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 684ms
memory: 318328kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 693ms
memory: 319760kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 0ms
memory: 10000kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 557ms
memory: 316360kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed