[Codeforces] combinatorics (R1600) Part.2

题单:https://codeforces.com/problemset?tags=combinatorics,1201-1600

288B. Polo the Penguin and Houses

原题指路:https://codeforces.com/problemset/problem/288/B

题意 ($2\mathrm{s}$)

有编号$1\sim n$的$n$个房间,其中$i$号房间上有一个数字$p_i\in [1,n]$.玩家在$i$号房间时,下一个房间要前往的房间是$p_i$.已知玩家从编号$1\sim k$的房间出发时,他能走到$1$号房间;从编号$(k+1)\sim n$的房间出发时,他不能走到$1$号房间;从$1$号房间出发时,他能经若干步返回$1$号房间.求有多少组$p_1,\cdots ,p_n$满足上述条件,答案对$1\mathrm{e}9+7$取模.

第一行输入两个整数 n , k    ( 1 ≤ n ≤ 1000 , 1 ≤ k ≤ min ⁡ { 8 , n } ) n,k\ \ (1\leq n\leq 1000,1\leq k\leq \min\{8,n\}) n,k  (1≤n≤1000,1≤k≤min{8,n}).

[简单题意] 构造一个包含编号$1\sim n$个节点的有向图,其中$1\sim k$号节点都存在到达$1$号节点的路径,$(k+1)\sim n$号节点都不存在到达$1$号节点的路径,求方案数.

思路

①对$1\sim k$号节点,先构造一个包含$k$个节点的Cayley树,有$k^{k-2}$种方案.任选一个节点为根节点,有$k$种方案.

​ 取$p_i=f{a}_i,p_{root}=1$,在树上加一条边使得出现一个包含节点$1$的有向环,显然这是满足条件的.

②对$(k+1)\sim n$号节点,每个节点都能与$(k+1)\sim n$号节点中的任一节点相连,有$(n-k{)}^{n-k}$种方案.

综上,$ans=k^{k-1}(n-k{)}^{n-k}$.

代码

const int MOD = 1e9 + 7;

void solve() {
  int n, k; cin >> n >> k;
  cout << qpow(k, k - 1, MOD) * qpow(n - k, n - k, MOD) % MOD;
}

int main() {
  solve();
}

319A. Malek Dance Club

原题指路:https://codeforces.com/problemset/problem/319/A

题意

有$2^n$个男生和$2^n$个女生,分别编号$1\sim (2^n-1)$.给定一个$n$位二进制数$x$,要求$i$号男生与$(i\mathrm{xor}x)$号女生组队,记作$(i,i\mathrm{xor}x)$.定义一个组队方案的复杂程度为满足$a<c$且$b>d$的数对$(a,b)$和$(c,d)$的个数,求该方案的复杂程度,答案对$1\mathrm{e}9+7$取模.

第一行输入一个长度为$n(1\le n\le 100)$的二进制数$x$.

思路I

考察一个两边各包含编号$0\sim (2^n-1)$的$2^n$个节点的二分图,将组队的节点间连线,显然任意两线段的交点会使得复杂程度$+1$.

如下图,考察在$0-1$串$x$前补$0$和补$1$产生的影响:

=

①在$x$前补$0$时,相同的结构复制了一遍.

②在$x$前补$1$时,相同的结构复制了一遍后,右边节点的上半部分与下半部分交换.

设长度为$n$的$0-1$串$x$的复杂程度为$f(\overline{x})$,则$f(\overline{0x})=2f(x),f(\overline{1x})=2f(x)+2^{2n}$.

由数学归纳法:$ans=x\cdot 2^{n-1}$.注意要对二进制数$x$做大数取模.

代码I

const int MOD = 1e9 + 7;

void solve() {
  string s; cin >> s;
  reverse(all(s));

  int n = s.length();
  int x = 0;
  for (int i = 0; i <= n; i++) 
    if (s[i] == '1') x = ((ll)x + qpow(2, i, MOD)) % MOD;
  cout << qpow(2, n - 1, MOD) * x % MOD;
}

