QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #232158 | #7063. Space Station | Ronbogo# | TL | 30ms | 4712kb | C++20 | 704b | 2023-10-29 22:37:01 | 2023-10-29 22:37:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long N=1e9+7;
int n,a[100010],cn[51];
long long ans[100010],t1,an;
void dfs(int p){
if (p>=a[n]){
int t=0;
for (int i=1;i<=50;i++)t+=cn[i];
an=(an+t1*ans[t]%N)%N;
return ;
}
for (int i=1;i<=p;i++)
if (cn[i]){
long long tt=t1;t1=1ll*t1*cn[i]%N;cn[i]--;
dfs(p+i);
t1=tt;cn[i]++;
}
}
int main(){
cin>>n;
for (int i=0;i<=n;i++)cin>>a[i];
// memset(cn,0,sizeof(cn));
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)cn[a[i]]++;
ans[1]=1;
for (int i=2;i<=n;i++){
ans[i]=ans[i-1]*i%N;//cout<<ans[i]<<"\n";
}
t1=1;an=0;dfs(a[0]);
for (int i=n-cn[0]+1;i<=n;i++)an=1ll*an*i%N;
cout<<an;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
3 2 1 2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 1 1 1 1 2 3
output:
54
result:
ok single line: '54'
Test #3:
score: 0
Accepted
time: 14ms
memory: 4668kb
input:
100000 47 25 43 22 17 6 15 17 45 4 14 34 46 22 0 8 2 48 41 6 49 42 21 25 48 43 2 17 27 25 38 31 39 48 13 49 24 30 36 19 29 47 48 1 4 5 12 9 21 39 30 21 8 4 9 45 18 0 3 29 26 18 24 39 31 49 22 4 46 21 27 11 11 7 8 3 26 25 29 4 1 21 34 4 44 39 13 26 33 44 5 17 10 32 37 25 44 34 17 14 40 32 27 39 41 6 ...
output:
268605493
result:
ok single line: '268605493'
Test #4:
score: 0
Accepted
time: 30ms
memory: 4712kb
input:
100000 35 39 20 34 18 5 21 21 45 38 48 44 50 42 35 23 21 18 24 9 40 18 16 20 41 27 25 4 0 5 9 7 39 26 47 13 18 27 43 45 31 20 45 39 7 29 4 41 6 39 4 27 7 24 42 10 49 21 9 21 33 12 7 2 24 13 47 11 43 25 8 18 5 14 44 9 14 50 50 19 6 18 45 41 0 27 20 44 17 19 5 26 38 19 1 30 10 32 46 4 24 27 28 32 27 3...
output:
590621358
result:
ok single line: '590621358'
Test #5:
score: -100
Time Limit Exceeded
input:
100000 21 4 24 20 20 30 50 25 47 22 31 30 2 37 43 13 16 12 8 39 31 18 10 42 32 10 49 17 46 35 5 36 13 4 32 4 12 22 49 44 6 18 40 24 34 4 48 22 15 10 1 31 30 44 49 24 29 16 39 11 13 31 42 39 17 28 20 18 15 30 40 23 49 45 3 15 2 24 21 34 11 15 5 2 7 17 27 11 2 44 31 38 16 32 17 9 2 30 49 18 35 46 30 5...