9521번: PALETA

https://www.acmicpc.net/problem/9521

fi <- i를 모두 연결해보면 트리나 하나의 사이클에 트리가 달린 그래프만 존재한다.
만약 모든 사이클에 채색을 마쳤다면 나머지 노드들에게는 각각 k-1가지의 채색 방법이 존재한다.
따라서 답은 각 사이클 채색 수 곱 * (k-1)^나머지 노드 수이다.
사이클 채색은 위키피디아 참조
https://en.wikipedia.org/wiki/Graph_coloring#Chromatic_polynomial

아래 소스의 시간복잡도는 $O(n)$

#include<cstdio>
#define mod (int(1e9)+7)
int n, k, a[1000001], vis[1000001], s, c;
long long r = 1, dp[1000001];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    dp[0] = k;
    for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] * (k - 2) + dp[i - 2] * (k - 1)) % mod;
    dp[1] = k;
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        int j = i;
        while (!vis[j]) vis[j] = ++c, j = a[j];
        if (vis[j] >= vis[i]) r = r*dp[c - vis[j] + 1] % mod, s += c - vis[j] + 1;
    }
    for (int i = n - s; i--;) r = r*(k - 1) % mod;
    printf("%lld", r);
    return 0;
}

2803번: KOŠARE

https://www.acmicpc.net/problem/2803

$O(m(n+2^m))$

풀이:
http://hsin.hr/coci/archive/2011_2012/contest6_solutions.zip
6번 참조

#include<cstdio>
#define mod int(1e9+7)
int n, m, r;
long long c[1 << 20];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1 << m; i--;) c[i]++;
    while (n--) {
        int k, x, tot = 0;
        for (scanf("%d", &k); k--;) {
            scanf("%d", &x);
            tot += 1 << x - 1;
        }
        c[tot] = c[tot] * 2 % mod;
    }
    for (int i = 1; i < 1 << m; i *= 2)
        for (int j = 1 << m; j--;) if (i&j) c[j] = c[j] * c[j^i] % mod;
    for (int i = 1 << m; i--;) {
        int b = 0;
        for (int j = i; j; j &= j - 1) b++;
        r = (r + mod + c[i] * (m - b & 1 ? -1 : 1)) % mod;
    }
    printf("%d", r);
    return 0;
}

14556번: Balance

https://www.acmicpc.net/problem/14556

$O(n)$

어떤 추의 무게는 그보다 가벼운 모든 추의 무게합보다 크다.
n개 추를 놓는 순서의 경우의 수를 an이라하자.
an+1은 마지막에 놓는 추의 종류에 따라 다음과 같은 경우로 나누어 계산할 수 있다.
1) 2^N+1 추를 오른쪽에 놓는다. -> an
2) 2^i (i<=N) 추를 왼쪽 혹은 오른쪽에 놓는다. -> an * 2N
따라서 an+1 = (2n+1) an
a1 = 1 이므로
an = 1 * 3 * 5 * ... * (2n-3) * (2n-1) 이다.

#include<cstdio>
int n, r = 1;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) r = (1LL * r*(2 * i - 1)) % (int(1e9) + 9);
    printf("%d", r);
    return 0;
}

4005번: 테이블 색칠하기

https://www.acmicpc.net/problem/4005

#include<cstdio>
#include<vector>
#define mod int(1e9)
using namespace std;
const int MX = 1e5;
int n, m, k, r = 1, vis[MX + 1], c[MX + 1], ck[MX + 1], tcnt, ccnt;
vector<pair<int, int> > row[MX + 1];
vector<int> col[MX + 1];
void f(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    int cnt = 0, tot = 0;
    for (auto it : row[h]) if (ck[it.first]) {
        tot++;
        int ans = it.second ^ (h&it.first & 1);
        if (c[it.first] ^ ans) cnt++;
    }
    if (0 < cnt && cnt < tot) r = 0;
    for (auto it : row[h]) if (!ck[it.first]) {
        tcnt++;
        ck[it.first] = 1;
        c[it.first] = it.second^cnt > 0 ^ (h&it.first & 1);
    }
    for (auto it : row[h]) if (ck[it.first] == 1) {
        ck[it.first]++;
        for (int t : col[it.first]) f(t);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        row[a].push_back({ b,c });
        col[b].push_back(a);
    }
    ccnt = m - 1;
    for (int i = 1; i <= n; i++) {
        tcnt = 0;
        f(i);
        if (tcnt) ccnt -= tcnt - 1;
    }
    while (ccnt--) r = (r * 2) % mod;
    for (int i = 1; i <= n; i++) if (row[i].empty()) r = (r * 2) % mod;
    printf("%d", r);
    return 0;
}

