提出 #11236179

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

template<typename R, size_t N>
struct SquareMatrix{
  typedef array<R, N> arr;
  typedef array<arr, N> mat;
  mat dat;

  SquareMatrix(){
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        dat[i][j]=R::add_identity();
  }

  bool operator==(const SquareMatrix& a) const{
    return dat==a.dat;
  }

  size_t size() const{return N;}
  arr& operator[](size_t k){return dat[k];}
  const arr& operator[](size_t k) const {return dat[k];}

  static SquareMatrix add_identity(){return SquareMatrix();}
  static SquareMatrix mul_identity(){
    SquareMatrix res;
    for(size_t i=0;i<N;i++) res[i][i]=R::mul_identity();
    return res;
  }

  SquareMatrix operator*(const SquareMatrix &B) const{
    SquareMatrix res;
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        for(size_t k=0;k<N;k++)
          res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
    return res;
  }

  SquareMatrix operator+(const SquareMatrix &B) const{
    SquareMatrix res;
    for(size_t i=0;i<N;i++)
      for(size_t j=0;j<N;j++)
        res[i][j]=dat[i][j]+B[i][j];
    return res;
  }

  SquareMatrix pow(long long n) const{
    SquareMatrix a=*this,res=mul_identity();
    while(n){
      if(n&1) res=res*a;
      a=a*a;
      n>>=1;
    }
    return res;
  }
};


template <typename E>
struct SegmentTree{
  using H = function<E(E,E)>;
  int n,height;
  H h;
  E ei;
  vector<E> laz;

  SegmentTree(H h,E ei):h(h),ei(ei){}

  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    laz.assign(2*n,ei);
  }

  inline void propagate(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    laz[k]=ei;
  }

  inline void thrust(int k){
    for(int i=height;i;i--) propagate(k>>i);
  }

  void update(int a,int b,E x){
    if(a>=b) return;
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
  }

  E get_val(int a){
    thrust(a+=n);
    return laz[a];
  }

  void set_val(int a,E x){
    thrust(a+=n);
    laz[a]=x;
  }
};


struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;

  struct D{
    double v;
    D(double v=0):v(v){}
    D operator+(D x)const{return D(v+x.v);}
    D operator*(D x)const{return D(v*x.v);}
    static D add_identity(){return D(0);}
    static D mul_identity(){return D(1);}
    bool operator==(const D x)const{return v==x.v;}
  };
  using SM = SquareMatrix<D, 3>;

  auto g=[&](SM a,SM b){return b*a;};
  SM ei=SM::mul_identity();
  SegmentTree<SM> seg(g,ei);
  seg.init(n);

  map<int, int> cnt;
  cnt[0]=k;

  auto resolve=
    [&](){
      vector<int> ks;
      for(auto p:cnt)
        ks.emplace_back(p.first);
      for(int key:ks)
        if(cnt[key]==0) cnt.erase(key);
    };

  auto print=
    [&](SM mat){
      for(int i=0;i<3;i++){
        for(int j=0;j<3;j++)
          cout<<mat[i][j].v<<" ";
        cout<<endl;
      }
      cout<<endl;
    };
  if(0) print(ei);

  for(int i=0;i<n;i++){
    int num;
    if(s[i]=='0') num=cnt.begin()->first;
    if(s[i]=='1') num=cnt.rbegin()->first;

    //for(auto p:cnt) cout<<p.first<<" "<<p.second<<endl;
    //cout<<num<<endl;

    auto pre=cnt;
    cnt[num]--;
    num++;
    cnt[num]++;
    resolve();

    vector<int> cs,ps;
    for(auto p:cnt) cs.emplace_back(p.first);
    for(auto p:pre) ps.emplace_back(p.first);

    SM prd;
    for(int i=0;i<(int)cnt.size();i++){
      for(int j=0;j<(int)pre.size();j++){
        if(ps[j]==num-1){
          if(ps[j]+0==cs[i]) prd[i][j]=1.0-1.0/pre[ps[j]];
          if(ps[j]+1==cs[i]) prd[i][j]=1.0/pre[ps[j]];
        }else{
          if(ps[j]==cs[i]) prd[i][j]=1.0;
        }
      }
    }
    //print(prd);

    if(i) seg.update(0,i,prd);

    int k=distance(cnt.begin(),cnt.find(num));
    SM res;
    res[k][0]=res[k][1]=res[k][2]=1;
    seg.set_val(i,res);
  }

  for(int k=0;k<n;k++){
    double res=0;
    auto mat=seg.get_val(k);
    // print(mat);

    vector<int> cs;
    for(auto p:cnt) cs.emplace_back(p.first);

    for(int i=0;i<(int)cs.size();i++)
      res+=mat[i][0].v*cs[i];

    cout<<res<<newl;
  }

  return 0;
}

提出情報

ジャッジ結果