11402 이항 계수 4

11402 이항 계수 4 https://www.acmicpc.net/problem/11402
SW Expert Academy 3238 이항계수 구하기


먼저 위의 문제들을 풀기위해서는 Lucas' Theorem을 알아야 한다.

[출처 : wiki] 

임의의 음이 아닌 정수 m과 n, 소수 p에 대하여 다음과 같이 합동식으로 표현할 수 있다.

• ${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$

여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것이다. 덧붙여, 한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다.

1. ${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$
2. ${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

즉, $m,n$을 $p$의 진수로 나타내고 그것의 계수들을 $m_{k}, n_{k}$라 했을 때
$_{m}C_{n} (mod$ $p) =$ $(_{m_{k}}C_{n_{k}})$$(_{m_{k-1}}C_{n_{k-1}})$$\cdots$$(_{m_{0}}C_{n_{0}})$$(mod$ $p)$

1. 11402 이항계수 4

위의 정리를 이용하여 기본적인 2차원 dp를 이용하면 $O(M^2)$에 풀 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2005; ll n, r; int m; int dp[MAXN][MAXN]; ll nCr(int n, int r) {     if (r == 1) return n;     if (r == 0) return 1;     if (n < r) return 0;     int &ret = dp[n][r];     if (ret != -1) return ret;     ret = 0;     return ret = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % m; } int main() {     memset(dp, -1, sizeof dp);     scanf("%lld%lld%d", &n, &r, &m);     ll ret = 1;     while (n || r) {         ret *= nCr(n%m, r%m);         ret %= m;         n /= m, r /= m;     }     printf("%lld", ret);     return 0; } Colored by Color Scripter

cs

2. 3238 이항계수 구하기

페르마 소정리와 분할정복 거듭제곱을이용해 $O(log$ $p)$에 구할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 5; ll n, r; int t, m; ll f[MAXN]; ll mpow(ll a, ll p) {     ll ret = 1;     while (p) {         if (p & 1) ret *= a, ret %= m;         a *= a;         a %= m;         p /= 2;     }     return ret; } int main() {     scanf("%d", &t);     for (int i = 1; i <= t; i++) {         scanf("%lld%lld%d", &n, &r, &m);         f[0] = 1;         for (int i = 1; i < m; i++)f[i] = (f[i - 1] * i) % m;         ll ret = 1;         while (n || r) {             ll a = n % m, b = r % m;             if (a < b) ret = 0;             if (ret == 0) break;             ret *= f[a];             ret %= m;             ret *= mpow((f[b] * f[a - b]) % m, m - 2);             ret %= m;             n /= m, r /= m;         }         printf("#%d %lld\n", i, ret);     }     return 0; } Colored by Color Scripter

cs

15949 Piet

15949 Piet https://www.acmicpc.net/problem/15949

Piet은 프로그래밍의 언어의 한 종류로 2차원 이미지로 구성이 되있다.

지문에서 설명되있는 그대로를 구현하면 되는 문제다.

같은 색깔 블록의 좌표 정보를 전처리로 구해놓고 유효한 코델이 나올 때 까지 찾아주었다.

현재 블록의 코델들 중 DP와 CC에 해당하는 값은 정렬시켜서 찾아주었다.

DP와 CC로 블록이 이동하는데 CC가 DP의 상대적인 값에 유의 하자!

2018 UCPC 본선 문제였는데 시간이 얼마 남지 않았을 때 봐서 풀지 못했던 문제다 ㅠㅠ

#include <bits/stdc++.h> using namespace std; const int MAXN = 105; int n, m; char arr[MAXN][MAXN]; int num[MAXN][MAXN]; int dy[] = { -1,0,1,0 }; int dx[] = { 0,1,0,-1 }; // up ,right, down, left enum dir{     up = 0, right, down, left  }; struct Info {     int y, x;     int dp, cc;     Info() {}     Info(int yy, int xx, int ddp, int ccc) :y(yy), x(xx), dp(ddp), cc(ccc) {} }; struct Point {     int y, x;     Point() {}     Point(int yy, int xx) :y(yy), x(xx) {} };     vector<Point> point[100001]; bool isout(int y, int x) {     if (y < 0 || y >= n || x < 0 || x >= m) return true;     return false; } void dfs(Point p, int cnt) {     point[cnt].push_back(p);     for (int i = 0; i < 4; i++) {         int ny = p.y + dy[i], nx = p.x + dx[i];         if (isout(ny, nx) || num[ny][nx] != -1 || arr[p.y][p.x] != arr[ny][nx]) continue;         num[ny][nx] = cnt;         dfs(Point(ny, nx), cnt);     } } int main() {     memset(num, -1, sizeof num);     scanf("%d%d", &n, &m);     for (int i = 0; i < n; i++) scanf("%s", &arr[i]);       int cnt = 0;     for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {         if (arr[i][j] == 'X') continue;         if (num[i][j] != -1) continue;         num[i][j] = ++cnt;         dfs(Point(i,j), cnt);       }     Info info(0, 0, dir::right, dir::left);     printf("%c", arr[0][0]);     while (1) {         Info cpy = info;         int g = num[info.y][info.x];         bool flag = false;         for (int i = 0; i < 4; i++) {             for (int j = 0; j < 2; j++) {                 if (cpy.dp == dir::up) {                     if (cpy.cc == dir::left) {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.y == b.y) return a.x < b.x;                             return a.y < b.y;                         });                     }                     else {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.y == b.y) return a.x > b.x;                             return a.y < b.y;                         });                     }                 }                 else if (cpy.dp == dir::down) {                     if (cpy.cc == dir::left) {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.y == b.y) return a.x > b.x;                             return a.y > b.y;                         });                     }                     else {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.y == b.y) return a.x < b.x;                             return a.y > b.y;                         });                     }                 }                 else if (cpy.dp == dir::right) {                     if (cpy.cc == dir::left) {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.x == b.x) return a.y < b.y;                             return a.x > b.x;                         });                     }                     else {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.x == b.x) return a.y > b.y;                             return a.x > b.x;                         });                     }                 }                 else if (cpy.dp == dir::left) {                     if (cpy.cc == dir::left) {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.x == b.x) return a.y > b.y;                             return a.x < b.x;                         });                     }                     else {                         sort(point[g].begin(), point[g].end(), [](Point &a, Point &b)->bool {                             if (a.x == b.x) return a.y < b.y;                             return a.x < b.x;                         });                     }                 }                 Point res = Point(point[g][0].y + dy[cpy.dp], point[g][0].x + dx[cpy.dp]);                 if (!isout(res.y, res.x) && arr[res.y][res.x] != 'X') {                     printf("%c", arr[res.y][res.x]);                     flag = true;                     info.y = res.y, info.x = res.x;                     info.dp = cpy.dp; info.cc = cpy.cc;                     break;                 }                 if(!j) cpy.cc += 2; cpy.cc %= 4;             }             if (flag) break;             cpy.dp += 1; cpy.dp %= 4;         }         if (!flag) break;     }              return 0; } Colored by Color Scripter

cs

C++ 디자인패턴 (Command Pattern)

Command Pattern

요구사항, 요청사항을 객체로 캡슐화하여 다양한 종류를 넣을 수 있다. 

또한 작업취소(undo)기능도 가능하다.

클래스 다이어그램과 코드는 wiki에서 가져왔다.

#include <iostream> #include <vector> #include <string> using namespace std; class Command { public:     virtual void execute(void) = 0;     virtual ~Command(void) {}; }; class Ingredient : public Command { public:     Ingredient(string amount, string ingredient) {         _ingredient = ingredient;         _amount = amount;     }     void execute(void) {         cout << " *Add " << _amount << " of " << _ingredient << endl;     } private:     string _ingredient;     string _amount; }; class Step : public Command { public:     Step(string action, string time) {         _action = action;         _time = time;     }     void execute(void) {         cout << " *" << _action << " for " << _time << endl;     } private:     string _time;     string _action; }; class CmdStack { public:     void add(Command *c) {         commands.push_back(c);     }     void createRecipe(void) {         for (vector<Command*>::size_type x = 0; x<commands.size(); x++) {             commands[x]->execute();         }     }     void undo(void) {         if (commands.size() >= 1) {             commands.pop_back();         }         else {             cout << "Can't undo" << endl;         }     } private:     vector<Command*> commands; }; int main(void) {     CmdStack list;     //Create ingredients     Ingredient first("2 tablespoons", "vegetable oil");     Ingredient second("3 cups", "rice");     Ingredient third("1 bottle", "Ketchup");     Ingredient fourth("4 ounces", "peas");     Ingredient fifth("1 teaspoon", "soy sauce");     //Create Step     Step step("Stir-fry", "3-4 minutes");     //Create Recipe     cout << "Recipe for simple Fried Rice" << endl;     list.add(&first);     list.add(&second);     list.add(&step);     list.add(&third);     list.undo();     list.add(&fourth);     list.add(&fifth);     list.createRecipe();     cout << "Enjoy!" << endl;     return 0; } Colored by Color Scripter

cs