4015번: DNA

https://www.acmicpc.net/problem/4015


$O(mk)$

#include<cstdio>
int m, k, s[50001];
long long r, dp[50001][11][5];
char g[] = " ACGT";
int main() {
    scanf("%d%d%lld", &m, &k, &r);
    for (int i = 0; i < m; i++) {
        char x;
        scanf(" %c", &x);
        if (x == 'A') s[i] = 1;
        if (x == 'C') s[i] = 2;
        if (x == 'G') s[i] = 3;
        if (x == 'T') s[i] = 4;
    }
    dp[m][1][4] = 1;
    for (int i = m; i--;) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= 4; l++) if (!s[i] || s[i] == l) {
                for (int n = 1; n < l; n++) dp[i][j][l] += dp[i + 1][j - 1][n];
                for (int n = l; n <= 4; n++) dp[i][j][l] += dp[i + 1][j][n];
            }
        }
    }
    for (int i = m; i--;)
        for (int j = 1; j <= k; j++)
            for (int l = 1; l <= 4; l++) dp[i][j][l] += dp[i][j - 1][l];
    for (int i = 0; i < m; i++) {
        if (s[i]) putchar(g[s[i]]);
        else {
            for (int j = 1; j <= 4; j++) {
                int t = 0;
                if (i&&s[i - 1]>j) t = 1;
                if (dp[i][k - t][j] < r) r -= dp[i][k - t][j];
                else {
                    s[i] = j;
                    putchar(g[j]);
                    break;
                }
            }
        }
        if (i&&s[i - 1] > s[i]) k--;
    }
    return 0;
}

13560번: Football

https://www.acmicpc.net/problem/13560


$O(n)$

https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets

#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[10000], s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", w + i);
    sort(w, w + n);
    for (int i = 0; i < n; i++) if ((s += w[i] - i) < 0) {
        puts("-1");
        return 0;
    }
    printf("%d", s ? -1 : 1);
    return 0;
}

1947번: 선물 전달

https://www.acmicpc.net/problem/1947


$O(n)$

교란(완전)순열을 구한다.

#include<cstdio>
int n;
long long r, m = 1;
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) r = (r*i + m) % (int)(1e9), m *= -1;
    printf("%lld", r);
    return 0;
}

10978번: 기숙사 재배정

https://www.acmicpc.net/problem/10978


$O(t+MAXn)$

1~20 번째 완전순열을 미리 구해놓고 각 테스트 케이스마다 정답을 출력한다.

#include<cstdio>
int t, n;
long long dp[21];
int main() {
    dp[0] = 1;
    for (int i = 2; i <= 20; i++) dp[i] = (i - 1)*(dp[i - 1] + dp[i - 2]);
    scanf("%d", &t);
    while (t--) scanf("%d", &n), printf("%lld\n", dp[n]);
    return 0;
}

2225번: 합분해

https://www.acmicpc.net/problem/2225


$O(nk)$

답은 kHn이다.

#include<cstdio>
int n, k, dp[201] = { 1 };
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++) dp[j] = (dp[j - 1] + dp[j]) % (int)(1e9);
    printf("%d", dp[n]);
    return 0;
}

2893번: XOR 도형

https://www.acmicpc.net/problem/2893

$O(2^n)$

x=a, y=b, x+y=c 로 이루어진 직각이등변삼각형을 (a,b,c)로 표현하자.

