CFR 303 A. Lucky Permutation Triple ( Math, Modulo )
題意:
求長度為 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; }