orz qyc
看成一個人 \(i\) 向 \(p_i\) 連邊，每個點的入度出度都為 \(1\) 。那麼就是若幹個環，每次可以選擇一條邊将這條邊兩端的端點染色，求 \(k\) 次染色後，最大和最小有顔色點的個數數。
最大值發現可以貪心，偶數長度的環可以用長度除以 \(2\) 次染色全部染色，每次染色的貢獻都拉滿了。奇數長度的環可以用長度減一除以 \(2\) 次染色将除了一個點其他全部染色，剩下的一個點最後還有染色機會再染。
最小值的話，每個環第一次開始染它色一定是貢獻為 \(2\)，基于貪心先不開其他的環，再繼續對這個環染色，每次貢獻為 \(1\)，到最後一步貢獻為 \(0\)。換而言之，開了一個環就将它染色到底。
發現對于一個長度為 \(a_i\) 的環，将其全部染色次數為 \(a_i\)，貢獻為 \(a_i\)。那麼一定想讓若幹個 \(a_i\) 組成 \(k\)，否則 \(k\) 多開的沒染完色的那個環會多貢獻 \(1\)。
問題轉化為給定若幹個正整數 \(a_i\)，其和為 \(n\)，問能不能挑出一些 \(a_i\) 使得和為 \(k\)。也就是 01 背包可行性問題。
發現
bitset
和分治 NTT 都不大能過，注意到對 \(a_i\) 總和的限制，不同的 \(a_i\) 僅有 \(\mathcal{O}(\sqrt{n})\) 個，把多個同樣的物品合成一個物體有不同的次數，就變成了一個多重背包問題。
再加個二進制分組優化就沖過去了，時間複雜度不大會算反正能過。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
typedef long long ll;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T Abs(T x) { return x < 0 ? -x : x; }
template <typename T> T chkmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T>
T &read(T &r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = (r << 3) + (r <<1) + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
const int N = 1000010;
int n, p[N], a[N], m, k, ans1, ans2;
bool vis[N];
int ct[N], b[N], c[N], us[N];
std::bitset<1000001>f;
void dfs(int x, int s) {
if(vis[x]) {
a[++m] = s;
return ;
}
vis[x] = 1;
dfs(p[x], s+1);
}
signed main() {
read(n); read(k); int _n = n;
for(int i = 1; i <= n; ++i) read(p[i]);
for(int i = 1; i <= n; ++i)
if(!vis[i])
dfs(i, 0);
n = m;
std::sort(a + 1, a + n + 1);
int k_ = k;
for(int i = 1; i <= n; ++i) {
if(!k_) break ;
int t = Min(a[i] / 2, k_);
ans2 += t * 2; k_ -= t;
}
for(int i = 1; i <= n; ++i)
if((a[i] & 1) && k_)
++ans2,
--k_;
//
for(int i = 1; i <= _n; ++i) ct[a[i]]++;
m = 0;
for(int i = 1; i <= _n; ++i)
if(ct[i])
b[++m] = i,
c[m] = ct[i];
f[0] = 1;
for(int i = 1; i <= m; ++i) {
int tc = c[i];
for(int j = 1; tc; j <<= 1) {
int t = Min(j, tc);
f |= f << (b[i] * t),
tc -= t;
}
}
if(f[k]) ans1 = k;
else ans1 = k+1;
printf("%d %d\n", ans1, ans2);
return 0;
}