QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645127#7420. K-pop Strings11d10xyTL 801ms177580kbC++141.7kb2024-10-16 16:59:192024-10-16 16:59:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 16:59:20]
  • 评测
  • 测评结果:TL
  • 用时:801ms
  • 内存:177580kb
  • [2024-10-16 16:59:19]
  • 提交

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

output:


result: