티스토리 뷰
점점 다이아가 많아지고 있다. 아무래도 몇 주 정도만 더 하게 될 것 같은데, 얼마 뒤에 루비가 나올 수도 있을 것 같다.
A. Make America Grade Again
역시 문제에 적힌 것을 그대로 구현하면 되는 문제이다.
l,h,p,e,n=map(int,input().split())
dct = {'l': [0, 0], 'h': [0, 0], 'p': [0, 0], 'e': [0, 0]}
for i in range(n):
s = list(input().split())
s[0] = s[0].lower()
r = s[-1].split('/')
dct[s[0][0]][0] += int(r[0])
dct[s[0][0]][1] += int(r[1])
ans = 0.0
ans += l * dct['l'][0] / dct['l'][1]
ans += h * dct['h'][0] / dct['h'][1]
ans += p * dct['p'][0] / dct['p'][1]
ans += e * dct['e'][0] / dct['e'][1]
print(int(ans))B. 좋은 노드 집합 찾기
트리 DP의 고전 문제 중 하나인 SNS와 거의 똑같은 문제이지만 추가 조건이 있다.
$DP[x][d]$를 다음과 같이 정의하자.
- $DP[x][d]$는 $x$의 서브트리에서 좋은 노드 집합의 최대 점수 합. 단, $d=0$인 경우 $x$가 포함되어서는 안 되고, $d=1$인 경우 $x$는 포함되어야 한다.
이때 $DP[x][1]$은 $\sum_y DP[y][0]$으로 쉽게 구할 수 있다. ($y$는 $x$의 자식) $DP[x][0]$은 $\max(DP[y][0], DP[y][1])$의 합으로 구할 수 있는데, 이때 $DP[y][1]$이 적어도 하나는 쓰여야 한다. 먼저 $DP[y][0]$을 모두 더해 주고, 적당한 배열에 $DP[y][1] - DP[y][0]$의 값을 모두 저장해 준 뒤 정렬하자. 이후 가장 큰 값을 $DP[x][0]$에 더하고, 남아있는 값들 중 양수를 $DP[x][0]$에 모두 더하면 된다.
시간 복잡도는 $O(n \log n)$인데 $O(n)$으로 쉽게 줄일 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int n, root;
ll arr[100002];
vector<int> link[100002];
ll DP[100002][2];
void dfs(int x){
DP[x][0] = 0, DP[x][1] = arr[x];
vector<ll> vec;
for(int y: link[x]){
dfs(y);
DP[x][1] += DP[y][0];
DP[x][0] += DP[y][0];
vec.push_back(DP[y][1] - DP[y][0]);
}
sort(vec.begin(), vec.end());
if(!vec.empty()){
DP[x][0] += vec.back(); vec.pop_back();
while(!vec.empty() && vec.back() > 0) DP[x][0] += vec.back(), vec.pop_back();
}
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]), link[i].clear();
for(int i=1; i<=n; i++){
int x;
scanf("%d", &x);
if(!x) root = i;
else link[x].push_back(i);
}
dfs(root);
printf("%lld\n", max(DP[root][0], DP[root][1]));
}
}C. 아이템
거꾸로 생각할 것이다. 다음과 같은 방식으로 생각하는 것이 좋다.
- 현재 step $d$를 정의하자. $d$를 $59$부터 시작해 $0$까지 내려간다.
- 맨 마지막에 끝낼 정수 $x$를 정한다. 또한 현재 아이템을 주운 횟수 $c$를 관리한다. 처음에 $c=1$이다. ($x$만 주웠다고 생각)
- $d$번 step에서는 하위 $d$비트가 $x$와 같은 수의 개수 $p$를 찾는다. $p$가 $c$보다 크다면, 새로이 주울 수 있는 아이템이 생겼다는 뜻이다. 해당 아이템을 줍는다. 그리고 $c$를 1 늘린다.
- 만약 새로 아이템을 주울 수 없다면($p=c$) 아무것도 하지 않고 $d$를 1 줄인다.
이제 위 알고리즘을 구현할 것인데, 저 $p$를 빠르게 구하는 것이 문제의 핵심이다. 생각하기 쉬운 방법은 trie를 쓰는 것인데 이 풀이는 조금 재미없다. 트라이를 안 쓰는 멋진 풀이가 있다.
겹치는 수 처리는 쉬우므로, 편의상 $X_i$가 모두 서로 다르다고 생각하자. 이때 $d$번 step에서는 현재 수와 이진수로 나타냈을 때 끝 $d$자리가 같은 수의 개수를 찾아야 한다. 이것을 현재 상태로 구하는 것은 조금 어려우니, 모든 수의 비트를 반대 순서로 바꿔 주자. 이렇게 하면 앞 $d$자리가 같은 수를 세면 되는데, 사전에 정렬을 해 놓는다면 이 수들은 구간을 이룬다는 사실을 확인할 수 있다. 이 수들이 $L[d]$번부터 $R[d]$번까지의 구간을 이룬다고 하자.
현재 보고 있는 수를 $i$번 수라고 하자. 다음 알고리즘을 반복한다.
- 각 $d$에 대해, 만약 $L[d] \le i \le R[d]$라면 이 값을 그대로 이용해도 된다.
- 만약 $R[d] < i$라면 (이 경우 알고리즘의 특성상 무조건 $i = R[d] + 1$일 것이다), $L[d] = R[d] = i$로 두고, $R[d]+1$번째 수를 구간에 넣을 수 있다면 $R[d]$에 1을 더하는 작업을 반복한다.
이제 남은 부분을 구현하면 문제를 맞을 수 있다.
시간 복잡도는 $O(N (\log N + \log X))$이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 60;
int n;
ll arr[200002];
ll BITS[62];
int L[62], R[62];
int ans;
int main(){
BITS[0] = (1LL << B) - 1;
for(int i=1; i<B; i++) BITS[i] = BITS[i-1] - (1LL << (i-1));
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
for(int i=1; i<=n; i++){
ll v = 0;
for(int j=0; j<B; j++) if((arr[i]>>j)&1) v += 1LL << (B-1-j);
arr[i] = v;
}
sort(arr+1, arr+n+1);
ll prv = -1, same = 0;
for(int i=1; i<=n; i++){
if(prv != arr[i]) prv = arr[i], same = 1;
else same++;
int c = same;
for(int d=0; d<B; d++){
if(R[d] < i){
L[d] = R[d] = i;
while(R[d] < n && (arr[i] & BITS[d]) == (arr[R[d]+1] & BITS[d])) R[d]++;
}
if(R[d] - L[d] + 1 > c) c++;
}
ans = max(ans, c);
}
printf("%d", ans);
}D. Date
복잡한 케이스워크 DP 문제이다. 이 문제는 아무리 봐도 DP이지만 대체 그 구현을 어떻게 해야 가장 짧을지를 생각하는 부분에 초점이 맞춰져 있다. 이 문제의 경우 거꾸로 DP를 돌려서 생각하는 것이 더 쉽다고 생각했다. (아닐 수도 있다.)
다음과 같이 상태를 정의하자.
- 일 부분
- $0$: 시작 (아직 아무 문자도 포함하지 않음)
- $1$: 끝자리 $1$
- $2$: 끝자리 $2$, $3$, …, $8$ 중 하나
- $3$: 끝자리 $9$
- $4$: 끝자리 $0$ (이 경우 앞에 무조건 1, 2, 3 중 하나를 추가해야 한다.)
- $5$: 일이 $10$ 이상 $28$ 이하
- $6$: 일이 정확히 $29$
- $7$: 일이 정확히 $30$
- $8$: 일이 정확히 $31$
- $9$, $10$, $11$, $12$: 각각 28 이하, 29, 30, 31인 경우
/까지 포함- 상태가 $9$인 경우 모든 달이 가능하고, $10$인 경우 윤년인 $2$월 또는 다른 아무 달, $11$인 경우 $2$월을 제외한 모든 달, $12$인 경우 1, 3, 5, 7, 8, 10, 12월만 가능하다.
- 달 부분
- $13$: 끝자리 1이고, 30일 이하 (1월, 11월 모두 가능)
- $14$: 끝자리 1이고, 31일 (1월만 가능)
- $15$: 끝자리 2이고, 일이 $28$ 이하 (이 경우 제한이 없다.)
- $16$: 끝자리 2이고, 일이 정확히 $29$ (이 경우 윤년인 2월 또는 12월이여야 한다.)
- $17$: 끝자리 2이고, 일이 30 또는 31 (이 경우 12월이여야 한다.)
- $18$: 끝자리 0 (이 경우 무조건 10월이여야 한다.)
- $19$: 3-12월 중 하나
- $20$: 달 앞의
/까지 포함했고, 윤년임 - $21$: 달 앞의
/까지 포함했고, 윤년이어도 되고 아니어도 됨
- 연 부분
- 윤년 조건을 판별하는 구역 (윤년임이 확정되지 않은 상태)
- $22$: 끝 자리가 0
- $23$: 끝 자리가 2, 6 중 하나
- $24$: 끝 자리가 4, 8 중 하나 (23이나 24번 상태의 경우 다음 수에 따라 윤년 여부가 바로 확정된다.)
- $25$: 끝 두 자리가 00
- $26$: 끝 세 자리가 000
- $27$: 끝 세 자리가 200, 600 중 하나
- $28$: 끝 세 자리가 400, 800 중 하나 (26, 27이나 28번 상태의 경우 다음 수에 따라 윤년 여부가 바로 확정된다.)
- 윤년 조건이 만족되었거나, 윤년일 필요가 없는 구역
- $29$: 현재로서 가장 왼쪽 자리가 $0$이라, 수를 하나 더 받아야 함
- $30$: 이곳에서 끝나도 됨
- 윤년 조건을 판별하는 구역 (윤년임이 확정되지 않은 상태)
이제 각각의 경우에 대한 코드를 잘 구현하면 된다. 나는 코드로 직접 구현하는 대신 31 x 11 전이표를 구성했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007;
const int X = -1;
const int ST = 31;
const int state[ST][11] = { /// 0 1 2 3 4 5 6 7 8 9 /
4, 1, 2, 2, 2, 2, 2, 2, 2, 3, X, /// 0
X, 5, 5, 8, X, X, X, X, X, X, 9, /// 1
X, 5, 5, X, X, X, X, X, X, X, 9, /// 2
X, 5, 6, X, X, X, X, X, X, X, 9, /// 3
X, 5, 5, 7, X, X, X, X, X, X, X, /// 4
X, X, X, X, X, X, X, X, X, X, 9, /// 5
X, X, X, X, X, X, X, X, X, X, 10, /// 6
X, X, X, X, X, X, X, X, X, X, 11, /// 7
X, X, X, X, X, X, X, X, X, X, 12, /// 8
18, 13, 15, 19, 19, 19, 19, 19, 19, 19, X, /// 9
18, 13, 16, 19, 19, 19, 19, 19, 19, 19, X, /// 10
18, 13, 17, 19, 19, 19, 19, 19, 19, 19, X, /// 11
18, 14, 17, 19, X, 19, X, 19, 19, X, X, /// 12
X, 19, X, X, X, X, X, X, X, X, 21, /// 13
X, X, X, X, X, X, X, X, X, X, 21, /// 14
X, 19, X, X, X, X, X, X, X, X, 21, /// 15
X, 19, X, X, X, X, X, X, X, X, 20, /// 16
X, 19, X, X, X, X, X, X, X, X, X, /// 17
X, 19, X, X, X, X, X, X, X, X, X, /// 18
X, X, X, X, X, X, X, X, X, X, 21, /// 19
22, X, 23, X, 24, X, 23, X, 24, X, X, /// 20
29, 30, 30, 30, 30, 30, 30, 30, 30, 30, X, /// 21
25, X, 30, X, 30, X, 30, X, 30, X, X, /// 22
X, 30, X, 30, X, 30, X, 30, X, 30, X, /// 23
29, X, 30, X, 30, X, 30, X, 30, X, X, /// 24
26, X, 27, X, 28, X, 27, X, 28, X, X, /// 25
29, X, 30, X, 30, X, 30, X, 30, X, X, /// 26
X, 30, X, 30, X, 30, X, 30, X, 30, X, /// 27
29, X, 30, X, 30, X, 30, X, 30, X, X, /// 28
29, 30, 30, 30, 30, 30, 30, 30, 30, 30, X, /// 29
29, 30, 30, 30, 30, 30, 30, 30, 30, 30, X, /// 30
};
int n;
char str[100005];
ll DP[100005][32];
int main(){
scanf("%d %s", &n, str+1);
DP[n+1][0] = 1;
for(int i=n; i>=1; i--){
for(int j=0; j<ST; j++) DP[i][j] = DP[i+1][j]; /// 아무것도 하지 않고 그대로 가져올 경우
/// 이제 숫자를 사용할 때에 대한 전이를 추가한다
int p = isdigit(str[i]) ? str[i] - '0' : 10;
for(int j=0; j<ST; j++){
if(state[j][p] != X) DP[i][state[j][p]] += DP[i+1][j];
}
for(int j=0; j<ST; j++) DP[i][j] %= MOD; /// 나머지 처리는 한 번에
// for(int j=0; j<ST; j++) printf("[%d][%d]: %lld, \t", i, j, DP[i][j]);
// puts("");
// puts("");
}
printf("%lld", (DP[1][24] + DP[1][28] + DP[1][30]) % MOD);
}E. Roulette
먼저 자신이 총 $T$개의 복권을 가졌을 때 승자가 되기 위한 리롤 횟수의 기댓값이 얼마인지 알아보자. 이 경우 총 복권의 수는 $S+T$개이고, $\frac{T}{S+T}$의 확률로 당첨된다. 당첨되지 않는다면 $R$원을 내고 추가로 돌려야 한다. 추첨 기댓값을 $E_1$이라고 한다면, $E_1 = \frac{T}{S+T} \times 0 + \frac{S}{S+T} \times (R + E_1)$이다. 따라서 $\frac{T}{S+T} E_1 = \frac{S}{S+T} R$이고, $E_1 = \frac{S}{T} R$이다.
$T$개 이상의 복권을 가지는 최소 비용을 $f(T)$라고 한다면, 답은 $\min f(T) + \frac{S}{T} R$임을 알 수 있다.
이제 답이 될 수 있는 $T$의 범위가 무엇인지 알아보자. 만약 현재 내가 복권이 엄청나게 많이 있다면, 더 이상 앨범을 구매하는 것이 무조건 손해가 되는 지점이 생긴다. 현재 내가 구매하고자 하는 앨범이 가격 $a$로 $b$개의 복권을 추가한다고 해 보자. 이 앨범이 이득이 될 조건은 $\frac{S}{T}R > \frac{S}{T+b}R + a$, 즉 $T(T+b) < \frac{SbR}{a}$이다. $T < \sqrt{\frac{SbR}{a}}$라는 대략적인 상한을 얻고, 저 값은 $b = 5000$, $a = 1$일 때 약 $7.1 \times 10^7$로 최대가 된다. 따라서 복권의 최적 값이 7천만 정도를 넘지 않는다는 것을 알 수 있다. 하지만 냅색으로 계산하기에는 터무니없이 많은 양이라는 사실은 여전하다.
앨범의 종류는 $N$가지지만, 이들 중 실질적으로 중요한 것은 $\max A_i$가지이다. $A_i$가 같은 앨범은 $B_i$가 같은 것을 사는 것이 항상 유리하기 때문이다. 또한 $A_i$가 더 작으면서 $B_i$가 더 높은 앨범이 있다면 이쪽을 사는 것이 훨씬 이득이다. 이렇게 답이 될 가능성이 있는 복권을 추려내고 나면 이 복권들은 $A_i$와 $B_i$가 모두 증가하는 형태가 될 것이다. ($A_i \le 300$이므로 복권의 종류가 300개 미만이 된다.)
또한, 앨범 종류를 다양하게 사는 것도 좋지 않다는 사실을 알 수 있다. 애매하게 복권을 살 바에 $B_i / A_i$가 가장 큰 앨범을 사는 것이 낫기 때문이다. 물론 이 앨범만 사는 것도 최적이 아닐 수 있다. 그러나 다음 사실을 보일 수 있다. $B_t / A_t$가 가장 큰 앨범 중 임의로 하나를 골라 $t$번 앨범이라고 하자.
- $t$번 앨범이 아닌 앨범을 $\max A_i \le 300$개 이하로 구매하는 최적해가 존재한다.
- 증명: $t$번 앨범이 아닌 앨범을 $\max A_i$개 초과로 구매하는 최적해가 있다고 가정해 보자. 각각의 앨범의 가격을 $[a_1, a_2, \cdots, a_k]$라고 하자. $k > \max A_i$이므로 $k > A_t$이다. $p_i = a_1 + \cdots + a_i$, 즉 누적 합으로 정의하자. $p_i$는 총 $k$가지가 있는데, 이를 $A_t$로 나눈 나머지가 같은 두 개의 $p_i$가 반드시 존재한다(비둘기집의 원리). 이 둘을 $p_i, p_j$라고 하면, $a_{i+1} \cdots a_j$ 의 앨범은 가격 합이 $A_t$의 배수이다. 이 앨범을 전부 취소하고 $t$번 앨범으로 대체하면 무조건 이득이다 ($t$의 정의에 의해).
따라서 $t$번 앨범이 아닌 앨범은 $300$개 이하이고, 그 가격 합은 $90000$ 이하임을 알 수 있다.
이제 $T$의 값을 $t$번 앨범으로 구매한 비용 + 그 외의 비용으로 분리해 생각할 수 있게 되었다. $90000$ 정도의 범위로는 충분히 냅색을 시행할 수 있다. $DP[x]$를 $x$ 이하의 비용으로 얻을 수 있는 최대 복권 수로 정의한다. $x \le 90000$까지에 대해 계산하면 $300^3$ 정도의 연산에 가능하다. 사실 개수가 $300$개 이하라는 사실이 여기서 크게 중요하지는 않고, 비용 $90000$ 이하라는 조건만 이용할 것이다.
이제 각 $x$에 대해 $t$번 앨범을 구매하는 최적의 개수를 찾을 것이다. 현재 우리가 가진 값은 $t$번 앨범 이외의 구매 비용 (사실 $t$번 앨범이 들어가 있어도 상관이 없고, 냅색도 그렇게 한다) $x$, 얻은 복권 수 $D[x]$이고, 여기서 $t$번 앨범을 구매할 개수 $v$를 찾아야 한다. 이때 $v$가 정해지면 기댓값은 $x + vA_t + \frac{SR}{D[x]+vB_t}$이다. 이 함수는 $v$에 대해 unimodal하므로, 삼분 탐색을 이용할 수 있다. 하지만 삼분탐색이 너무 느려서 시간 초과가 난다. 저 위의 식을 $f(v)$로 두고 $f'(v)$를 계산하면 식이 최소일 때의 $v$ 값을 알아낼 수 있다. 그 근처의 정수값 몇 개를 후보로 테스트해 주면 시간복잡도 $O(X^3)$에 문제를 해결할 수 있다. ($X = \max A_i$)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 300;
struct Frac{
ll a, b;
Frac(){b = 1;}
Frac(ll _a, ll _b){
ll g = __gcd(_a,_b);
a = _a/g, b = _b/g;
}
Frac operator+(ll r)const{
return Frac(a+r*b, b);
}
bool operator<(const Frac &r)const{
return __int128(a) * r.b < __int128(r.a) * b;
}
};
int n, t;
ll S, R;
ll arr[302];
ll D[90002];
Frac ans (1e18, 1);
inline Frac calc(ll i, ll s, ll v){
return Frac(S*R, s+v*arr[t]) + (i+v*t);
}
int main(){
scanf("%d %lld %lld", &n, &S, &R);
for(int i=1; i<=n; i++){
int A, B;
scanf("%d %d", &A, &B);
arr[A] = max(arr[A], ll(B));
}
for(int i=1; i<=MX; i++) arr[i] = max(arr[i], arr[i-1]);
for(int i=1; i<=MX*MX; i++){
for(int j=1; j<=i && j<=MX; j++){
D[i] = max(D[i], D[i-j] + arr[j]);
}
}
t = 1;
for(int i=2; i<=MX; i++) if(arr[i]*t>arr[t]*i) t = i;
for(int i=0; i<=MX*MX; i++){
ll val = round((sqrt(double(arr[t])*S*R/t) - D[i]) / arr[t]);
ll L = max(0LL, val - 3), R = val + 3;
for(ll v=L; v<=R; v++) ans = min(ans, calc(i, D[i], v));
}
printf("%lld %lld", ans.a, ans.b);
}F. 팰린드롬의 개수
문제가 풀기 싫게 생겨서 리롤했다.
F. N과 M
의외로 등장한 정수론 문제다.
먼저 오일러 정리를 알아야 한다. 문제에서 $N^{N^{N^{…}}}$을 $M$으로 나눈 나머지를 구하라고 하는데, 먼저 $N$과 $M$이 서로소가 아닌 경우부터 생각해 보자.
$g = gcd(N, M)$으로 정의하자. 이때 지수 부분이 매우 커지면 $g$의 지수가 무한히 커지므로 $g$로 나눈 나머지가 $0$이 된다. 따라서 $g$뿐만 아니라 $g$의 모든 소인수 거듭제곱으로로 나눈 나머지가 $0$이 될 것이다. $M$과 $g^\infty$의 최대공약수 $G$에 대해, $M$을 $G$로 나누고, 나중에 CRT를 이용해 원래 답을 복원해 주자.
이제 $N$과 $M$이 서로소인 경우에 대해서 생각해 보자. 오일러 정리에 의해 $N^{\phi(M)} \bmod M = 1$이다. 따라서 $N^{N^{\cdots}} \bmod \phi(M)$을 구하면 충분하다. 그런데 이것을 구하기 위해서는 다시 $N^{N^{\cdots}} \bmod \phi(\phi(M))$을 구하면 충분하다. 이 논리는 $\phi(M)$이 더 이상 줄어들지 않을 때까지 계속해서 지속할 수 있는데, $M > 1$이면 $\phi(M) < M$이므로 사실상 $M=1$까지 줄여야 한다는 결론에 도달한다. 그러나 실제로 돌려 보면 $\phi(M)$이 꽤나 빠르게 줄어들기 때문에, 이 방식으로도 문제를 맞을 수 있다.
결론적으로, 다음을 반복하면 된다.
- $M$에서 $N$의 소인수로 나누어지는 성분을 $G$라고 하자. $(N, G)$에 대한 답은 $0$이다. $(N, M/G)$에 대한 답을 구한다. $M' = M/G$라고 하자. $G=1$이면 답은 $0$이다.
- $(N, \phi(M'))$에 대한 답을 구하고, 이 답을 $v$라고 할 때, $N^v \bmod M'$을 구한다.
- CRT를 이용해 $M/G$로 나눈 나머지와 $G$로 나눈 나머지를 병합하고 답을 구한다.
코드의 pollard rho / miller rabin은 옛날부터 어딘가에서 가져와 템플릿처럼 쓰고 있는데 출처를 잊어버렸다. 아마 이 글로 추정되는데 확실하진 않다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll n, m;
ll phifunc[1000002];
bool isPrime[1000002];
vector<ll> alist = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
vector<ll> ans;
inline ll addmod(ll x, ll y, ll m) {
x %= m;
y %= m;
return (x >= m - y? x - (m - y) : x + y);
}
inline ll mulmod(ll x, ll y, ll m) {
x %= m;
y %= m;
ll r = 0;
while (y > 0) {
if (y % 2 == 1)
r = addmod(r, x, m);
x = addmod(x, x, m);
y /= 2;
}
return r;
}
ll powmod(ll x, ll y, ll m) {
x %= m;
ll r = 1ULL;
while (y > 0) {
if (y % 2 == 1)
r = mulmod(r, x, m);
x = mulmod(x, x, m);
y /= 2;
}
return r;
}
inline bool miller_rabin(ll n, ll a) {
ll d = n - 1;
while (d % 2 == 0) {
if (powmod(a, d, n) == n-1)
return true;
d /= 2;
}
ll tmp = powmod(a, d, n);
return tmp == n-1 || tmp == 1;
}
bool is_prime(ll n) {
if (n <= 1000000LL)
return isPrime[n];
if (n <= 10000000000LL) {
for (ll i = 2; i*i <= n; i++)
if (n % i == 0)
return false;
return true;
}
for (ll a : alist)
if (!miller_rabin(n, a))
return false;
return true;
}
void getPrime(){
for(int i=2; i<=1000000; i++){
isPrime[i] = 1;
}
for(int i=2; i<=1000; i++){
if(!isPrime[i]) continue;
for(int j=i*i; j<=1000000; j+=i){
isPrime[j] = 0;
}
}
}
void polard_rho(ll n) {
if(n==1) return;
if(is_prime(n)){
ans.push_back(n);
return;
}
int i = 0;
ll x = (ll)rand()*rand() % n;
ll y = x;
ll k = 2;
ll d = n;
while(1) {
i++;
x = (mulmod(x, x, n) - 1 + n) % n;
d = __gcd(abs(y - x), n);
if(d != 1) {
break;
}
if(i == k) {
y = x;
k *= 2;
}
}
if(d != n) {
polard_rho(d);
polard_rho(n / d);
return;
}
if(!(n & 1)) {
polard_rho(2);
polard_rho(d / 2);
return;
}
for(ll i = 3; i * i <= n; i += 2) if(n % i == 0) {
polard_rho(i);
polard_rho(d / i);
return;
}
}
ll phi(ll val){
if(val <= 1'000'000) return phifunc[val];
ans.clear();
polard_rho(val);
sort(ans.begin(), ans.end());
ll ret = val;
for(int l=0; l<(int)ans.size(); l++){
if(!l || ans[l] != ans[l-1]) ret = ret / ans[l] * (ans[l] - 1);
}
return ret;
}
ll mpow(ll x, ll y, ll mod){
if(!y) return 1;
if(y&1) return mpow(x, y-1, mod) * x % mod;
ll tmp = mpow(x, y>>1, mod);
return tmp*tmp%mod;
}
pair<ll, ll> extendedEuclidean(ll a, ll b){ /// ax+by=1의 해
if(b==0){
assert(a==1);
return make_pair(1LL, 0LL);
}
pair<ll, ll> tmp = extendedEuclidean(b, a%b);
return make_pair(tmp.second, tmp.first - tmp.second * (a/b));
}
inline ll mod(ll a, ll g){
if(a>=0) return a%g;
return (g - (-a)%g) % g;
}
ll calc(ll N, ll M){
ll G = 1;
{
ll g = __gcd(N, M);
while(__gcd(M, g) > 1){
ll tmp = __gcd(M, g);
G *= tmp;
M /= tmp;
}
}
if(M==1) return 0;
ll ph = phi(M);
ll val = mpow(N, calc(N, ph), M); /// val mod m, 0 mod G
pair<ll, ll> p = extendedEuclidean(M, G);
ll a = -p.first; /// a * m + B * G = 1
ll c = mod(a,G) * M + 1;
ll res = __int128(c) * val % (M*G);
assert(res % M == val && res % G == 0);
return res;
}
int main(){
for(int i=0; i<=1'000'000; i++) phifunc[i] = i;
for(int i=2; i<=1'000'000; i++){
if(phifunc[i] == i){
isPrime[i] = 1;
for(int j=i; j<=1'000'000; j += i) phifunc[j] -= phifunc[j] / i;
}
}
scanf("%d", &t);
while(t--){
scanf("%lld %lld", &n, &m);
printf("%lld\n", calc(n, m));
}
}G. Domes
기초적인 반평면 교집합 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace HalfPlaneIntersection{
// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
const long double eps = 1e-9, inf = 1e9;
// Basic point/vector struct.
struct Point {
long double x, y;
explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}
// Addition, substraction, multiply by constant, dot product, cross product.
friend Point operator + (const Point& p, const Point& q) {
return Point(p.x + q.x, p.y + q.y);
}
friend Point operator - (const Point& p, const Point& q) {
return Point(p.x - q.x, p.y - q.y);
}
friend Point operator * (const Point& p, const long double& k) {
return Point(p.x * k, p.y * k);
}
friend long double dot(const Point& p, const Point& q) {
return p.x * q.x + p.y * q.y;
}
friend long double cross(const Point& p, const Point& q) {
return p.x * q.y - p.y * q.x;
}
};
// Basic half-plane struct.
struct Halfplane {
// 'p' is a passing point of the line and 'pq' is the direction vector of the line.
Point p, pq;
long double angle;
Halfplane() {}
Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
angle = atan2l(pq.y, pq.x);
}
// Check if point 'r' is outside this half-plane.
// Every half-plane allows the region to the LEFT of its line.
bool out(const Point& r) {
return cross(pq, r - p) < -eps;
}
// Comparator for sorting.
bool operator < (const Halfplane& e) const {
return angle < e.angle;
}
// Intersection point of the lines of two half-planes. It is assumed they're never parallel.
friend Point inter(const Halfplane& s, const Halfplane& t) {
long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
return s.p + (s.pq * alpha);
}
};
// Actual algorithm
vector<Point> hp_intersect(vector<Halfplane>& H) {
Point box[4] = { // Bounding box in CCW order
Point(inf, inf),
Point(-inf, inf),
Point(-inf, -inf),
Point(inf, -inf)
};
for(int i = 0; i<4; i++) { // Add bounding box half-planes.
Halfplane aux(box[i], box[(i+1) % 4]);
H.push_back(aux);
}
// Sort by angle and start algorithm
sort(H.begin(), H.end());
deque<Halfplane> dq;
int len = 0;
for(int i = 0; i < int(H.size()); i++) {
// Remove from the back of the deque while last half-plane is redundant
while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
// Remove from the front of the deque while first half-plane is redundant
while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
// Special case check: Parallel half-planes
if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
// Opposite parallel half-planes that ended up checked against each other.
if (dot(H[i].pq, dq[len-1].pq) < 0.0)
return vector<Point>();
// Same direction half-plane: keep only the leftmost half-plane.
if (H[i].out(dq[len-1].p)) {
dq.pop_back();
--len;
}
else continue;
}
// Add new half-plane
dq.push_back(H[i]);
++len;
}
// Final cleanup: Check half-planes at the front against the back and vice-versa
while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
// Report empty intersection if necessary
if (len < 3) return vector<Point>();
// Reconstruct the convex polygon from the remaining half-planes.
vector<Point> ret(len);
for(int i = 0; i+1 < len; i++) {
ret[i] = inter(dq[i], dq[i+1]);
}
ret.back() = inter(dq[len-1], dq[0]);
return ret;
}
} // https://cp-algorithms.com/geometry/halfplane-intersection.html
using namespace HalfPlaneIntersection;
ll X, Y; int n;
Point arr[102];
int ord[102];
int main(){
cin >> X >> Y >> n;
for(int i=1; i<=n; i++) cin >> arr[i].x >> arr[i].y;
for(int i=1; i<=n; i++) cin >> ord[i];
vector<Halfplane> vec;
vec.emplace_back(Point(0, Y), Point(0, 0));
vec.emplace_back(Point(X, Y), Point(0, Y));
vec.emplace_back(Point(X, 0), Point(X, Y));
vec.emplace_back(Point(0, 0), Point(X, 0));
for(int i=1; i<n; i++) for(int j=i+1; j<=n; j++) vec.emplace_back(arr[ord[j]], arr[ord[i]]);
vector<Point> res = hp_intersect(vec);
long double ans = 0;
for(int i=2; i<(int)res.size(); i++){
ans += cross(res[i-1] - res[0], res[i] - res[0]);
}
printf("%.9Lf", abs(ans)/2);
}H. Ruka
문제가 풀기 싫게 생겨서 리롤했다.
H. Analyzing Contracts
다3을 리롤했더니 다2가 나왔다. 조금 고민해 봤는데 굉장히 복잡해 보여서 리롤했다.
H. Гарри и носки
간단히 문제 요약을 하면 다음과 같다.
- 길이 $N$의 수열 $A$가 있다.
- $f: {1, \cdots, n} \rightarrow {1 \cdots n}$으로 가는 일대일대응 함수 $f$를 정의할 때, $A_i = A_{f(i)}$인 것이 없게 하는 $f$는 몇 가지인가?
문제의 형태를 보았을 때 직접 세는 것은 많이 어려워 보이고 포함 배제의 원리를 이용해야 할 것 같다는 느낌이 온다.
그런데 포함 배제의 원리를 어떻게 이용할까? 보통 포함 배제의 원리를 이용할 때는 다음과 같이 한다.
- 어떤 조건 $C_1, C_2, \cdots, C_k$를 모두 만족하지 않는 해의 개수를 세어야 한다.
- 이를 위해 $S \subseteq {C_1, C_2, \cdots, C_k}$인 임의의 $S$에 대해, $S$ 안의 조건을 모두 만족하는 해의 개수를 세고 포함 배제의 원리를 적용한다.
이 문제에서는 각 조건 $C_i$를 $A_i = A_{f(i)}$로 표현할 수 있다. 이제 다음을 빠르게 구하면 문제를 해결할 수 있다.
- $S_i$: $S \subseteq {1, 2, \cdots, n }$이고 $|S| = i$인 모든 부분집합 $S$에 대해 다음 문제의 답의 합을 계산한다.
- $j \in S$인 모든 $j$에 대해 $A_j = A_{f(j)}$인 $f$의 개수가 얼마인가?
위 문제를 빠르게 풀기 위해 우선 $S$에 집중해 보자. 기존 수열 $A$에 등장하는 수가 $m$가지라고 하고, 각각의 빈도 수가 $t_1, t_2, \cdots, t_m$이라고 하자. 그리고 집합 $S$에는 이들이 각각 $u_1, u_2, \cdots, u_m$번 등장한다고 하자. 먼저 $j \in S$인 부분의 조건을 채워 보자. $i$번 종류의 수는 집합 $S$에 총 $u_i$번 등장하는데, $t_i$개의 후보를 사용할 수 있다. $u_i$개의 수를 고르는 방법이 $\binom{t_i}{u_i}$가지이고, $t_i$개의 수 중 하나씩 골라 $u_i$개에 배치하는 방법의 수는 ${}_{t_i} P_{u_i}$이다. 모든 작업을 끝내면 $n -|S|$개의 수가 남고, 이들은 무작위로 배치해도 좋다. 따라서, $S$가 정해지면, 해당 조건을 만족하는 경우의 수는 $\prod_i \binom{t_i}{u_i} {}_{t_i} P_{u_i} \times (n-|S|)!$임을 알 수 있다.
이제 $|S|$를 고정하고, 저 값의 합을 구해 보자. $|S| = k$로 고정하자. 뒤의 $(n-k)!$ 항은 고정이므로 앞부분의 합만 계산하면 된다. 여기서는 다음과 같은 DP를 해 보자.
DP에 앞서, 위의 $t_i$, $u_i$의 정의를 이용하기로 하자. $t$의 값은 이미 정해져 있고, $u$의 값은 집합 $S$의 선택에 따라 달라진다는 점을 생각하자.
- $DP[i][j]$: $i$번 종류의 수까지 보았고, $u_1 + \cdots + u_i=j$인 경우에 $\prod_{1 \le x \le i} \binom{t_x}{u_x}{}_{t_x}P_{u_x}$의 합
이 DP를 계산했을 때, $DP[m][k]$의 값이 우리가 원하는 값이다. 위 DP는 $O(mn^2)$에 쉽게 계산할 수 있다. 모든 $(i, j) \rightarrow (i+1, j+b)$ 로 가는 전이에 대해 $(i, j, b)$ 쌍을 둘러보면 된다. 그러나 여기서 $n$을 하나 떼는 방법이 필요하다. 이를 위해서는 전이식을 한 번 써 볼 필요가 있다. 그런데 사실 각 $i+1$에 대해 가능한 $b$의 최댓값은 $t_{i+1}$이다. 그래서 저 DP는 $O(mn^2)$이 아니라 $O(mn)$이고, 저 DP를 짜면 맞을 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
int n, m;
int arr[3002], t[3002];
ll fact[3002], factInv[3002];
ll DP[3002][3002];
inline ll perm(int n, int k){
if(n<k) return 0;
return fact[n] * factInv[n-k] % MOD;
}
inline ll comb(int n, int k){
if(n<k) return 0;
return fact[n] * factInv[n-k] % MOD * factInv[k] % MOD;
}
int main(){
fact[0] = 1;
for(int i=1; i<=3000; i++) fact[i] = fact[i-1] * i % MOD;
factInv[3000] = mpow(fact[3000], MOD-2);
for(int i=2999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
sort(arr+1, arr+n+1);
for(int l=1; l<=n; l++){
int r = l;
while(r<n && arr[l]==arr[r+1]) r++;
t[++m] = r-l+1;
l=r;
}
DP[0][0] = 1;
for(int i=1; i<=m; i++){
for(int j=0; j<=n; j++){
if(!DP[i-1][j]) continue;
for(int b=0; b<=t[i]; b++){
DP[i][j+b] += DP[i-1][j] * perm(t[i], b) % MOD * comb(t[i], b) % MOD;
}
}
for(int j=0; j<=n; j++) DP[i][j] %= MOD;
}
ll ans = 0;
for(int i=0; i<=n; i++){
ans += DP[m][i] * fact[n-i] % MOD * (i%2 ? -1 : 1);
if(ans < 0) ans += MOD;
ans %= MOD;
}
printf("%lld", ans);
}'문제풀이 > 랜덤 마라톤' 카테고리의 다른 글
| 랜덤 마라톤 11주차 (최종) (0) | 2024.08.21 |
|---|---|
| 랜덤 마라톤 10주차 (0) | 2024.08.13 |
| 랜덤 마라톤 8주차 (0) | 2024.07.30 |
| 랜덤 마라톤 7주차 (0) | 2024.07.24 |
| 랜덤 마라톤 6주차 (0) | 2024.07.14 |