QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645160#7420. K-pop Strings11d10xyTL 6047ms361016kbC++141.9kb2024-10-16 17:06:282024-10-16 17:06:28

Judging History

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

  • [2024-10-16 17:06:28]
  • 评测
  • 测评结果:TL
  • 用时:6047ms
  • 内存:361016kb
  • [2024-10-16 17:06:28]
  • 提交

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;
map<tuple<u64,u64,u64>,i64>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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

input:

1 16

output:

35

result:

ok 1 number(s): "35"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

4 0

output:

1499400

result:

ok 1 number(s): "1499400"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

15 5

output:

911125634

result:

ok 1 number(s): "911125634"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

35 5

output:

93640047

result:

ok 1 number(s): "93640047"

Test #5:

score: 0
Accepted
time: 854ms
memory: 44872kb

input:

100 16

output:

991183816

result:

ok 1 number(s): "991183816"

Test #6:

score: 0
Accepted
time: 2587ms
memory: 168692kb

input:

22 16

output:

960803400

result:

ok 1 number(s): "960803400"

Test #7:

score: 0
Accepted
time: 6047ms
memory: 361016kb

input:

20 16

output:

235606959

result:

ok 1 number(s): "235606959"

Test #8:

score: -100
Time Limit Exceeded

input:

17 15

output:


result: