freee Programming Contest 2023（AtCoder Beginner Contest 310）

A - Order Something Else（模拟）

题意：两种方式购买饮料，一种是直接购买，一种是使用优惠券购买，使用优惠券购买，但是必须买一个小菜。

思路：模拟。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
void solve() {int n, p, q;cin >> n >> p >> q;int mn = 0x3f3f3f3f;for (int i = 0; i < n; i++) {int x;cin >> x;mn = min(mn, x);}cout << min(p, q + mn) << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;// cin >> T;while (T--) {solve();}return 0;
}

B - Strictly Superior（模拟）

题意：有n个产品，第i个产品价格为pi，有ci个功能，问是否有严格更优的产品。定义严格更优的产品优以下特征：

• $P_i⩾P_j$
• 第j个含有第i个所有功能
• 第j个价格严格更少，或者功能严格更多。

思路：模拟。

代码：

int mark[105][105];
int p[105], c[105];
void solve() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> p[i] >> c[i];for (int j = 0; j < c[i]; j++) {int x;cin >> x;mark[i][x] = 1;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j || p[i] < p[j]) continue;int flag = 1;for (int k = 0; k <= m; k++) {if (mark[i][k] > mark[j][k]) {flag = 0;break;}}if (!flag) continue;if (p[i] > p[j] || c[j] > c[i]) {cout << "Yes\n";return;}}}cout << "No\n";
}

C - Reversible（模拟）

题意：完全相同和恰好相反的字符串是相同的，求出这里所有不同的字符串。

思路：正向和方向取字典序最小放入集合中即可。

拓展：如果是要求循环同构条件下本质不同的字符串，可以使用最小表示法，或者后缀数组来实现求出字典序最小的位置，放入集合中即可，均可以实现线性复杂度找到最小字典序位置。

代码：

void solve() {int n;cin >> n;set<string> st;for (int i = 0; i < n; i++) {string s;cin >> s;string t = s;reverse(s.begin(), s.end());st.insert(min(s, t));}cout << st.size() << '\n';
}

D - Peaceful Teams(DFS+状压)

题意：有n个队员，但是其中m对不和睦的关系，现在要想划分成t个队伍，求出所有合法的不同的划分。

思路：暴力，这里的n最大为10，划分成t组，朴素暴力的时间复杂度是$O(n^t)$ 1e10数量级，无法承受。利用状态压缩，用一个数来代表一个小队，然后判断当前人是加入已有小队还是另外创建小队分类dfs，这样时间复杂度降到$O(n!)$ 10！只有3,628,800。

理念：考虑划分可能有些困难，可以用动态规划的思想，就是考虑前i个的时候有哪些划分，例如，只有一个人的时候，就只能自成一队，当前i个人组成了dp[i]种划分时，此时再加入一个人，他可以选择加入现有的队，或者自成一队，这两者是互斥的。

注意：一定要预先分配内存块(reserve)，否则，递归的时候，扩容的话可能会转移vector，导致上一个递归内存帧的迭代器失效。

代码：

int mask[15];
vector<int> teams;
//dfs遍历所有可能的划分情况
//now是单调递增的，根据动态规划的思想，考虑加入现有队伍或者自成一队的情况
//对于前面i种所有本质不同的划分，插入一个新的now，对于不同划分之间仍然保持本质不同。
//对于同一划分，不同插入位置也本质不同，因此这样是完备的。
int dfs(int now) {if (now == n + 1) {return teams.size() == t;}int ans = 0;for (int& team : teams) {//auto&！if (!(team & mask[now])) {team |= 1 << now;ans += dfs(now + 1);team ^= 1 << now;}}if (teams.size() < t) {teams.push_back(1 << now);ans += dfs(now + 1);teams.pop_back();}return ans;
}
void solve() {cin >> n >> t >> m;teams.reserve(t);for (int i = 0; i < m; i++) {int x, y;cin >> x >> y;mask[y] |= 1 << x;//都是拿大的去找小的}cout << dfs(1) << '\n';
}

E - NAND repeatedly(普通dp)

题意：给出一个01序列，求所有的非合取连续子段和。

思路：dp即可，dp表示所有以i结尾的非零后缀数，如果这位是0，那么，此处的贡献是i-1（注意这个运算，0的话任意后缀均可，除了单个零）；如果是1，此处是1(独立一个数，最小的后缀)+(i-1) - dp(i-1)（表示以i-1为结尾所有为0的后缀，全部后缀减去非零后缀）。
$$d{p}_i=\{\begin{array}{c}1+i-1-d{p}_{i-1}{s}_i为1\\ i-1s_i为0\end{array}$$

void solve() {int n;cin >> n;string s;cin >> s;int last = 0, cnt = 0;long long ans = 0;for (auto x : s) {if (x == '0') {ans += cnt;last = cnt;} else {last = 1 + cnt - last;ans += last;}cnt++;}cout << ans << '\n';
}

拓展：如果是求一个序列所有的连续子段异或和，这些数是int范围内，那么我们可以拆成32位，统计各位的贡献次数。普通异或的情况下。最后加权求和即可。
$$d{p}_i=\{\begin{array}{c}1+i-1-d{p}_{i-1}{s}_i为1\\ d{p}_{i-1}{s}_i为0\end{array}$$

F - Make 10 Again（状态压缩+概率dp）

题意：给定N个骰子，每个骰子有Ai个面，问同时抛出这些骰子有多大的概率得到10

前言：如何设计状态？不同的概率对应有情况的不同划分，把诸多的骰子组合完整地划分成若干情况，使得这些情况的概率方便计算，方便推演是我们的目标。当然，我们可以将最后N个骰子的情况，简单地划分成两种情况，这些骰子能组成10的和这些骰子不能组成10的，但是这样划分太过粗糙，每种情况都有诸多的子情况，比较难以计算，不方便递推，尽管这样同样是合法的——这两种情况互不包含，并且涵盖了所有的情况。这里，我们可以把最后骰子的情况，划分成这些骰子能够组成的所有数的集合，这样有一个优异的性能，我们可以通过先前的集合和当前骰子的情况，推算该骰子所能转移到的所有能够抵达的状态，如果我们不选择这个集合，我们可以有原先的集合S都可以取到， 有 1 A i 概率 , T = { x ∈ S ∣ x + j ( j ∈ [ 1 , A i ] ] ) } 有\frac{1}{A_i}概率,T=\{x\in S\;|\;x+j(j\in[1,A_i]])\} 有Ai​1​概率,T={x∈S∣x+j(j∈[1,Ai​]])}，那么当前概率下可以抵达的状态便是$S\cup T$，对于当前骰子等概率的各种情况，我们都能转移到前i+1个骰子的各种状态，更进一步，我们可以不考虑大于10的部分，我们于是将原先所有的情况，按照能够组成0~10这11个数的情况划分成2^11类型，这些类型完全涵盖了所有骰子状态，并且这些情况不会互相重叠。当我们考虑玩当前所有集合，所有骰子的情况，我们就能完整且不遗漏地得到得到当前所有骰子的所有状态的概率

思路：$dp[N][mask]$表示，考虑前N个骰子的情况，够组合成这个mask集合的概率。

边界
d p [ 0 ] [ S ] = { 0 i f S ≠ { 0 } 1 i f S = { 0 } dp[0][S]=\left\{ \begin{array}{l} 0\quad if\;S\neq \{0\}\\ 1\quad if\;S=\{0\}\\ \end{array} \right. dp[0][S]={0ifS={0}1ifS={0}​

转移
∀ i , S , j ∈ [ 1 , A i ] , d p [ i ] [ S ] → d p [ i + 1 ] [ S ∪ T ] 其中 T = { x ∈ S ∣ x + j ( j ∈ [ 1 , A i ] ] ) } \forall i,S, j\in{[1,A_i]},dp[i][S]\rightarrow dp[i+1][S\cup T]其中T=\{x\in S\;|\;x+j(j\in[1,A_i]])\} ∀i,S,j∈[1,Ai​],dp[i][S]→dp[i+1][S∪T]其中T={x∈S∣x+j(j∈[1,Ai​]])}

答案
$$\sum _{10\in S}dp[N][S]$$
时间复杂度
$$O(10N{2}^{11})$$
约4e6

ll po(ll rad, ll idx) {ll res = 1;while (idx) {if (idx & 1) res = res * rad % mod;idx >>= 1;rad = rad * rad % mod; }return res;
}int mask = (1 << 11) - 1;
ll f[105][1 << 11];void solve() {f[0][1] = 1;int n;cin >> n;for (int i = 1; i <= n; i++) {int x;cin >> x;ll inv = po(x, mod - 2);for (int j = 1; j <= min(x, 10); j++) {for (int k = 0; k <= mask; k++) {int u = (k | (k << j)) & mask;f[i][u] = (f[i][u] + f[i - 1][k] * inv % mod) % mod;}}if (x > 10) {//取并了等于没有取，统一处理for (int k = 0; k <= mask; k++) {f[i][k] = (f[i][k] + f[i - 1][k] * inv % mod * (x - 10) % mod) % mod;}}}ll ans = 0;for (int i = 0; i <= mask; i++) {if (i & (1 << 10)) {ans = (ans + f[n][i]) % mod;}}cout << ans << '\n';
}

G - Takahashi And Pass-The-Ball Game(倍增/内向基环树)

题意：这里有$N$个高桥君（这是Atcoder的社长），第$i$个高桥君一个整数$A_i$和$B_i$个球。给定一个$K$，等概率地选择$x,x\in [1,K]$，之后他们互相传球，第$i$个高桥君，把球传给第$A_i$个高桥君，注意，他们是同时传球的，传$x$次。求出每个高桥君手里的球的数量的期望。

思路：这里是倍增的方法。等概率$[1,K]$，我们最后答案是${\sum }_{i=1}^K\frac{1}{K}f(i)$，$f(x)$表示$x$次时，某个高桥君在手上的球的数目的。求期望，我们首先，可以求出$1$到$K$的时候，各个高桥君手里球的数目，然后除以$K$即可。

如何计算呢？

上图是传三次球的情况，我们最终的答案是后三排的和数组，因为不能传零次。如果是偶数排，我们可以把两排并作一排，我们可以传一次球累加得到绿色的第一排和第二排的和，也就是右侧蓝色的第一排，显然我们不能同样地算出蓝色第二排，因为$K$非常大，我们要用快速幂的思想，蓝色第二排，也就是绿色第三排，绿色第四排的和，注意看，绿色第三排的球来自绿色第一排传两次的球，绿色第四排的球来自绿色第二排传两次的球，如果我们把绿色第一排和绿色第二排作为一个整体，那么相当于，这个整体连传两次球到绿色第三排和绿色第四排的整体，我们对传球关系进行迭代运算，可以得到右侧蓝色两排传直球的关系，经过这样的操作，总排数便减少了一半。传球有平行关系！

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;ll po(ll rad, ll idx) {ll res = 1;rad %= mod;//炸long long!!!while (idx) {if (idx & 1) res = res * rad % mod;idx >>= 1;rad = rad * rad % mod; }return res;
}void solve() {int n;ll k;cin >> n >> k;vector<ll> A(n), B(n);vector<ll> ans(n);for (int i = 0; i < n; i++) {cin >> A[i];A[i]--;}for (int i = 0; i < n; i++) {cin >> B[i];ans[i] = mod - B[i];//减去第一排}ll inv = po(k, mod - 2);k++;//k+1排while (k) {if (k & 1) {//取走一排for (int i = 0; i < n; i++) {ans[i] = (ans[i] + B[i]) % mod;}//传一次球vector<ll> tmp(n);for (int i = 0; i < n; i++) {tmp[A[i]] = (tmp[A[i]] + B[i]) % mod;}B = tmp;}//两排并一排vector<ll> tmp(n);//传一次球for (int i = 0; i < n; i++) {tmp[A[i]] = (tmp[A[i]] + B[i]) % mod;}for (int i = 0; i < n; i++) {B[i] = (B[i] + tmp[i]) % mod;}//关系迭代vector<ll> AA(n);for (int i = 0; i < n; i++) {AA[i] = A[A[i]];} A = AA;k >>= 1;}for (int i = 0; i < n; i++) {cout << ans[i] * inv % mod << " \n"[i == n - 1];}
}