CF

Problem - 2266D - Codeforces

1400 思维好题

观察发现，元素往前移动一格，该元素大小-1，下标-1。

所以可以发现元素大小和下标关系：

b[i]=a[i]-i

这个值不管怎么移动都不会变，然后要找任意次移动之后相同的一段，就是找 b数组的连续的自然数的一段，然后可以任意移动排列，所以直接排序去重，找最长长度就可以了

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5+10;void solve()
{int n;cin >> n;vector a(n), b(n);for (int i = 0; i < n;i++){cin >> a[i];b[i] = a[i] - i;}sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());int cnt = 1, ans = 1;for (int i = 1; i < b.size();i++){if(b[i-1]==b[i]-1){cnt++;}else{cnt = 1;}ans = max(ans, cnt);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

Problem - 2255B - Codeforces

1600 组合数 可以发现操作之后，0和1的段数不会变，比如000111001100011011，0这里一定是4部分，1是4部分，移动之后改变的是每一部分的数量，所以用隔板法求可能的情况

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 1e6+10;
LL f[N], inv[N];void init(int n){f[0] = f[1] = inv[0] = inv[1] = 1;for (int i = 2; i <= n; i++){f[i] = f[i - 1] * i % mod;inv[i] = mod - (mod / i) * inv[mod % i] % mod;}for (int i = 1; i <= n; i++){inv[i] = inv[i - 1] * inv[i] % mod;}
}LL C(int n,int m){return f[n] * inv[m] % mod * inv[n - m] % mod;
}void solve()
{int n;cin >> n;string s;cin >> s;int c0 = 0, c1 = 0;int d0 = 0, d1 = 0;for (int i = 0; i < s.size();i++){if(s[i]=='0'){c0++;}else{c1++;}if (i == 0 || s[i - 1] != s[i]){if(s[i]=='0'){d0++;}else{d1++;}}}LL ans = 1;if(c0)ans = ans * C(c0 - 1, d0 - 1) % mod;if(c1)ans = ans * C(c1 - 1, d1 - 1) % mod;cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init(1000000);int T;cin >> T;while (T--){solve();}
}

Problem - 2244F - Codeforces

1700 DFS 从底向上判断，判断是否只有一段不连续（因为是环形）

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5+10;
vector e[N];
int a[N], mn[N], mx[N];
bool flag;void dfs(int u){if(e[u].empty()){mn[u] = mx[u] = a[u];return;}mn[u] = 1e9;mx[u] = 0;for(auto v:e[u]){dfs(v);mn[u] = min(mn[u], mn[v]);mx[u] = max(mx[u], mx[v]);}int cnt = 0, pre = e[u].back();for(auto v:e[u]){if(mx[pre]+1!=mn[v]){cnt++;}pre = v;}if(cnt!=1){flag = 0;}
}void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){e[i].clear();}for (int i = 2; i <= n; i++){int fa;cin >> fa;e[fa].push_back(i);}for (int i = 1; i <= n;i++){cin >> a[i];}flag = 1;dfs(1);if(flag){cout << "YES\n";}else{cout << "NO\n";}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

左儿子右兄弟 - Problem - QOJ.ac

求子树和，还有满足方案个数

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5+10;
vector e[N];
int fa[N], sz[N];void dfs(int u){sz[u] = 1;for(auto v:e[u]){dfs(v);sz[u] += sz[v];}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 2; i <= n;i++){int fa;cin >> fa;e[fa].push_back(i);}dfs(1);LL ans = n, totcnt = 1;for (int u = 1; u <= n;u++){vector a;for(auto v:e[u]){a.push_back(sz[v]);}sort(a.begin(), a.end());LL sum = 0;for (int i = 0; i < a.size();i++){sum += a[i];ans += sum;}int cnt = 0;for (int i = 0; i < a.size();i++){if(i>0&&a[i]==a[i-1]){cnt++;}else{cnt = 1;}totcnt = totcnt * cnt % mod;}}cout << ans << endl;cout << totcnt << endl;
}

