C. Harmony Analysis

implementation, math

출처: Codeforces C. Harmony Analysis

SOL)
자기 자신을 곱하면 1, 자기 자신과 보수를 곱하면 -1을 이용

k = 0일때 "+" 또는 "*"로 시작할 수 있다.

k = 1일때 "+"로 시작했다는 가정하에
첫 번째 문자열 "+" 자기자신을 복사한 "++"를 얻을 수 있고
두 번째 문자열은 "+"에서 "+"의 보수인 "*"을 붙여 "+*"을 만든다.

"++"
"+*"
위 문자열에서 1x1 + 1x(-1) = 0을 얻는다.

k = 2일때
첫 번째, 두 번째 문자열은 자기 자신을 복사하여
"++++", "+*+*"을 얻는다.

첫 번째 문자열에서 앞부분 "++"을 가져오고
뒤에 남은"++"의 보수인 "**"을 붙여 "++**"을 얻는다.
마찬가지고 두 번째 문자열 앞부분 "+*"을 가져오고 보수인
"*+"을 붙여 "+**+"를 얻는다.

이 과정을 반복하면 된다.

k = 2
1 - "++/++"
2 - "+*/+*"
3 - "++/**"
4 - "+*/*+"

2개씩 끊어서 보면 당연히 1, 2의 관계는 직교이다.
신기한 것이 2,3의 앞부분은 당연히 0일 것이다.
(k=1에서 얻은결과)
그런데 뒷 부분을 조금 헷갈릴 수 잇는데 잘 생각해보면
경우의 수가 4가지로 만약 앞부분의 결과값이 2였으면 뒤는 -2가 나오고
0이었으면 0이 나오는것을 계산을 좀 하면 알 수 있다.
단순히 1x1 + (-1)x(1)을 할지 1x(-1) + (-1)x(-1)을 할 지 차이이다.




[-] Collapse

#include<iostream>
#include<string>
#include<vector>
using namespace std;

vector<string> str;
char rv[300];
int n;

int main(){
    freopen("input.txt", "r", stdin);
    cin >> n;

    rv['*'] = '+';
    rv['+'] = '*';

    str.push_back("+");

    for (int c = 0; c < n; c++){
        int size = str.size();

        for (int i = 0; i < size; i++){
            string new_str = str[i];

            for (int j = 0; j < size; j++){
                new_str += rv[str[i][j]];
            }

            str[i] += str[i];
            str.push_back(new_str);
        }
    }

    for (int i = 0; i < str.size(); i++){
        cout << str[i] << endl;
    }
    return 0;
}