int main() {
    solve();
}

思路II

注意到$0\sim (2^n-1)$的二进制表示中,前$2^{n-1}$个数的首位为$0$,后$2^{n-1}$个数的首位为$1$.

①$x$首位为$0$时,原数异或后首位不变,则$0\sim (2^n-1)$中的逆序对数即$0\sim (2^{n-1}-1)$中的逆序对数$+2^{n-1}\sim (2^n-1)$中的逆序对数.注意到这两部分数除首位外相同,而首位不共线复杂程度,故答案即第一部分的复杂程度$\times 2$.

②$x$首位为$1$时,原数异或后首位取反,则异或后的数中前$2^{n-1}$个数$>$后$2^{n-1}$个数,这导致在情况①的基础上增加了$2^{n-1}\cdot 2^{n-1}=2^{2(n-1)}$个逆序对.

设$0\sim (2^n-1)$异或上$x$得到的逆序对数为$f(n,x)$,$x$去掉首位后的数为$g(x)$,$x$的首位为$h(x)$,

则$f(n,x)=\{\begin{array}{l}0,n=1\text{且}x=0\\ 1,n=1\text{且}x=1\\ 2\cdot f(n-1,g(x)),h(x)=0\\ 2\cdot f(n-1,g(x))+2^{2(n-1)},h(x)=1\end{array}$,递归求即可.

代码II

const int MAXN = 205;  // 两倍空间
const int MOD = 1e9 + 7;
char x[MAXN];
int len;
int pow2[MAXN];

void init() {
  pow2[0] = 1;
  for (int i = 1; i < MAXN; i++) pow2[i] = (ll)pow2[i - 1] * 2 % MOD;
}

int f(int pos) {
  if (pos == len - 1) return x[pos] == '1';
  else if (x[pos] == '0') return (ll)f(pos + 1) * 2 % MOD;
  else return ((ll)f(pos + 1) * 2 % MOD + pow2[2 * (len - pos - 1)]) % MOD;
}

void solve() {
  init();

  cin >> x;
  len = strlen(x);

  cout << f(0);  // 从最高位开始计算
}

int main() {
  solve();
}

322B. Ciel and Flowers

原题指路:https://codeforces.com/problemset/problem/322/B

题意

有红、绿、蓝三种花各$r$、$g$、$b(0\le r,g,b\le 1\mathrm{e}9)$种,用于制作如下四种花束:①红花束,需$3$朵红花;②绿花束,需$3$朵绿花;③蓝花束,需$3$朵蓝花;④混合花束,需红、绿、蓝三种花各$1$朵.问最多能制作多少花束.

思路I

常见错误 a n s = ⌊ r 3 ⌋ + ⌊ g 3 ⌋ + ⌊ b 3 ⌋ + min ⁡ { r   m o d   3 , g   m o d   3 , b   m o d   3 } ans=\left\lfloor\dfrac{r}{3}\right\rfloor+\left\lfloor\dfrac{g}{3}\right\rfloor+\left\lfloor\dfrac{b}{3}\right\rfloor+\min\{r\ \mathrm{mod}\ 3,g\ \mathrm{mod}\ 3,b\ \mathrm{mod}\ 3\} ans=⌊3r​⌋+⌊3g​⌋+⌊3b​⌋+min{r mod 3,g mod 3,b mod 3},hack数据$r=2,g=2,b=3$.

分析知只有$r,g,b$(无序)模$3$的余数分别为$0,2,2$且余数为$0$的花不少于$3$朵时答案会$+1$,特判即可.

代码I

void solve() {
  vi a(3);
  for (auto& ai : a) cin >> ai;

  sort(all(a), [&](const int& A, const int& B) {
    return A % 3 < B % 3;
  });

  int ans = a[0] / 3 + a[1] / 3 + a[2] / 3 + min({ a[0] % 3, a[1] % 3, a[2] % 3 });
  if (a[0] >= 3 && a[0] % 3 == 0 && a[1] % 3 == 2 && a[2] % 3 == 2) ans++;
  cout << ans;
}

int main() {
  solve();
}

思路II

存在最优策略,其中包含的混合花束$<3$.

[证] 若有$3$个混合花束,则将其拆解为红花束、绿花束、蓝花束各$1$个,答案不会变差.

枚举制作$0,1,2$个混合花束,求答案的最大值.

代码II

void solve() {
  int r, g, b; cin >> r >> g >> b;

  int ans = r / 3 + g / 3 + b / 3 + min({ r % 3,g % 3,b % 3 });  // 0个混合花束
  if (r >= 1 && g >= 1 && b >= 1)  // 1个混合花束
    ans = max(ans, (r - 1) / 3 + (g - 1) / 3 + (b - 1) / 3 + min({ (r + 2) % 3, (g + 2) % 3, (b + 2) % 3 }) + 1);
  if (r >= 2 && g >= 2 && b >= 2)  // 2个混合花束
    ans = max(ans, (r - 2) / 3 + (g - 2) / 3 + (b - 2) / 3 + min({ (r + 1) % 3, (g + 1) % 3, (b + 1) % 3 }) + 2);
  cout << ans;
}

int main() {
  solve();
}

323A. Black-and-White Cube

原题指路:https://codeforces.com/problemset/problem/323/A

题意 $(0.5\mathrm{s})$

给定一个由$k\times k\times k(1\le k\le 100)$个小正方体组成的大正方体.两小正方体视为相邻,如果它们有公共面.现要给每个小正方体的每个面染黑色或白色,使得每个白色的正方体恰有$2$个相邻的白色正方体,每个黑色的正方体恰有$2$个相邻的黑色正方体.若有解,输出任一种方案;否则输出$-1$.

若有解,前$k$行输出一个$k\times k$的由字符’b’和’w’组成的字符矩阵,表示大正方体第一层的染色情况.接下来$k$行同理,表示大则会那个方体第二层的染色情况,以此类推.

思路

①$k$为奇数时,手模样例知无解.

②$k$为偶数时,每层的构造如下图所示,同时保证上层与下层异色即可.

代码

void solve() {
  int n; cin >> n;

  if (n & 1) {
    cout << -1;
    return;
  }

  vector<vi> a(n + 1, vi(n + 1));
  for (int c = 1; c <= n; c++) {  // c的奇偶性代表颜色
    for (int i = c; i <= n - c + 1; i++) {
      for (int j = c; j <= n - c + 1; j++) {
        if (i == c || i == n - c + 1) a[i][j] = c & 1;
        else if (j == c || j == n - c + 1) a[i][j] = c & 1;
        else a[i][j] = (c & 1) ^ 1;
      }
    }
  }

  for (int k = 1; k <= n; k++) {  // 枚举大正方体的每一层
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        cout << (a[i][j] ? 'w' : 'b');
        a[i][j] ^= 1;
      }
      cout << endl;
    }
  }
}

