0w1

CFR 303 A. Lucky Permutation Triple ( Math, Modulo )

Problem - 303A - Codeforces

題意:
求長度為 N 的三個排列 A, B, C,使得所有 ( A[ i ] + B[ i ] ) % N = C[ i ]。若無解輸出 - 1。

資料規模:
N ≤ 1e5

解法:
先算一下總和:Sigma( i % N, for all 0 ≤ i < N ),便會發現偶數時此值為 N / 2,奇數時為 0。發現若 N 為偶數一定無法達成,因為三個排列的總和都為 N / 2,其中兩個相加後一定會等於 0,便不可能和剩下的排列的總和 N / 2 相同。因此只需考慮 N 為奇數時的情形:發現 A[ i ] = B[ i ] = i 時必為合法。

時間 / 空間複雜度:
O( N )

#include <bits/stdc++.h>
using namespace std;

signed main(){
  ios::sync_with_stdio( 0 );
  int N; cin >> N;
  if( ~N & 1 ){
    cout << -1 << endl;
  } else{
    for( int i = 0; i < N; ++i ){
      cout << i << " \n"[ i + 1 == N ];
    }
    for( int i = 0; i < N; ++i ){
      cout << i << " \n"[ i + 1 == N ];
    }
    for( int i = 0; i < N; ++i ){
      cout << ( i + i ) % N << " \n"[ i + 1 == N ];
    }
  }
  return 0;
}