UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213139#2356. CountX_X86751ms37128kbC++1.4kb2024-11-09 21:12:192024-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;
}

详细

小提示:点击横条可展开更详细的信息

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