ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213139 | #2356. Count | X_X | 86 | 751ms | 37128kb | C++ | 1.4kb | 2024-11-09 21:12:19 | 2024-11-09 23:19:07 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+3,MOD=1e9+7;
int n,k,l1,l2,ans1;
LL ans2,ans3,ans4;
LL p[N],q[N];
LL f[N][22],g[N][22];
void upd(LL &x,LL y){
(x+=y)%=MOD;
}
LL qpow(LL x,int y=MOD-2){
LL cnt=1;
while(y){
if(y&1) cnt=cnt*x%MOD;
x=x*x%MOD;
y>>=1;
}
return cnt;
}
LL C(int x,int y){
if(x<0||y<0||x<y) return 0;
return p[x]*q[y]%MOD*q[x-y]%MOD;
}
int Main()
{
scanf("%d%d%d%d",&n,&k,&l1,&l2);
p[0]=1;for(int i=1;i<=N-3;i++) p[i]=p[i-1]*i%MOD;
q[N-3]=qpow(p[N-3]);for(int i=N-3;i>=1;i--) q[i-1]=q[i]*i%MOD;
for(int i=1;i<=k;i++) if(k%i==0) ans1++;
f[1][1]=1,g[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j*j<=i;j++)
if(i%j==0){
for(int l=0;l<20;l++)
upd(f[i][l+1],f[j][l]),upd(g[i][l+1],g[j][l]+f[j][l]*i);
if(j==1||j*j==i) continue;
for(int l=0;l<20;l++)
upd(f[i][l+1],f[i/j][l]),upd(g[i][l+1],g[i/j][l]+f[i/j][l]*i);
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<20;j++)
upd(f[0][j+1],f[i][j]),upd(g[0][j+1],g[i][j]);
for(int i=1;i<20;i++){
//cout<<i<<' '<<f[0][i]<<' '<<g[0][i]<<' '<<C(l1,i-1)<<endl;
upd(ans2,f[0][i]*C(l1,i-1));
if(i<=l2+1) upd(ans3,f[0][i]);
upd(ans4,g[0][i]);
}
printf("%d %lld %lld %lld\n",ans1,ans2,ans3,ans4);
return 0;
}
int main()
{
int Case=1;
while(Case--) Main();
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 7
Acceptable Answer
time: 0ms
memory: 2760kb
input:
5 0 7 3
output:
0 126 6 26
result:
points 0.70 wrong correct correct correct
Test #2:
score: 7
Acceptable Answer
time: 0ms
memory: 2760kb
input:
8 0 9 4
output:
0 807 14 108
result:
points 0.70 wrong correct correct correct
Test #3:
score: 10
Accepted
time: 0ms
memory: 2756kb
input:
10 1 10 5
output:
1 1585 19 171
result:
points 1.0 correct correct correct correct
Test #4:
score: 8
Acceptable Answer
time: 0ms
memory: 2928kb
input:
500 2 996 6
output:
2 370442183 13552 6303307
result:
points 0.80 correct correct correct wrong
Test #5:
score: 8
Acceptable Answer
time: 2ms
memory: 3032kb
input:
800 233 966 7
output:
2 31028437 32745 23491266
result:
points 0.80 correct correct correct wrong
Test #6:
score: 10
Accepted
time: 4ms
memory: 3100kb
input:
1000 666 999 10
output:
12 494787167 48614 41846205
result:
points 1.0 correct correct correct correct
Test #7:
score: 10
Accepted
time: 133ms
memory: 19944kb
input:
50000 2048 98673 100
output:
12 795207831 42179339 148036147
result:
points 1.0 correct correct correct correct
Test #8:
score: 10
Accepted
time: 246ms
memory: 30256kb
input:
80000 65535 25192 50
output:
16 857081183 94939299 733768189
result:
points 1.0 correct correct correct correct
Test #9:
score: 8
Acceptable Answer
time: 196ms
memory: 37128kb
input:
100000 23333 99696 12
output:
2 921281341 139356052 499158596
result:
points 0.80 correct correct correct wrong
Test #10:
score: 8
Acceptable Answer
time: 170ms
memory: 37128kb
input:
100000 89941 99669 6
output:
4 684798865 39157829 499158596
result:
points 0.80 correct correct correct wrong