주어진 삼각형을 이루는 점들 집합을 ti라 하자.
구하고자 하는 구역
r=
sum(ti)
-2*sum(ti∩tj)
+4*sum(ti∩tj∩tk)
...

r구하기 위해 ti들을 교집합하는 연산을 구현해야 한다.
ti(ai,bi,ci)라고 하자.
ti∩tj를 잘 생각해보면 max(ai,aj)+max(bi,bj)<min(ci,cj) 인 경우 (max(ai,aj),max(bi,bj),min(ci,cj)) 인 직각이등변 삼각형이 됨을 알 수 있다.(위 부등식을 만족하지 않으면 ∅이다.)

∅이 아닌 경우만 따져서 계산하여 r을 구해주면 된다.

#include<cstdio>
int n, x[10], y[10], z[10];
double s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", x + i, y + i, z + i), z[i] += x[i] + y[i];
    for (int i = 1; i < 1 << n; i++) {
        int m = 1, a = 0, b = 0, c = 1e9;
        for (int j = 0; j<n; j++) if (i&(1 << j)) {
            m *= -2;
            if (a<x[j]) a = x[j];
            if (b<y[j]) b = y[j];
            if (c>z[j]) c = z[j];
        }
        s += (a + b < c) / -4.0*(c - a - b)*(c - a - b)*m;
    }
    printf("%.1lf", s);
    return 0;
}

1359번: 복권

https://www.acmicpc.net/problem/1359


$O(n^2)$

#include<cstdio>
int c[9][9], n, m, k, s;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    for (int i = k; i <= m; i++) s += c[m][i] * c[n - m][m - i];
    printf("%.9lf", (double)s / c[n][m]);
    return 0;
}

1344번: 축구

https://www.acmicpc.net/problem/1344


O(...)

#include<cstdio>
#include<math.h>
const int p[] = { 0,1,4,6,8,9,10,12,14,15,16,18 };
int c[19][19], a, b;
double f(double x) {
    double s = 0;
    for (int i = 0; i < 12; i++) s += c[18][p[i]] * pow(x, p[i])*pow(1 - x, 18 - p[i]);
    return s;
}
int main() {
    scanf("%d%d", &a, &b);
    for (int i = 0; i < 19; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    printf("%lf", 1 - f(a / 100.0)*f(b / 100.0));
    return 0;
}

2448번: 별찍기 - 11

https://www.acmicpc.net/problem/2448

$O(n^2)$

가장 작은 삼각형이 그려지는 모양을 보면
파스칼의 삼각형을 이루는 숫자들 중 홀수만 칠한 것과 같음을 알 수 있다.

#include<cstdio>
int n, a[3072][6146];
int main() {
    scanf("%d", &n);
    a[0][n - 1] = a[1][n - 2] = a[1][n] = a[2][n - 3] = a[2][n - 2] = a[2][n - 1] = a[2][n] = a[2][n + 1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2 * n - 1; j++) {
            if (i > 2) a[i][j] = (j>2 && a[i - 3][j - 3]) ^ a[i - 3][j + 3];
            putchar(" *"[a[i][j]]);
        }
        puts("");
    }
    return 0;
}

1670번: 정상 회담 2

https://www.acmicpc.net/problem/1670


$O(n^2)$

카탈란 수열이다.

#include<cstdio>
int n, c[5001] = { 1 };
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n / 2; i++)
        for (int j = 0; j < i; j++) c[i] = (c[i] + 1LL * c[j] * c[i - 1 - j]) % 987654321;
    printf("%d", n & 1 ? 0 : c[n / 2]);
    return 0;
}

10422번: 괄호

https://www.acmicpc.net/problem/10422


$O(l^2+t)$

카탈란 수열이다.

#include<cstdio>
int t, l, c[2501] = { 1 };
int main() {
    for (int i = 1; i < 2501; i++)
        for (int j = 0; j < i; j++) c[i] = (c[i] + 1LL * c[j] * c[i - 1 - j]) % 1000000007;
    for (scanf("%d", &t); t--;) scanf("%d", &l), printf("%d\n", l & 1 ? 0 : c[l / 2]);
    return 0;
}

