UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213157#2356. Countwucy562149ms70896kbC++2.3kb2024-11-09 21:42:272024-11-09 23:23:26

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,l1,l2;
vector <int> g[100010];
const int md = 1e9 + 7;
int dp[100111][22];
int oud[101111];
int qp(int x,int y) {
	if(y == 0) return 1;
	if(y == 1) return x % md;
	if(y % 2 == 0) {
		int w = qp(x,y / 2);
		return w * w % md;
	}
	else {
		int w = qp(x,y / 2);
		return w * w % md * x % md;
	}
	return 0;
}
int inv(int x) {return qp(x,md - 2) % md;}
int jc[101122];
int invjc[101111];
int played[25][101011];
int ans[101111][25];
signed main(){
	cin >> n >> k >> l1 >> l2;
	/* The first part */
	int ans1 = 0;
	for(int i = 1;i <= n;i ++)
	ans1 += (k % i == 0);
	cout << ans1 << " ";
	/* The second part */
	int ans2 = 0,ans3 = 0;
	jc[0] = 1;
	for(int i = 1;i <= 100500;i ++) 
	jc[i] = jc[i - 1] * i % md,invjc[i] = inv(jc[i]);
	invjc[0] = 1;
	for(int j = 0;j <= 20;j ++) 
	played[j][0] = 1;
	for(int i = 1;i <= 100500;i ++) 
		for(int j = 0;j <= 20;j ++) played[j][i] = jc[i + j - 1] * invjc[i - 1] % md * invjc[j] % md;
	for(int i = 1;i <= 100500;i ++) 
		for(int j = 1;j <= 20;j ++) played[j][i] = (played[j][i - 1] + played[j][i]) % md;
	for(int i = 2;i <= n;i ++){
		for(int j = 1;j * j <= i;j ++){
			if(i % j == 0){
				g[j].push_back(i),oud[i] ++; 
				if(j * j != i && j != 1)
				g[i / j].push_back(i),oud[i] ++; 
			}
		}
	}
	dp[1][0] = 1;
	ans[1][0] = 1;
	queue <int> q;
	q.push(1);
	while(!q.empty()) {
		int now = q.front();
		int sz = g[now].size();
		for(int i = 0;i < sz;i ++){
			int nxt = g[now][i];
			for(int j = 0;j <= 19;j ++){
				dp[nxt][j + 1] = (dp[nxt][j + 1] + dp[now][j]) % md;
				ans[nxt][j + 1] = (ans[now][j] * dp[now][j] % md + ans[nxt][j + 1] + dp[now][j] * nxt % md) % md;
			}
			oud[nxt] --;
			if(oud[nxt] == 0) q.push(nxt);
		} 
		q.pop();
	}
	
	for(int i = 1;i <= n;i ++){
		for(int j = 0;j <= 19;j ++){
			int lst = l1 - j - 1;
			if(lst >= 0) 
			ans2 = (ans2 + dp[i][j] * played[j + 1][lst]) % md;
		}
	}
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= 19;j ++)
			if(l2 - j - 1 >= 0) ans3 = (ans3 + dp[i][j]) % md;
	int ans4 = 0;
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= 19;j ++) 
			if(l2 - j - 1 >= 0) ans4 = (ans4 + ans[i][j]) % md;
	cout << ans2 << " " << ans3 << " " << ans4 << endl;
}

详细

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

Test #1:

score: 7
Acceptable Answer
time: 45ms
memory: 21760kb

input:

5 0 7 3

output:

5 202 6 26

result:

points 0.70 correct wrong correct correct

Test #2:

score: 7
Acceptable Answer
time: 37ms
memory: 21768kb

input:

8 0 9 4

output:

8 1394 14 108

result:

points 0.70 correct wrong correct correct

Test #3:

score: 7
Acceptable Answer
time: 33ms
memory: 21768kb

input:

10 1 10 5

output:

1 3076 19 171

result:

points 0.70 correct wrong correct correct

Test #4:

score: 5
Acceptable Answer
time: 44ms
memory: 21980kb

input:

500 2 996 6

output:

2 736653161 13552 352380403

result:

points 0.50 correct wrong correct wrong

Test #5:

score: 5
Acceptable Answer
time: 32ms
memory: 22120kb

input:

800 233 966 7

output:

2 666060529 32745 848989658

result:

points 0.50 correct wrong correct wrong

Test #6:

score: 5
Acceptable Answer
time: 39ms
memory: 22204kb

input:

1000 666 999 10

output:

12 177426561 48614 138487506

result:

points 0.50 correct wrong correct wrong

Test #7:

score: 5
Acceptable Answer
time: 240ms
memory: 45980kb

input:

50000 2048 98673 100

output:

12 714549025 42179339 357719671

result:

points 0.50 correct wrong correct wrong

Test #8:

score: 5
Acceptable Answer
time: 406ms
memory: 60956kb

input:

80000 65535 25192 50

output:

16 769048462 94939299 263223062

result:

points 0.50 correct wrong correct wrong

Test #9:

score: 5
Acceptable Answer
time: 543ms
memory: 70892kb

input:

100000 23333 99696 12

output:

2 264899073 139356052 943525346

result:

points 0.50 correct wrong correct wrong

Test #10:

score: 5
Acceptable Answer
time: 730ms
memory: 70896kb

input:

100000 89941 99669 6

output:

4 892611662 39157829 136901241

result:

points 0.50 correct wrong correct wrong