NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #213182 | #2356. Count | fddwd | 72 | 536ms | 21124kb | C++11 | 1.1kb | 2024-11-09 22:26:57 | 2024-11-09 23:28:25 |
answer
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define MAXN 100010
int n,k,l1,l2;
ll dp[1010][1010],f[1010][1010];
vector<int>g[MAXN],h[MAXN];
int main(){
cin>>n>>k>>l1>>l2;
for(int i=1;i<=n;++i)for(int j=i;j<=n;j+=i)
g[i].push_back(j),h[j].push_back(i);
if(!k) cout<<n<<" ";
else cout<<h[k].size()<<" ";
if(n<=1000){
dp[1][1]=1;
for(int i=2;i<=l1;++i)for(int j=1;j<=n;++j)for(int v:h[j])
(dp[i][j]+=dp[i-1][v])%=mod;
ll ans=0;
for(int i=1;i<=l1;++i)for(int j=1;j<=n;++j) (ans+=dp[i][j])%=mod;
cout<<ans<<" ";
}else cout<<0<<" ";
if(n<=1000){
memset(dp,0,sizeof(dp)),dp[1][1]=1;
for(int i=2;i<=l2;++i)for(int j=1;j<=n;++j)for(int v:h[j])if(v!=j)
(dp[i][j]+=dp[i-1][v])%=mod;
ll ans=0;
for(int i=1;i<=l2;++i)for(int j=1;j<=n;++j) (ans+=dp[i][j])%=mod;
cout<<ans<<" ";
}else cout<<0<<" ";
if(n<=1000){
f[1][1]=1;
for(int i=2;i<=l2;++i)for(int j=1;j<=n;++j)for(int v:h[j])if(v!=j)
(f[i][j]+=f[i-1][v]+dp[i-1][v]*j)%=mod;
ll ans=0;
for(int i=1;i<=l2;++i)for(int j=1;j<=n;++j) (ans+=f[i][j])%=mod;
cout<<ans<<endl;
}else cout<<0<<endl;
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 7ms
memory: 13924kb
input:
5 0 7 3
output:
5 126 6 26
result:
points 1.0 correct correct correct correct
Test #2:
score: 10
Accepted
time: 0ms
memory: 13928kb
input:
8 0 9 4
output:
8 807 14 108
result:
points 1.0 correct correct correct correct
Test #3:
score: 10
Accepted
time: 3ms
memory: 13932kb
input:
10 1 10 5
output:
1 1585 19 171
result:
points 1.0 correct correct correct correct
Test #4:
score: 10
Accepted
time: 13ms
memory: 14000kb
input:
500 2 996 6
output:
2 370442183 13552 5619309
result:
points 1.0 correct correct correct correct
Test #5:
score: 10
Accepted
time: 34ms
memory: 14052kb
input:
800 233 966 7
output:
2 31028437 32745 22476650
result:
points 1.0 correct correct correct correct
Test #6:
score: 10
Accepted
time: 59ms
memory: 14096kb
input:
1000 666 999 10
output:
12 494787167 48614 41846205
result:
points 1.0 correct correct correct correct
Test #7:
score: 3
Acceptable Answer
time: 36ms
memory: 13104kb
input:
50000 2048 98673 100
output:
12 0 0 0
result:
points 0.30 correct wrong wrong wrong
Test #8:
score: 3
Acceptable Answer
time: 86ms
memory: 17952kb
input:
80000 65535 25192 50
output:
16 0 0 0
result:
points 0.30 correct wrong wrong wrong
Test #9:
score: 3
Acceptable Answer
time: 143ms
memory: 21120kb
input:
100000 23333 99696 12
output:
2 0 0 0
result:
points 0.30 correct wrong wrong wrong
Test #10:
score: 3
Acceptable Answer
time: 155ms
memory: 21124kb
input:
100000 89941 99669 6
output:
4 0 0 0
result:
points 0.30 correct wrong wrong wrong