int main() {
  solve();
}

340C. Tourist Problem

原题指路:https://codeforces.com/problemset/problem/340/C

题意

给定一个长度为$n(2\le n\le 1\mathrm{e}5)$的序列$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}7)$.对$a[]$的所有排列$a_{p_1},\cdots ,a_{p_n}$,求所有的$|a_{p_1}-0|+\sum _{i=2}^n|a_{p_i}-a_{p_{i-1}}|$之和的平均值,输出既约分数的分子和分母.

思路

①对$|a_{p_1}-0|$,固定每个$a_i$作为第一个数,其余$(n-1)$个数任排,它对答案的贡献为$\sum _{i=1}^n{a}_i(n-1)!$.

②对$\sum _{i=2}^n|a_{p_i}-a_{p_{i-1}}|$,枚举每个相邻的$(i,j)$,它可排在排列的$(n-1)$个位置上,其余$(n-2)$个数任排, 它对答案的贡献为$\sum _{i=1}^n\sum _{j=1}^n|a_i-a_j|\cdot (n-1)\cdot (n-2)!=\sum _{i=1}^n\sum _{j=1}^n|a_i-a_j|\cdot (n-1)!$.

故$ans=\frac{\left(\sum _{i=1}^n\sum _{j=1}^n|a_i-a_j|+\sum _{i=1}^n{a}_i\right)\cdot (n-1)!}{n!}=\frac{\sum _{i=1}^n\sum _{j=1}^n|a_i-a_j|+\sum _{i=1}^n{a}_i}{n}$.