11876번: PERICA

https://www.acmicpc.net/problem/11876


$O(n(k+\lg n))$

ai(0부터)를 정렬한 뒤
sum(nCk-1*ai)을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000007
int c[100000][50], a[100000], n, k, r;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    sort(a, a + n);
    for (int i = 0; i<n; i++) {
        c[i][0] = 1;
        for (int j = 1; j<k&&j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        r = (r + (long long)c[i][k - 1] * a[i]) % mod;
    }
    printf("%d", r);
    return 0;
}

13259번: 강호의 초대

https://www.acmicpc.net/problem/13259


$O(n^2)$

#include<cstdio>
int n, a[50];
double dp[51], f = 1, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), dp[i + 1] = dp[i] - (f /= -i - 1);
    for (int i = 0; i < n; i++) {
        int ck[50] = { 0, }, c = 0;
        for (int j = i; !ck[j]; j = a[j]) ck[j] = 1, c++;
        r += dp[c];
    }
    printf("%.9lf", r);
    return 0;
}

13253번: 토러스

https://www.acmicpc.net/problem/13253


$O(nm)$

문제와 같이 움직이면 띠형태로 순환할 것이다.
이에 따라 다음 문제로 변형할 수 있다.

x=0, 1, ..., n 지점이 있다.
매 시도마다 좌우로 각각 1/2 확률로 움직인다.
x=k에서 시작해서 x=0 or x=n 에 최초로 도착할 때까지의 시도 횟수 기댓값 a[k]는?

a[k]들은 다음 식들을 만족한다.
a[1]=(a[0]+a[2])/2+1
a[2]=(a[1]+a[3])/2+1
...
a[n-1]=(a[n-2]+a[n])/2+1
a[0]=a[n]=0
위 식들의 좌우변을 각각 더하면
a[1]+a[n-1]=2n-2
a[1]=a[n-1] 이므로 a[1]=n-1
a[i]=(a[i-1]+a[i+1])/2+1
를 이용하면
a[k]=k(n-k)

#include<cstdio>
int n, m, x, y, t = -1, c, i, j;
int main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    do {
        if (t<0 && i == x&&j == y) t = c;
        i = (i + 1) % n;
        j = (j + 1) % m;
        c++;
    } while (i | j);
    printf("%d", t<0 ? -1 : c*t - t*t);
    return 0;
}

13249번: 공의 충돌

https://www.acmicpc.net/problem/13249


$O(n^2)$


공이 부딛힌 후 그냥 지나간다고 생각하자.
떨어진 거리가 2t 이하인 임의의 한 쌍의 공은 1/4 확률로 충돌한다.

#include<cstdio>

int n, a[12], t, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    scanf("%d", &t);
    for (int i = 0; i<n; i++)for (int j = i; j--;)r += a[i] <= a[j] + t * 2 & a[i] >= a[j] - t * 2;
    printf("%f", r / 4.0);
    return 0;
}

6567번: Let it Bead

https://www.acmicpc.net/problem/6567


https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets


포여열거정리를 이용한다.

#include<cstdio>
int pi(int x) {
    int r = x;
    for (int i = 2; i*i <= x; i++) {
        if (x%i == 0) r -= r / i;
        while (x%i == 0) x /= i;
    }
    return r - (x > 1)*r / x;
}
int pow(int x, int y) {
    if (!y) return 1;
    int r = pow(x, y / 2);
    return r*r*(y & 1 ? x : 1);
}
int c, s;
int main() {
    while (scanf("%d %d", &c, &s) && c) {
        int t = 0;
        for (int i = 1; i <= s; i++)
            if (s%i == 0) t += pi(i)*pow(c, s / i);
        printf("%d\n", (t / s + (s & 1 ? pow(c, s / 2 + 1) : (c + 1)*pow(c, s / 2) / 2)) / 2);
    }
    return 0;
}