90分dfs剪枝,调了半天
查看原帖
90分dfs剪枝,调了半天
246331
mystic_qwq楼主2023/5/5 06:16
/*#ifndef ONLINE_JUDGE               
  #define DEBUG \
    printf("p=%d k=%d\n",p,k)
  #define DEBUG1 \
    ans.out(),\
    putchar(' ');\
    Mint t=mul(0,K);t.out(),\
    putchar('\n')
#endif*/
#define printf __builtin_printf
#define scanf __builtin_scanf
#define putchar __builtin_putchar

template<typename T>
T max(T a,T b){return a>b?a:b;}

struct Mint{
  int a[5000]={0},l=0;
  void flatten(){
    for(int i=1;i<=l;i++)
      a[i+1]+=a[i]/10,
      a[i]%=10,
      (i==l&&a[i+1])&&(l++);
  }
  Mint(int t=0){
    (!t)&&(a[1]=0,l=1);
    do{
      a[++l]=t%10,t/=10;
    }while(t);
  }
  Mint operator*(Mint b){
    Mint c;
    for(int i=1;i<=l;i++)
      for(int j=1;j<=b.l;j++)
        c.a[i+j-1]+=a[i]*b.a[j];
    c.flatten(); 
    return c;
  }
  bool operator==(Mint b){
    if(l^b.l)
      return 0;
    for(int i=1;i<=l;i++)
      if(a[i]^b.a[i])
        return 0;
    return 1;
  }
  bool operator>(Mint b){
    if(l^b.l)
      return l>b.l;
    for(int i=l;i;i--)
      if(a[i]^b.a[i])
        return a[i]>b.a[i];
    return 0;
  }
  bool operator<(Mint b){
    return !(*this>b||*this==b);
  }
  void out(){
    for(int i=l;i;i--)
      putchar('0'+a[i]);
  }
}n[70],ans(0);

int N,K;
char s[410];

void inq(int p,int k){
  for(int i=n[k].l;i;i--)
    n[k].a[i+1]=n[k].a[i];
  n[k].a[1]=s[p]^'0',n[k].l++;
  //a[k]=(a[k]<<3)+(a[k]<<1)+(s[p]^'0');
}
void del(int k){
  for(int i=2;i<=n[k].l;i++)
    n[k].a[i-1]=n[k].a[i];
  n[k].l--;
 //a[k]/=10
}
Mint mul(int l,int r){
  Mint k(1);
  for(int i=l;i<=r;i++)
    k=k*n[i];
  return k;
}
void dfs(int p,int k){
  //DEBUG;
  if(N-1-p<max(0,K-k))
    return;
  if(k==K){
    for(int i=p;i<N;i++)
      inq(i,K);
    //DEBUG1;
    ans=max(ans,mul(0,K));
    n[K]=0;
    return;
  }
  inq(p,k);
  dfs(p+1,k);
  if(!(n[p+1]==(Mint)'0'))//if(a[p+1]^'0')
    dfs(p+1,k+1);
  del(k);
}
int main(){
  __builtin_scanf("%d%d%s",&N,&K,s);
  dfs(0,0);
  ans.out();
}
2023/5/5 06:16
加载中...