D-ABS SUM（技術室奥プログラミングコンテスト#6 Day1）

f:id:peroon:20210824131430p:plain

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    VI B(N+1);
    rep(i,N){
      B[i+1] = A[i];
    }
    rep(i,N){
      B[i+1] += B[i];
    }
    SORT(B);

    mint sum=0;
    FOR(i,1,N+1){
      sum += i*(B[i]%mod); // mod必要！(overflow)
    }
    rep(i,N){
      sum -= (B[i]%mod)*(N-i); // mod必要！(overflow)
    }
    p(sum.x);
    
    return 0;
}

平面走査(法) (scanline algorithm?)

f:id:peroon:20210817082639p:plain

問題集

クエリと状態変化を同列で扱ってt順に処理

E-Throne ～合同方程式(ax≡b (mod m))とgcdの関係をつかむ動画2つ～ 

ax ≡ b (mod m)

これを満たすxを求めたいが、xは存在することもあるし、存在しないこともある
gcd(a, m)の値が重要になる
高校の数Aで学ぶ
  • 数Aを読み直すかーと思っていたが、現状は以下の動画で間に合った

動画2つ

Moamen and XOR

f:id:peroon:20210810075906p:plain

code

void solve(){
  ll n,k;cin>>n>>k;
  
  if(n%2==0){
    // even
    mint sum = 0;

    // & == xor
    // 等号が成り立つ場合の数---
    // equalになる各列
    // 001111
    // 000011
    // などなら、両辺共に0になる
    mint equal = 0;
    for(int i=2; i<=n; i+=2){
      equal += nCr(n,i);
    }
    // それがk列ある
    sum += equal.pow(k);
    // 等号が成り立つ場合の数---ここまで



    // & > xor
    // 大なり分の場合の数---ここから

    // 1列を0にする場合の数
    mint zero_column = 0;
    // 000000
    // 000011
    // 001111 など
    for(int i=2; i<=n; i+=2){
      zero_column += nCr(n,i);
    }

    mint two=2;
    mint free = two.pow(n); // 1列に0,1を自由に置く場合の数は2^n

    mint bigger_sum=0;
    // 何列目でbiggerを確定させるかを全探索
    rep(i,k){
      // i列目でbiggerを確定させる
      
      mint a = zero_column.pow(i); // i-1列までは各列、&もxorも0
      //a *= 1; // i列目は111111で確定
      a *= free.pow(k-i-1); // i+1列以降は自由

      bigger_sum += a;
    }
    
    sum += bigger_sum;
    p(sum.x);
  }
  else{
    // odd

    // equal only

    // 111で1にしてequalにするか
    // 110で0にするか(0の個数が奇数) nC1 + nC3 + ...

    mint a = 1; // 111
    for(int i=1; i<=n; i+=2){ // i:0の個数
      a += nCr(n, i);
    }

    // それがビット数分(k)あるので

    mint ans = a.pow(k);
    p(ans.x);
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    prepare_nCr();
    
    while(N--)solve();
    
    return 0;
}

other's tweet (C)