QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#645127 | #7420. K-pop Strings | 11d10xy | TL | 801ms | 177580kb | C++14 | 1.7kb | 2024-10-16 16:59:19 | 2024-10-16 16:59:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr i64 mod=998244353;
mt19937 g(time(0));
i64 pw[110];
int n,K;
struct N_{int i,len;};
struct S_{
int col[110],cnt;
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;
map<pair<int,S_>,i64>S;
i64 dfs(S_ cur,int i){
if(S.count({i,cur}))return S[{i,cur}];
i64&v=S[{i,cur}];
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});
shuffle(begin(a),end(a),g);
S_ init{};
for(int i=1;i<=n;i++)init.col[i]=i;init.cnt=n;
printf("%lld",dfs(init,0));
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4024kb
input:
1 16
output:
35
result:
ok 1 number(s): "35"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
4 0
output:
1499400
result:
ok 1 number(s): "1499400"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
15 5
output:
911125634
result:
ok 1 number(s): "911125634"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
35 5
output:
93640047
result:
ok 1 number(s): "93640047"
Test #5:
score: 0
Accepted
time: 801ms
memory: 177580kb
input:
100 16
output:
991183816
result:
ok 1 number(s): "991183816"
Test #6:
score: -100
Time Limit Exceeded
input:
22 16