技術室奥プログラミングコンテスト#4 Day1 N問題 - multiple

Source

技術室奥プログラミングコンテスト#4 Day1
問題文

問題概要

省略

解法

省略

cLay（version 20190902-1）のコード

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

int N, D, A[1d5];

int fs, f[20], fn[20];
int cur[20];

inline void doit(int n, int fg){
  int i;
  rep(i,fs) while(n%f[i]==0) n /= f[i], cur[i] += fg;
}

inline int isok(void){
  int i;
  rep(i,fs) if(cur[i] < fn[i]) return 0;
  return 1;
}

{
  int i, j, s, t;
  map<int,int> mp;
  ll res = 0;
  
  rd(N,D,A(N));

  fs = Factor(D, f, fn);

  s = 0;
  mp[s]++;
  rep(i,N){
    s = (s + A[i]) % D;
    mp[s]++;
  }

  s = t = 0;
  j = 0;
  rep(i,N){
    while(i >= j || (j < N && !isok())){
      mp[t]--;
      t = (t + A[j]) % D;
      doit(A[j], 1);
      j++;
    }
    if(!isok()) break;
    
    res += mp[s];
    s = (s + A[i]) % D;
    doit(A[i], -1);
  }

  wt(res);
}

Current time: 2024年04月19日18時03分28秒
Last modified: 2019年09月04日00時13分03秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)