ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213157 | #2356. Count | wucy | 56 | 2149ms | 70896kb | C++ | 2.3kb | 2024-11-09 21:42:27 | 2024-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