暴力求时间复杂度$O(n^2)$,会TLE.考虑优化,先将$a[]$升序排列,则$\sum _{i=1}^n\sum _{j=1}^n|a_i-a_j|=2\sum _{i=1}^n\sum _{j=1}^{i-1}(a_i-a_j)=2\sum _{i=1}^n(i-1)a_i-\sum _{j=1}^{i-1}{a}_j$,在计算的过程中维护$a[]$的前缀和$pre$即可将计算答案的时间复杂度优化道$O(n)$.

代码

void solve() {
  int n; cin >> n;
  vi a(n + 1);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ans += a[i];
  }

  sort(a.begin() + 1, a.end());

  ll pre = 0;  // a[]的前缀和
  for (int i = 1; i <= n; i++) {
    ans += ((ll)(i - 1) * a[i] - pre) * 2;
    pre += a[i];
  }

  ll g = gcd(ans, n);
  cout << ans / g << ' ' << n / g;
}

int main() {
  solve();
}

364A. Matrix

原题指路:https://codeforces.com/problemset/problem/364/A

题意

给定一个只包含数码的字符串$s$,定义$b_{ij}=s_i\cdot s_j$,在矩阵$B=(b_{ij})$中求满足矩形中的元素之和等于$a$的矩形的个数.

第一行输入一个整数$a(0\le a\le 1\mathrm{e}9)$.第二行输入一个长度不超过$4000$的只包含数码的字符串$s$.

思路

$ans=\sum _{i=1}^n\sum _{j=1}^n\sum _{k=i}^n\sum _{l=j}^n\left[\sum _{p=i}^k\sum _{q=j}^l{s}_p\cdot s_q=a\right]=\sum _{i=1}^n\sum _{j=1}^n\sum _{k=i}^n\sum _{l=j}^n\left[\left(\sum _{p=i}^k{s}_p\right)\left(\sum _{q=j}^l{s}_q\right)=a\right]$.

维护$s[]$的前缀和$pre[]$,预处理出所有$\sum _{i=1}^n\sum _{j=i}^n(pre[j]-pre[i-1])$,存在哈希表$mp[]$中,

​ 则$ans=\sum _{i=1}^n\sum _{j=i}^n[pre[j]-pre[i-1]\ne 0]\cdot [(pre[j]-pre[i-1])\mid a]\cdot mp\left[\frac{a}{pre[j]-pre[i-1]}\right]$.

注意特判$a=0$的特殊i情况.

代码

const int MAXN = 4005;
int a;
char s[MAXN];
int pre[MAXN];  // s[]的前缀和
umap<int, int> mp;

void solve() {
  cin >> a >> s + 1;

  int n = strlen(s + 1);
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + s[i] - '0';

  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) mp[pre[j] - pre[i - 1]]++;

  if (!a) cout << (ll)mp[0] * n * (n + 1) - (ll)mp[0] * mp[0];
  else {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int tmp = pre[j] - pre[i - 1];
        if (tmp && a % tmp == 0) ans += mp[a / tmp];
      }
    }
    cout << ans;
  }
}

int main() {
  solve();
}

374B. Inna and Nine

原题指路:https://codeforces.com/problemset/problem/374/B

题意

给定一个长度不超过$1\mathrm{e}5$的只包含数码的字符串$s$.现有操作:取两相邻的数码使得它们之和为$9$,将这两个数码合并为一个数码$9$.问经若干次操作后包含最多个数码$9$的数的个数.数据保证答案不超过ll.

思路

定义一个$block$是一个区间,其中任意两相邻数之和都为$9$.

①对长度为偶数的$block$,如$3636$,若合并中间两个数码,则会导致结果少一个数码$9$,显然这不是最优的.

​ 故长度为偶数的$block$只有一种情况.

②对长度为奇数的$block$,最优策略操作后剩下一个单独的数码,则合并该$block$的方案数为$\lceil \frac{len}{2}\rceil$,其中$len$为区间长度.

代码

const int MAXN = 1e5 + 5;
char s[MAXN];
int block[MAXN], idx;  // 每个block的长度、当前block的编号

void solve() {
  cin >> s + 1;

  int n = strlen(s + 1);
  bool ok = false;  // 记录当前是否在block中
  for (int i = 2; i <= n; i++) {
    if (s[i] - '0' + s[i - 1] - '0' == 9) {
      if (!ok) {
        ok = true;
        block[++idx] = 1;
      }
      block[idx]++;
    }
    else ok = false;
  }

  ll ans = 1;
  for (int i = 1; i <= idx; i++)
    if (block[i] & 1) ans *= (block[i] + 1) / 2;
  cout << ans;
}

int main() {
  solve();
}

414B. Mashmokh and ACM

原题指路:https://codeforces.com/problemset/problem/414/B

题意

称一个整数序列$a_1,\cdots ,a_n$是好的,如果$a_i\mid a_{i+1}(1\le i\le n-1)$.给定整数$n,k(1\le n,k\le 2000)$,求长度为$k$的、元素范围为$[1,n]$的好的整数序列的个数,答案对$1\mathrm{e}9+7$取模.

思路

$dp[i][j]$表示长度为$i$的、以$j$结尾的好的序列的个数.枚举$j$的约数$d$,状态转移方程$dp[i][j]=\sum _{d\mid x}dp[i-1][d]$.初始条件可取$dp[0][1]=1$.

暴力转移时间复杂度$O(kn\sqrt{n})$,会TLE.考虑优化,先预处理出$2000$内所有数的约数,总时间复杂度$O(kn\log n)$.

代码

const int MAXN = 2005;
const int MOD = 1e9 + 7;
vi divisors[MAXN];  // 存每个数的约数
int dp[MAXN][MAXN];  // dp[i][j]表示长度为i的、以j结尾的好的序列的个数

void init() {
	for (int i = 1; i < MAXN; i++)
		for (int j = i; j < MAXN; j += i) divisors[j].push_back(i);
}

void solve() {
	init();

	int n, k; cin >> n >> k;
	
	dp[0][1] = 1;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (auto d : divisors[j])
				dp[i][j] = ((ll)dp[i][j] + dp[i - 1][d]) % MOD;
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) ans = ((ll)ans + dp[k][i]) % MOD;
	cout << ans;
}

int main() {
	solve();
}

459B. Pashmak and Flowers

原题指路:https://codeforces.com/problemset/problem/459/B

题意

给定一个长度为$n(2\le n\le 2\mathrm{e}5)$的序列$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}9)$.从中选出两个元素,使得最大元素与最小元素之差$diff$最大,且选出的数中最大元素的出现次数不超过$1$,输出$diff$和方案数.若选出的两个元素相等,则视其中一个为最大元素,另一个为最小元素,进而该方案也视为合法方案.

思路

①若序列的所有元素都相等,则$ans=C_n^2$.

②若序列存在不相等的元素,设序列的最大元素、最小元素出现次数分别为$cn{t}_1,cn{t}_2$,则$ans=cn{t}_1\cdot cn{t}_2$.

代码

void solve() {
  int n; cin >> n;
  vi a(n);
  int maxnum = -INF, minnum = INF;
  for (auto& ai : a) {
    cin >> ai;
    maxnum = max(maxnum, ai), minnum = min(minnum, ai);
  }

  cout << maxnum - minnum << ' ';
  cout << (maxnum - minnum ? (ll)count(all(a), maxnum) * count(all(a), minnum) : (ll)n * (n - 1) / 2);
}