复习（准备女生赛）

10.26｜基础数论、质数、组合数学

基础数论

  • 组合数
  • 数学函数与公式总结

质数与因数

  • CF264B
  • CF1061C
  • 线性筛好题复盘

（晚上） 矩阵快速幂

  • 矩阵快速幂模板补充
  • dp+矩阵快速幂

组合数学与计数

  • [[2026-05-07#Problem - 768C - Codeforces|计数好题 1]]
  • [[2026-05-13#Problem - 375B - Codeforces|计数好题 2]]
  • 计数好题（计数排序） [[2026-09-22#Problem - 914C - Codeforces|好题]]

其他数学

  • 进制转换
  • 置换环

组合数好题

Problem - 553A - Codeforces

题意 ：在取出第 i+1 种颜色最后一颗球之前，已经取出了第 i 种颜色的最后一颗球。 所以对于到第 \(i\) 种颜色，固定一个第 \(i\) 种颜色球，剩下的随意放前面，所以插空放就可以了，这里是一个空能放好几个球的情况，就是先放球，再按照之前的的排序放进其他球

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 1010;
LL C[N][N], cnt[N];void init(){for (int i = 0; i <= 1000; ++i){C[i][0] = 1;for (int j = 1; j <= i; ++j){C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}C[i][i + 1] = 0;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init();int n;cin >> n;for (int i = 1; i <= n;i++){cin >> cnt[i];}LL ans = 1, sum = 0;for (int i = 1; i <= n;i++){sum += cnt[i];ans = (ans * C[sum - 1][cnt[i] - 1]) % mod;}cout << ans << endl;
}

质因数好题

Problem - 264B - Codeforces

1500 最长子序列 优化：只枚举输入 \(x\) 的质因子，找质因子对应的最长dp，然后更新 \(x\) 的所有质因子

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 1e5+10;
int dp[N], ans;void solve(int x){vector f;for (int i = 2; i <= x / i;i++){if(x%i==0){f.push_back(i);}while(x%i==0){x /= i;}}if(x>1){f.push_back(x);}int mx = 0;for(auto p:f){mx = max(mx, dp[p]);}for(auto p:f){dp[p] = mx + 1;}ans = max(ans, mx + 1);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){int x;cin >> x;solve(x);}cout << ans << endl;
}

Problem - 1061C - Codeforces

计数dp

对每一个输入的元素 \(x\) ，先记录它所有的因数（1e6以内的数，因数最多也就 240 个），然后dp[j]=dp[j]+dp[j-1]，就是 \(x\) 放或不放它的因子 \(j\) 的位置

dp[j] 表示长度为 \(j\) 的方案的个数

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 1e6+10;
LL dp[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;dp[0] = 1;for (int i = 1; i <= n;i++){int x;cin >> x;vector d;for (int j = 1; j <= x / j;j++){if(x%j==0){d.push_back(j);if(j*j!=x){d.push_back(x / j);}}}sort(d.rbegin(), d.rend());for(auto j:d){if(j>i)continue;dp[j] = (dp[j] + dp[j - 1]) % mod;}}LL ans = 0;for (int i = 1; i <= n;i++){ans = (ans + dp[i]) % mod;}cout << ans << endl;
}

线性筛好题

Problem - 546D - Codeforces

数学，线性筛求因子数 加一个f数组，求每个数质因数总个数

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 5e6 + 10;
bool st[N];
int prime[N];
int cnt;
LL f[N], ans[N];void get_prime(int n)
{st[1] = true;for (int i = 2; i <= n;i++){if(!st[i]){prime[cnt++] = i;f[i] = 1;}for (int j = 0; prime[j] <= n / i;j++){st[prime[j] * i] = true;f[prime[j] * i] = f[i] + 1;if(i%prime[j]==0)break;}}
}void solve()
{int a, b;cin >> a >> b;cout << ans[a] - ans[b] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;get_prime(5000000);for (int i = 1; i <= 5000000;i++){ans[i] = ans[i - 1] + f[i];}while (T--){solve();}
}

矩阵快速幂

Problem - 222E - Codeforces (基础题)

建立字母之间的可行性矩阵

然后通过矩阵快速幂，求出A.c[i][j] 即从字符 \(i\) 到 \(j\) 走 \(n-1\) 步的方案数

时间复杂度：\(O(m^3\log n)\)

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 60;
LL len,n, k;struct matrix{LL c[N][N];matrix(){memset(c, 0, sizeof c);}
};matrix operator*(const matrix &x, const matrix &y){matrix t;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 1; k <= n; k++){t.c[i][j] =(t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;}}}return t;
}matrix matpow(matrix A,LL k){matrix res;for (int i = 1; i <= n; i++){res.c[i][i] = 1;}while (k){if (k & 1){res = res * A;}A = A * A;k >>= 1;}return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> len >> n >> k;matrix A;for (int i = 1; i <= n;i++){for (int j = 1; j <= n;j++){A.c[i][j] = 1;}}for (int i = 0; i < k;i++){string s;cin >> s;int x = (islower(s[0]) ? s[0] - 'a' + 1 : s[0] - 'A' + 27);int y = (islower(s[1]) ? s[1] - 'a' + 1 : s[1] - 'A' + 27);A.c[x][y] = 0;}matrix res = matpow(A, len - 1);LL ans = 0;for (int i = 1; i <= n;i++){for (int j = 1; j <= n;j++){ans = (ans + res.c[i][j]) % mod;}}cout << ans << endl;
}

Problem - 852B - Codeforces

难点在思考怎么构造转移矩阵

矩阵 A[i][j] 记录的是：经过一层后，费用余数从 \(i\) 变成 \(j\) 的方案数。

用快速幂加速 \(L-2\) 个相同中间层的转移，最后合并首层和末层并取余数 0 的方案数。

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 105;
const int M = 1e6 + 10;
LL a[N], b[N], c[N], dp[N];
int B[M];
int n, m;
LL l;struct matrix{LL c[N][N];matrix(){memset(c, 0, sizeof c);}
};matrix operator*(const matrix &x, const matrix &y){matrix t;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 1; k <= n; k++){t.c[i][j] =(t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;}}}return t;
}matrix matpow(matrix A,LL k){matrix res;for (int i = 1; i <= n; i++){res.c[i][i] = 1;}while (k){if (k & 1){res = res * A;}A = A * A;k >>= 1;}return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> m >> l >> n;for (int i = 1; i <= m;i++){int x;cin >> x;a[x % n]++;}for (int i = 1; i <= m;i++){cin >> B[i];B[i] %= n;b[B[i]]++;//计数}for (int i = 1; i <= m;i++){int x;cin >> x;c[(B[i] + x) % n]++;}matrix A;for (int i = 0; i < n;i++){//枚举余数for (int j = 0; j < n;j++){A.c[i + 1][j + 1] = b[(j - i + n) % n];}}matrix res = matpow(A, l - 2);//注意，以 1 为下标for (int i = 0; i < n;i++){for (int j = 0; j < n;j++){dp[j] = (dp[j] + a[i] * res.c[i+1][j+1]) % mod;}}LL ans = 0;for (int i = 0; i < n;i++){ans = (ans + dp[i] * c[(n - i) % n]) % mod;}cout << ans << endl;
}

Problem - 1970E2 - Codeforces

矩阵快速幂优化dp好题！！！

定义矩阵 \(A\)：$$A= \begin{bmatrix} A_{1,1}&A_{1,2}&\cdots&A_{1,m}\ A_{2,1}&A_{2,2}&\cdots&A_{2,m}\ \vdots&\vdots&\ddots&\vdots\ A_{m,1}&A_{m,2}&\cdots&A_{m,m} \end{bmatrix}$$​​​

其中：\(A_{i,j}\)

表示：一天内从小屋 \(i\) 到小屋 \(j\) 的路线方案数。

\[A_{i,j}​=s_i​s_j​+s_i​l_j​+l_i​s_j \]

矩阵 \(A\) 存储“一天从任意小屋到任意小屋的方案数”，矩阵相乘负责把多天的路线拼接起来，因此走 \(n\) 天的所有方案就由 \(A^n\) 表示。​

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 1e9 + 7;
const int N = 105;
int n;
LL k;
LL s[N], l[N];struct matrix{LL c[N][N];matrix(){memset(c, 0, sizeof c);}
};matrix operator*(const matrix &x, const matrix &y){matrix t;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 1; k <= n; k++){t.c[i][j] =(t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;}}}return t;
}matrix matpow(matrix A,LL k){matrix res;for (int i = 1; i <= n; i++){res.c[i][i] = 1;}while (k){if (k & 1){res = res * A;}A = A * A;k >>= 1;}return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k;for (int i = 1; i <= n;i++){cin >> s[i];}for (int i = 1; i <= n;i++){cin >> l[i];}matrix A;for (int i = 1; i <= n;i++){for (int j = 1; j <= n;j++){A.c[i][j] = (s[i] * s[j] % mod + s[i] * l[j] % mod + l[i] * s[j] % mod) % mod;}}matrix res = matpow(A, k);LL ans = 0;for (int i = 1; i <= n;i++){ans = (ans + res.c[1][i]) % mod;}cout << ans << endl;
}

置换环

E - Minimum Swap

置换环，对于整个序列，分成几个环，只要分别对几个环排序就可以了 最终有序的状态 \((1, 2, 3, \dots, N)\)，其实就是 \(N\) 个长度为 1 的自环。

\[1\to1, \quad 2\to2, \quad 3\to3, \dots \]

也就是说，我们的目标是让环的数量越多越好（最后要有 \(N\) 个环）。 有一个数学定理（最小交换次数公式）：

\[\text{最小交换次数} = N - \text{当前的环数} \]

  • 起点：假设现在有 \(C\) 个环，我们需要操作 \(N-C\) 次。
  • 终点：我们要有 \(N\) 个环，需要操作 \(N-N=0\) 次。
    这意味着：为了保证“次数最少”，我们所做的每一次交换，必须让“环的数量”加 1。
    即对环内数字交换，环数一定增加
#include 
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=3e5+10;
int p[N];
bool vis[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> p[i];}LL ans = 0;for (int i = 1; i <= n;i++){if(vis[i])continue;int cur = i;int sz = 0;while(vis[cur]==0){vis[cur] = 1;sz++;cur = p[cur];}ans += 1LL * (sz - 1) * sz/2;}cout << ans << endl;
}

计数

Problem - 768C - Codeforces

计数排序

看数据范围，发现每个数字不超过2000，所以最大为1023（111111111）

通过这个优化时间复杂度 \(O(k\times M)\)

#include 
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define PII pair
const LL mod = 998244353;
const int N = 2e5 + 10, M = 1 << 10;
int a[2][M];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k, m;cin >> n >> k >> m;for (int i = 0; i < n;i++){int x;cin >> x;a[0][x]++;}while(k--){for (int i = 0; i < M;i++){a[1][i] = 0;}int t = 0;for (int i = 0; i < M; i++){int x = a[0][i] / 2, y = a[0][i] / 2;if (a[0][i] & 1){if(t==0)x++;elsey++;t ^= 1;}a[1][i ^ m] += x;a[1][i] += y;}for (int i = 0; i < M;i++){a[0][i] = a[1][i];}}int l = 0, r = 1023;while(a[0][l]==0)l++;while(a[0][r]==0)r--;cout << r << " " << l << endl;
}