daily 3

今天数位dp主场惹

CF 1051D

常见的范围dp，思想比较简单

$dp[i][j][0/1]$表示当前是第i列，然后有j组，当前列两个方块颜色相同/不同

那么转移方程很好写

$dp[i][j][0]=(dp[i-1][j-1][0]+dp[i-1][j][0]+2*dp[i-1][j][1])$

$dp[i][j][1]=(2*dp[i-1][j-1][0]+dp[i-1][j][1]+dp[i-1][j-2][1])$

ll dp[N][2*N][2];//0 means equal 1 means not equal
void solve(){
  int n,k;
  cin>>n>>k;
  int cur,nxt;
  dp[1][1][0]=dp[1][2][1]=2;
  for(int i=2;i<=n;++i){
    for(int j=1;j<=k;++j){
        if(j==1){
            dp[i][j][0]=2;
        }else{
            dp[i][j][0]=(dp[i-1][j-1][0]+2*dp[i-1][j][1]+dp[i-1][j][0])%MOD;
            dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j-2][1]+2*dp[i-1][j-1][0])%MOD;
        }
    }
  }
  cout<<(dp[n][k][0]+dp[n][k][1])%MOD<<'\n';
  return;
}

CF 855E
dp[base][pos][sta]表示当前的的基数下，当前遍历到第pos位，之前的情况是sta

那么转移很正常，就按数位dp的板子套一哈就好了

ll dp[11][70][1024];
void solve(){
  int q;
  cin>>q;
  int base;
  memset(dp,-1,sizeof(dp));
  vector<int>num(70);
  function<ll(int,int,int,int)>dfs=[&](int pos,int sta,int lead,int flag){
    if(!pos)return (ll)!sta;
    if(!lead&&!flag&&dp[base][pos][sta]!=-1){
        return dp[base][pos][sta];
    }
    ll res=0;
    int lim=flag?num[pos]:base-1;
    for(int i=0;i<=lim;++i){
        res+=dfs(pos-1,(lead&&!i)?0:(sta^(1<<i)),lead&&(!i),flag&&(i==(lim)));
    }
    if(!lead&&!flag){
        dp[base][pos][sta]=res;
    }
    return res;
  };
  ll l,r;
  function<ll(ll)>get=[&](ll x){
    int pos=0;
    while(x){
        num[++pos]=x%base;
        x/=base;
    }
    return dfs(pos,0,1,1);
  };
  while(q--){
    cin>>base>>l>>r;
    ll right=get(r),left=get(l-1);
    cout<<get(r)-get(l-1)<<'\n';
  }
  return;
}

CF 55D
首先1-9的乘积为2520，然后对于一个数A，你等价于A%2520

之后你还需要存一哈mod的值，注意到2520的因数只有48个，那么就搞这48个就吼了（只有这48个满足情况）

ll dp[50][N+1][50];
ll gcd(ll a,ll b){
    return b?a:gcd(b,a%b);
}
void solve(){
  int t;cin>>t;
  memset(dp,-1,sizeof(dp));
  vector<int>mp(N+1);
  int cnt=0;
  for(int i=1;i<=N;++i){
    if(2520%i==0){
        mp[i]=++cnt;
    }
  }
  vector<int>num(50);
  function<ll(int,int,int,int)>dfs=[&](int pos,int pre,int mod,int flag){
    if(!pos)return (ll)(pre%mod==0);
    if(!flag&&dp[pos][pre][mp[mod]]!=-1){
        return dp[pos][pre][mp[mod]];
    }
    ll res=0;
    int lim=flag?num[pos]:9;
    for(int i=0;i<=lim;++i){
        res+=dfs(pos-1,(pre*10+i)%N,i==0?mod:mod*i/gcd(mod,i),flag&&(i==lim));
    }
    if(!flag){
        dp[pos][pre][mp[mod]]=res;
    }
    return res;
  };
  function<ll(ll)>get=[&](ll x){
    int pos=0;
    while(x){
        num[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1,1);
  };    
  while(t--){
    ll l,r;
    cin>>l>>r;
    cout<<get(r)-get(l-1)<<'\n';
  }
  return;
}

明天三面阿里了，有点紧脏。啊啊啊啊，干巴爹