CSP-S 模拟赛 37
T1
口胡题。显然尽量靠近中间更优，且选端点一定不劣，于是依据结论将中点设为所有端点的中位数。
代码：
#include <bits/stdc++.h>
#define N 300005
#define int long long
using namespace std;
int n;
int l[N], r[N];
int rk[N << 1];
int pos[N];
int ans;
signed main() {
freopen("case.in", "r", stdin);
freopen("case.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> l[i] >> r[i], rk[i] = l[i], rk[i + n] = r[i];
sort(rk + 1, rk + 1 + (n << 1));
int x = rk[n];
for (int i = 1; i <= n; i++) {
if (l[i] <= x && x <= r[i])
pos[i] = x;
else if(x < l[i])
pos[i] = l[i];
else
pos[i] = r[i];
}
sort(pos + 1, pos + 1 + n);
for (int i = 1; i < n; i++)
ans += (pos[i + 1] - pos[i]) * i * (n - i);
cout << ans << "\n";
return 0;
}
T2
考虑枚举 \(b\) 中 \(1\) 的个数 \(x\)，设第 \(i\) 行 \(1\) 的个数为 \(r\)。
- \(r>x\) 时，选 \(0\) 那么 \(1\) 不够，必须选 \(1\)。
- \(r<x\)，同理必须选 \(0\)。
- \(r=x\)，选 \(0/1\) 随意。
对于方案数的统计，考虑设 \(a_x\) 表示 \(r\le x\) 行中 \(1\) 的并，\(b_i\) 表示 \(r>x\) 行中 \(0\) 的并。那么 \(a,b\) 不能有交集。当 \(r=x\) 时方案数显然是 \(2^{tot}\)，\(tot\) 表示 \(r=x\) 的 \(i\) 的个数，对于 \(r\neq x\)，\(n-a_x-b_x\) 的位置是确定的，\(x-pre_x\) 个 \(1\) 尚未确定，于是乘上 \({{n-a_x-b_x}\choose {x-a_x}}\)。
代码：
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 5005
using namespace std;
int n;
int fac[N], inv[N];
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int C(int n, int m) {
if (n < m || n < 0)
return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
vector<int>ct[N];
bitset<N>a[N], b[N], c[N];
int ans;
signed main() {
freopen("de.in", "r", stdin);
freopen("de.out", "w", stdout);
fac[0] = inv[0] = 1;
for (int i = 1; i < N; i++)
fac[i] = fac[i - 1] * i % mod;
for (int i = 1; i < N; i++)
inv[i] = qpow(fac[i], mod - 2);
cin >> n;
for (int i = 1; i <= n; i++) {
int p = 0;
for (int j = 1, x; j <= n; j++) {
scanf("%1lld", &x);
if (x)
c[i].set(j, 1);
p += x;
}
ct[p].push_back(i);
}
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1];
for (auto j : ct[i])
a[i] |= c[j];
}
for (int i = 1; i <= n; i++)
b[n + 1].set(i, 1);
for (int i = n; i >= 1; i--) {
b[i] = b[i + 1];
for (auto j : ct[i])
b[i] &= c[j];
}
for (int i = 0; i <= n; i++)
if ((a[i] & b[i]) == a[i]) {
int c1 = a[i].count(), c2 = b[i].count();
ans = (ans + qpow(2, ct[i].size()) * C(c2 - c1, i - c1) % mod) % mod;
}
cout << ans << "\n";
return 0;
}
T3
首先显然考虑容斥。
设 \(g(i)\) 表示前 \(i\) 堆所有方案数，\(f(i)\) 表示其异或和为 \(0\) 的方案数。显然 \(g(i)=g(i-1)\times (2^n-i)\)。
对于 \(f(i)\)，也就是前 \(i-1\) 个数的异或和和第 \(i\) 个数相等，初步的想法是 \(f(i)=g(i-1)-f(i-1)\)。但是考虑当前数列中的最后一个数可能在前 \(i-1\) 个数中出现。这个数值显然出自于 \([1,i-2]\)，于是有 \(2^n-1-(i-2)=2^n-i+1\) 种值，除了这个数的排列有 \(f(i-2)\) 种，将这个数插入 \(i-2\) 个数中有 \(i-1\) 种情况，于是 \(f(i)=g(i-1)-f(i-1)-(2^n-i+1)\times(i-1)\times f(i-2)\)。
答案是 \(g(n)-f(n)\)，时间复杂度为 \(O(n)\)。
代码：
#include <bits/stdc++.h>
#define N 10000007
#define int long long
#define mod 1000000007
using namespace std;
int n;
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int f[N], g[N];
signed main() {
freopen("yui.in", "r", stdin);
freopen("yui.out", "w", stdout);
cin >> n;
int n2 = qpow(2, n);
g[0] = 1;
for (int i = 1; i <= n; i++)
g[i] = g[i - 1] * ((n2 - i + mod) % mod) % mod;
f[0] = 1;
f[1] = 0;
for (int i = 2; i <= n; i++)
f[i] = (g[i - 1] - f[i - 1] - ((n2 - i + 1 + mod) % mod) * (i - 1) % mod * f[i - 2] % mod + mod + mod) % mod;
cout << (g[n] - f[n] + mod) % mod << "\n";
return 0;
}
T4
口胡出考虑最优的情况一定是一个团，然后跑 BK 即可。
代码就不放了。
标签：int,37,long,ans,fac,define,CSP,模拟,mod From： https://www.cnblogs.com/Rock-N-Roll/p/18459384