yukicoder No.868 - ハイパー部分和問題

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

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

int N, K, A[15000], Q, X, V;

mint dp[15001];

void go(int m){
  int i;
  if(m==0) return;
  for(i=K;i>=m;i--) dp[i] += dp[i-m];
}

void back(int m){
  int i;
  if(m==0) return;
  rep(i,m,K+1) dp[i] -= dp[i-m];
}

{
  int i, j, k, m;
  Rand rnd;

  rep(100) m = rnd.get(9d8, 1.01d9);
  while(!isPrime(m)) m++;
  dp[0].setmod(m);
  
  rd(N,K,A(N),Q);

  dp[0] = 1;
  rep(i,N) go(A[i]);

  rep(Q){
    rd(X--, V);
    back(A[X]);
    A[X] = V;
    go(A[X]);
    if((int)dp[K]) wt(1); else wt(0);
  }
}

Current time: 2024年04月27日12時21分34秒
Last modified: 2019年08月21日06時08分01秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)