HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235） F問題 - Variety of Digits

Source

HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）
問題文

問題概要

省略

解法

省略

cLay（version 20220116-1）のコード

C++に変換後のコードはこちら

#define MD 998244353
char N[1d5]; int LEN, M, C[10], mask, cmask, c, m, bsm[1024];
Modint cur = 0, res = 0;
Modint **dp1, **dp2, **dp3, repmean[1d4+2];
Comb<Modint> comb;

rd(N@LEN, M, C(M));
rep(i,LEN) N[i] -= '0';

cntArrayNecessaryElement_walloc(LEN, 10, &dp1, &dp2, &dp3);

repmean[0] = 0;
rep(i,LEN) repmean[i+1] = repmean[i] * 10 + 1;
rep(i,LEN) repmean[i+1] /= i+1;

rep(m,1<<10) bsm[m] = sum[i,0,10 @ BIT_ith(m,i)](i);
cmask = mask = ((1<<10)-1) ^ arr2bit_int(M,C);

rep(k,1,LEN) rep(i,1,10){
  m = mask | (1<<i);
  c = BIT_popcount(m);
  res += i * comb.pw10(LEN-k-1) * dp1[LEN-k-1][10-c];
  if(LEN-k-1 > 0){
    res += dp3[LEN-k-1][10-c] * bsm[m] * repmean[LEN-k-1];
    res += dp2[LEN-k-1][10-c] * (45 - bsm[m]) * repmean[LEN-k-1];
  }
}

rep(k,LEN){
  rep(i,N[k]) if(!(k==i==0)){
    m = cmask | (1<<i);
    c = BIT_popcount(m);
    res += (10 * cur + i) * comb.pw10(LEN-k-1) * dp1[LEN-k-1][10-c];
    if(LEN-k-1 > 0){
      res += dp3[LEN-k-1][10-c] * bsm[m] * repmean[LEN-k-1];
      res += dp2[LEN-k-1][10-c] * (45 - bsm[m]) * repmean[LEN-k-1];
    }
  }
  cur = 10 * cur + N[k];
  cmask |= (1<<N[k]);
}
if(cmask == (1<<10)-1) res += cur;
wt(res);

Current time: 2024年05月19日00時10分41秒
Last modified: 2022年01月16日13時51分08秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC235 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン：