QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #602500 | #7063. Space Station | zjy0001 | AC ✓ | 370ms | 30920kb | C++17 | 1.2kb | 2024-10-01 08:57:05 | 2024-10-01 08:57:06 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e6+5,M=55,Mod=1e9+7;
int n,k,ans;
int a[M];
uLL val[N];
unordered_map<uLL,int>mp;
vector<int>frc({1,1}),inv({0,1}),ivf({1,1});
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
inline int qpow(int x,int y,int z=1){
for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline void Init(const int&n){
for(int i=frc.size();i<=n;++i)
frc.emplace_back((LL)frc.back()*i%Mod),
inv.emplace_back(Mod-Mod/i*(LL)inv[Mod%i]%Mod),
ivf.emplace_back((LL)ivf.back()*inv.back()%Mod);
}
inline int solve(int r,int n,uLL s){
if(r>49||!n)return frc[n];
if(mp.count(s))return mp[s];
int z=0;
for(int i=1;i<=r;++i)if(a[i])
--a[i],z=(z+(LL)solve(r+i,n-1,s^(val[i]*(a[i]+1))^(val[i]*a[i]))*(a[i]+1))%Mod,++a[i];
return mp[s]=z;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>k,Init(n);
for(int i=1;i<=n;++i){int x;cin>>x,++a[x];}
uLL hs=0;
for(int i=1;i<50;++i)val[i]=rng()*2+1,hs^=val[i]*a[i];
int ans=solve(k,n-a[0],hs);
ans=(LL)ans*frc[n]%Mod*ivf[n-a[0]]%Mod;
cout<<ans<<'\n';
return 0;
}
/*
*/
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
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: 5ms
memory: 4460kb
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: 5ms
memory: 4472kb
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: 0
Accepted
time: 12ms
memory: 5136kb
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...
output:
983292446
result:
ok single line: '983292446'
Test #6:
score: 0
Accepted
time: 130ms
memory: 16724kb
input:
100000 7 20 29 6 48 4 29 30 48 7 16 15 7 7 26 28 38 32 42 43 47 19 4 37 25 21 21 3 43 13 2 38 14 34 40 19 7 18 5 43 33 16 36 11 35 30 15 2 25 10 49 9 2 40 31 40 9 36 19 28 19 23 26 27 10 18 45 24 38 35 48 6 42 27 13 22 16 50 17 25 42 10 16 15 41 30 6 31 36 17 31 49 18 18 33 14 19 5 27 7 19 15 32 43 ...
output:
363626098
result:
ok single line: '363626098'
Test #7:
score: 0
Accepted
time: 5ms
memory: 4472kb
input:
100000 46 11 7 43 50 4 34 33 49 42 49 0 11 1 34 42 33 26 26 22 39 46 24 33 18 5 44 16 15 42 23 14 14 11 23 10 27 15 11 18 35 39 6 48 12 4 8 34 34 34 48 14 0 9 11 3 41 6 25 19 50 17 9 12 27 33 44 31 36 14 29 12 9 9 23 27 4 0 39 39 46 32 27 29 48 19 13 48 20 41 32 34 47 5 23 17 37 4 29 48 4 35 34 10 3...
output:
545614387
result:
ok single line: '545614387'
Test #8:
score: 0
Accepted
time: 5ms
memory: 4468kb
input:
100000 33 26 12 4 27 29 13 37 50 26 33 35 14 21 17 6 4 22 9 50 30 47 19 28 10 40 16 30 11 21 20 17 12 40 6 24 22 35 18 16 10 38 2 34 40 4 0 14 43 32 45 18 22 3 44 18 46 27 5 9 4 35 44 50 20 50 17 38 8 17 11 18 2 14 7 33 46 25 10 3 1 28 12 41 4 8 21 17 30 15 32 44 25 44 38 48 29 2 6 11 14 4 35 2 42 4...
output:
93496998
result:
ok single line: '93496998'
Test #9:
score: 0
Accepted
time: 10ms
memory: 5588kb
input:
100000 20 41 41 40 28 3 16 41 1 11 41 47 19 16 0 21 23 41 43 3 46 47 13 48 28 48 40 16 33 0 16 44 38 18 41 15 16 32 24 17 12 35 49 20 42 28 44 46 28 5 43 48 22 25 26 9 25 48 35 27 35 28 27 37 13 15 42 46 5 22 17 25 46 47 18 40 34 0 5 44 30 23 23 3 37 23 2 35 14 15 32 4 2 30 2 2 46 2 35 2 49 0 37 21 ...
output:
558286380
result:
ok single line: '558286380'
Test #10:
score: 0
Accepted
time: 190ms
memory: 23640kb
input:
100000 6 6 45 27 30 1 47 45 1 45 25 31 50 37 8 10 19 36 28 33 37 23 8 45 21 33 12 29 30 29 36 47 38 47 50 4 10 27 31 42 38 8 44 31 19 3 37 27 37 4 14 2 44 19 7 23 6 17 40 18 41 46 12 50 6 4 41 26 28 27 50 31 39 29 27 45 22 25 27 9 36 21 34 14 45 11 9 2 50 39 32 15 4 17 17 30 12 0 38 16 35 19 39 13 3...
output:
294711323
result:
ok single line: '294711323'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4592kb
input:
100000 45 22 24 14 7 26 0 48 1 30 9 17 2 32 43 25 40 5 11 11 29 23 28 40 13 17 36 43 2 33 32 23 37 24 33 21 5 23 36 40 40 6 14 17 47 28 29 7 47 27 13 6 16 40 39 38 37 38 21 7 22 40 47 36 24 19 15 33 0 32 31 38 32 10 37 0 36 50 49 50 41 42 46 27 27 26 15 21 34 12 32 25 31 5 32 35 5 50 16 5 46 39 15 3...
output:
523779527
result:
ok single line: '523779527'
Test #12:
score: 0
Accepted
time: 2ms
memory: 4448kb
input:
100000 35 17 27 31 8 22 13 24 9 5 26 31 40 34 8 29 11 19 8 33 49 15 45 38 32 21 11 3 14 29 6 13 5 31 39 42 26 49 37 43 7 17 1 11 26 5 27 23 23 4 34 31 39 14 48 7 30 19 45 3 5 4 0 15 50 23 20 11 11 2 43 33 39 19 45 10 2 34 48 1 19 12 14 42 15 39 1 8 44 45 9 13 29 26 22 4 17 43 32 29 14 31 8 0 40 5 5 ...
output:
845953523
result:
ok single line: '845953523'
Test #13:
score: 0
Accepted
time: 5ms
memory: 4472kb
input:
100000 8 3 1 5 0 0 3 1 5 10 39 44 42 39 38 40 42 47 47 37 42 43 43 42 50 38 41 44 45 43 38 49 45 39 46 40 38 50 48 40 50 45 44 38 42 45 41 44 50 46 39 37 37 43 42 50 46 40 45 38 50 47 42 46 50 41 38 46 44 38 46 38 47 47 38 40 42 50 49 41 42 45 48 49 38 50 40 44 45 43 44 40 46 50 40 50 50 44 43 41 44...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 5ms
memory: 4528kb
input:
100000 10 4 0 5 4 0 8 8 1 1 43 46 46 47 50 48 49 49 43 49 42 42 47 50 48 43 42 45 42 44 48 43 47 47 49 43 48 44 42 47 46 43 49 49 49 44 44 48 46 46 48 45 49 48 50 45 50 43 50 50 50 43 45 48 42 46 47 42 49 48 48 43 50 43 50 47 49 42 50 49 48 48 43 50 47 48 49 42 42 45 46 49 45 45 47 44 44 45 47 45 50...
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 5ms
memory: 4460kb
input:
100000 1 10 9 6 6 0 9 8 0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 4468kb
input:
100000 10 7 7 0 3 7 0 8 0 5 48 48 49 49 50 48 48 50 48 49 50 49 49 48 48 48 49 48 48 48 50 49 48 48 48 48 50 49 49 49 48 50 49 48 49 49 50 50 49 50 50 48 50 49 48 50 49 48 50 48 50 48 49 49 48 49 49 50 50 48 48 50 50 48 50 49 48 50 49 50 49 48 48 50 49 48 49 49 50 49 50 48 48 49 49 48 49 50 50 49 48...
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 2ms
memory: 4536kb
input:
100000 5 9 5 0 8 7 9 45 45 46 49 45 47 46 45 45 47 46 46 44 46 47 49 48 47 48 45 46 49 45 44 47 44 45 48 45 45 46 50 48 46 48 45 47 50 50 46 48 47 50 47 44 44 44 46 44 48 49 50 44 47 49 49 50 45 49 49 45 45 48 47 46 47 44 49 50 50 48 50 50 50 45 50 48 45 48 50 50 49 47 50 47 49 49 47 49 45 45 47 50 ...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 370ms
memory: 30920kb
input:
100000 1 25 50 6 21 4 25 36 20 32 10 14 44 0 19 1 38 41 5 25 38 11 20 11 37 5 4 19 39 11 45 16 38 14 44 20 38 25 32 5 34 37 28 4 41 4 12 34 31 32 11 18 33 10 6 16 29 40 24 14 9 17 16 42 26 16 24 4 46 34 20 24 27 21 27 17 17 7 8 50 0 36 30 4 5 16 43 0 19 29 25 11 16 0 50 30 12 50 26 9 0 46 38 11 50 4...
output:
646807826
result:
ok single line: '646807826'
Test #19:
score: 0
Accepted
time: 360ms
memory: 30900kb
input:
100000 2 47 4 27 34 49 41 45 33 7 38 40 39 44 34 44 28 4 49 30 35 33 27 25 16 42 14 28 2 46 43 5 5 48 8 42 21 16 13 50 25 19 18 11 22 44 18 16 45 37 32 25 35 47 13 11 44 32 1 11 43 33 15 47 46 20 8 11 17 32 13 5 26 5 43 31 20 8 26 40 11 35 25 41 15 43 47 18 16 35 14 7 21 31 13 25 45 12 35 35 16 9 10...
output:
314526688
result:
ok single line: '314526688'
Test #20:
score: 0
Accepted
time: 283ms
memory: 28400kb
input:
100000 3 0 31 5 30 7 21 1 19 44 44 40 7 29 46 10 30 1 9 4 34 20 37 36 16 44 37 45 14 21 6 48 26 23 15 50 27 7 7 34 25 7 14 41 19 38 0 10 21 9 26 32 12 31 49 11 0 15 50 49 24 18 47 49 2 2 37 2 1 40 17 32 48 2 49 19 24 27 10 33 31 12 32 40 12 21 8 15 42 19 31 25 47 20 11 21 12 29 25 24 16 41 42 44 42 ...
output:
852903575
result:
ok single line: '852903575'
Test #21:
score: 0
Accepted
time: 237ms
memory: 25740kb
input:
100000 4 47 15 19 4 38 45 37 2 40 40 37 3 39 15 10 12 36 4 7 11 43 34 3 45 1 41 28 46 17 45 3 0 33 39 18 45 38 32 43 20 49 30 42 12 0 34 19 0 35 13 6 32 21 20 5 7 22 45 5 0 20 22 30 35 13 23 10 25 45 30 30 48 27 49 24 40 46 22 12 38 33 13 49 2 31 15 11 22 34 12 9 22 39 37 40 16 22 30 14 33 26 19 28 ...
output:
67686831
result:
ok single line: '67686831'
Test #22:
score: 0
Accepted
time: 209ms
memory: 23572kb
input:
100000 5 48 35 6 33 23 33 24 13 36 42 39 31 36 21 13 24 26 27 25 0 29 11 15 0 11 50 46 41 38 15 50 23 49 39 45 23 31 9 8 30 5 14 30 15 7 37 45 50 20 34 34 48 8 44 7 29 0 42 6 34 34 9 48 44 40 36 5 42 35 36 26 47 27 29 24 37 36 7 30 20 13 40 22 49 16 30 20 22 6 11 26 12 16 15 20 4 31 47 48 13 9 1 9 3...
output:
283449875
result:
ok single line: '283449875'
Test #23:
score: 0
Accepted
time: 4ms
memory: 4604kb
input:
94347 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
371131493
result:
ok single line: '371131493'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 1 0
output:
1
result:
ok single line: '1'