Codeforces Round #678 DIV2 F問題 - Sum Over Subsets

Source

Codeforces Round #678 DIV2 F問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201115-2）のコード

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

//no-unlocked
#define MD 998244353
int F[1d5+1];
int fs, f[30], fn[30];
{
  Modint res = 0, tmp, fc;
  Modint ps, p2s;

  REP(rd_int()){
    int @A, @x;
    F[A] += x;
  }
  rep(k,1,1d5+1){
    Modint pw, pwi;
    ll tot = 0;

    fs = Factor(k, f, fn);
    if(max(fn(fs)) >= 2) continue;

    tot = 0;
    rep(i,k,1d5+1,k) tot += F[i];
    if(tot <= 1) continue;

    ps = p2s = 0;
    rep(i,k,1d5+1,k) ps += F[i] * Modint(i);
    rep(i,k,1d5+1,k) p2s += F[i] * Modint(i) ** 2;

    pw = Modint(2) ** (tot-2);
    pwi = pw / 2;

    tmp = 0;
    rep(i,k,1d5+1,k){
      fc = (ps - i) * pw;
      tmp += i * fc * F[i];
      fc = ((ps - i) ** 2 + (p2s - Modint(i)**2)) * pwi;
      tmp += fc * F[i];
    }
    res if[fs%2==1, -=, +=] tmp;
  }
  wt(res);
}

Current time: 2024年04月23日15時28分00秒
Last modified: 2020年11月16日23時28分11秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF678 CF_DIV2_F
トップページに戻る

Logged in as: unknown user (not login)