int main() {
  solve();
}

476B. Dreamoon and WiFi

原题指路:https://codeforces.com/problemset/problem/476/B

题意

某人在数轴上移动,初始时在原点.给定一个只包含字符’+‘和’-‘的字符串$s_1$,其中’+‘表示向右移动一个单位,’-‘表示向左移动一个单位.给定一个与$s_1$等长的、只包含字符’+‘、’-‘和’?‘的字符串$s_2$,其中’?‘等概率地取’+‘或’-'.分别进行操作$s_1$和操作$s_2$,求最后停在同一位置的概率,误差不超过$1\mathrm{e}-9$.

第一行输入一个只包含字符’+‘和’-‘的字符串$s_1$.第二行输入一个与$s_1$等长的、只包含字符’+‘、’-‘和’?'的字符串$s_2$.数据保证两字符串的长度都不超过$10$.

思路I

显然操作$s_1$后停在的位置$target$可求得.

显然$s_2$中’?‘的位置不影响概率,可先求出只操作$s_2$中确定的字符后停在的位置$last$,并统计$s_2$中’?'的个数$unknown$.

考察两终点的距离(相差的$+1$数)$dis=target-last$.

①$dis$与$unknown$奇偶性不同或$unknown<abs(dis)$时无解,概率为$0$.

②设从$last$走到$target$所需的步数为$need$,则$need-(unknown-need)=|dis|$,解得$need=\lfloor \frac{unknown+|dis|}{2}\rfloor$.

​ $ans=\frac{C_{unknown}^{need}}{2^{unknown}}$.

代码I

void solve() {
	string s1, s2; cin >> s1 >> s2;

	int target = 0;  // s1序列的终点
	for (int i = 0; i < s1.length(); i++)
		target += s1[i] == '+' ? 1 : -1;

	int last = 0;  // s2已知序列的终点
	int unknown = 0;  // s2中的?数
	for (int i = 0; i < s2.length(); i++) {
		if (s2[i] == '?') unknown++;
		else last += s2[i] == '+' ? 1 : -1;
	}
	
	int dis = target - last;  // 两终点相差的+1数
	if ((dis + unknown & 1) || unknown < abs(dis)) {
		cout << 0;
		return;
	}

	int need = unknown + abs(dis) >> 1;  // 到达终点所需的步数
	int ans = 1;
	for (int i = 0; i < need; i++) ans *= unknown - i;
	for (int i = 2; i <= need; i++) ans /= i;
	cout << fixed << setprecision(18) << (double)ans / (1 << unknown);
}

int main() {
	solve();
}

思路II

因’?‘的个数至多有$10$个,可枚举每个’?'取何值.

思路III

$dp[i][j]$表示走到第$i$个问号时坐标为$j$的概率.

状态转移方程$dp[i][j]=dp[i-1][j-1]\ast 0.5+dp[i-1][j+1]\ast 0.5$.

因坐标可能为负,第二维加一个$BASE=10$的偏移值即可.

代码III

const int MAXN = 25;  // 两倍空间
const int BASE = 10;  // 偏移量
string s1, s2;
double dp[MAXN][MAXN];  // dp[i][j]表示走到第i个问号时坐标为j的概率

void solve() {
	cin >> s1 >> s2;
	
	int pos1 = 0, pos2 = 0, cnt = 0;
	for (int i = 0; i < s1.length(); i++) {
		pos1 += s1[i] == '+' ? 1 : -1;

		if (s2[i] == '?') cnt++;
		else pos2 += s2[i] == '+' ? 1 : -1;
	}

	dp[0][pos2 + BASE] = 1;
	for (int i = 1; i <= cnt; i++) {
		for (int j = -10; j <= 10; j++)  // 枚举下标
			dp[i][j + BASE] = dp[i - 1][j - 1 + BASE] * 0.5 + dp[i - 1][j + 1 + BASE] * 0.5;
	}
	cout << fixed << setprecision(18) << dp[cnt][pos1 + BASE];
}

int main() {
	solve();
}