QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645179 | #7420. K-pop Strings | 11d10xy | TL | 4809ms | 520204kb | C++14 | 2.1kb | 2024-10-16 17:09:47 | 2024-10-16 17:09:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
using u64=unsigned long long;
constexpr i64 mod=998244353;
i64 pw[110];
int n,K;
struct N_{int i,len;};
struct S_{
int col[110],cnt;
tuple<u64,u64,u64>code(int i){
u64 x=i,y=i,z=i;
for(int i=1;i<=n;i++){
x=x*19260817+col[i];
y=y*998244353+col[i];
z=z*13331+col[i];
}return{x,y,z};
}
void recol(){
int id[110]{},tot=0;
for(int i=1;i<=n;i++){
if(!id[col[i]])id[col[i]]=++tot;
col[i]=id[col[i]];
}
}
bool merge(int x,int y){
if(col[x]==col[y])return false;
replace(col+1,col+n+1,+col[x],+col[y]),cnt--;
return true;
}
bool operator<(const S_&o)const{
if(cnt!=o.cnt)return cnt<o.cnt;
for(int i=1;i<=n;i++)if(col[i]<o.col[i])return true;
return false;
}
bool operator==(const S_&o)const{
if(cnt!=o.cnt)return false;
for(int i=1;i<=n;i++)if(col[i]!=o.col[i])return false;
return true;
}
};
vector<N_>a;
struct H_{
size_t operator()(tuple<u64,u64,u64>x)const{
return get<0>(x)*66667ull|get<1>(x)*1717171717717ull|get<2>(x)*998244853ull;
}
};
unordered_map<tuple<u64,u64,u64>,i64,H_>S;
i64 dfs(S_ cur,int i){
auto h=cur.code(i);
if(S.count(h))return S[h];
i64&v=S[h];
if(i==a.size()){
return v=pw[cur.cnt];
}
for(int j=i;j<a.size();j++){
bool flag=true;
for(int k=0;k<a[j].len;k++)if(cur.col[a[j].i+k]!=cur.col[a[j].i+a[j].len+k]){flag=false;break;}
if(flag)return v=0;
}
S_ o=cur;
bool flag=false;
for(int k=0;k<a[i].len;k++)flag|=o.merge(a[i].i+k,a[i].i+a[i].len+k);
if(!flag)return v=0;
o.recol();
return v=(dfs(cur,i+1)+mod-dfs(o,i+1))%mod;
}
int main(){
scanf("%d%d",&n,&K);
pw[0]=1;for(int i=1;i<=n;i++)pw[i]=pw[i-1]*35%mod;
for(int i=1;i<=n;i++)for(int k=max((n-K+1)/2,1);i+k*2-1<=n;k++)
a.push_back({i,k});
S_ init{};
for(int i=1;i<=n;i++)init.col[i]=i;init.cnt=n;
printf("%lld",dfs(init,0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4012kb
input:
1 16
output:
35
result:
ok 1 number(s): "35"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
4 0
output:
1499400
result:
ok 1 number(s): "1499400"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
15 5
output:
911125634
result:
ok 1 number(s): "911125634"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
35 5
output:
93640047
result:
ok 1 number(s): "93640047"
Test #5:
score: 0
Accepted
time: 716ms
memory: 41528kb
input:
100 16
output:
991183816
result:
ok 1 number(s): "991183816"
Test #6:
score: 0
Accepted
time: 1453ms
memory: 158080kb
input:
22 16
output:
960803400
result:
ok 1 number(s): "960803400"
Test #7:
score: 0
Accepted
time: 3036ms
memory: 335664kb
input:
20 16
output:
235606959
result:
ok 1 number(s): "235606959"
Test #8:
score: 0
Accepted
time: 4723ms
memory: 520204kb
input:
17 15
output:
730957706
result:
ok 1 number(s): "730957706"
Test #9:
score: 0
Accepted
time: 4809ms
memory: 520100kb
input:
17 16
output:
730957706
result:
ok 1 number(s): "730957706"
Test #10:
score: -100
Time Limit Exceeded
input:
18 16