计数题代码及细节
"我要的并不在这里,你给的答案没意义"
前两篇博客的一些代码可以在这一篇中翻翻
写计数题可能会犯的一些错误
- FWT的值域和长度搞混,FWT数组开小了
- 没开longlong,在循环里int的局部变量
- ans最后没有+P)%P,尤其是容斥QAQ
- 忘记取模,不是少取模,是求某些数组答案时自然而然的忘记,千万不要犯
- inv1,inv0没赋初值
- bitset自己有锅,赋值的时候可能不会全赋值,就是tmp=a&b可能不太对
代码已经删除调试信息
CF451E Devu and Flowers
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
const int P = 1e9 + 7;
const int MAXN = 200;
int n;
ll a[MAXN], m, ans, inv[MAXN], fac[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline ll C(ll n, ll m) {
ll ret = 1;
for(ll i = n - m + 1; i <= n; ++i) {
ret = ret * (i % P) % P;
}
ret = ret * inv[m] % P;
return ret;
}
int main() {
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
int MAXS = (1 << n) - 1;
fac[0] = inv[0] = inv[1] = 1;
for(int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % P;
}
inv[n] = ksm(fac[n], P - 2);
for(int i = n - 1; i >= 2; --i) {
inv[i] = inv[i + 1] * (i + 1) % P;
}
for(ll S = 0, N, SIZ = 0; S <= MAXS; ++S) {
N = m + n - 1;
SIZ = 1;
for(int i = 0; i < n; ++i) {
if(S & (1 << i)) {
N -= a[i + 1] + 1;
SIZ = SIZ * -1;
}
}
if(N < 0)continue;
ans = (ans + C(N, n - 1) * SIZ % P) % P;
ans = (ans + P) % P;
}
printf("%lld\n", ans);
return 0;
}
CF449D Jzzhu and Numbers
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
#define int long long
const int MAXN = 4e6 + 7;
const int P = 1e9 + 7;
ll a[MAXN];
ll ans, n;
inline void FWT(ll *F, int len) {
register int mid, j, k;
for(mid = 1; mid < len; mid <<= 1) {
for(j = 0; j < len; j += (mid << 1)) {
for(k = 0; k < mid; ++k) {
F[j + k] = (F[j + k] + F[j + k + mid] % P) % P;
}
}
}
}
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
signed main() {
scanf("%lld", &n);
int MAXS = 0;
for(int i = 1, x; i <= n; ++i) {
scanf("%lld", &x);
if(MAXS < x)MAXS = x;
a[x]++;
}
int L = 0;
while(MAXS)MAXS >>= 1, ++L;
++L;
MAXS = (1 << L) - 1;
FWT(a, (1 << L));
a[0] = ksm(2, n) - 1;
for(int i = 1; i <= MAXS; ++i) {
a[i] = ksm(2, a[i]) - 1;
}
for(int S = 0, ccnt; S <= MAXS; ++S) {
ccnt = 1;
for(int i = 0; i <= L; ++i) {
if(S & (1 << i))ccnt *= -1;
}
ans = (ans + ( 1ll * a[S] * ccnt % P)) % P;
}
ans = (ans + P) % P;
printf("%lld\n", ans);
return 0;
}
CF1043F Make It One
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
const int MAXN = 1e6 + 7;
const int P = 1e9 + 7;//qwq自己钦定的
ll a[MAXN], g[MAXN], f[MAXN], cnt[MAXN], MAX, n, fac[MAXN], inv[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void init() {
for(int i = 1; i <= MAX; ++i) {
for(int j = i; j <= MAX; j = j + i) {
cnt[i] += a[j];
}
}
fac[0] = inv[0] = inv[1] = 1;
for(int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % P;
}
inv[n] = ksm(fac[n], P - 2);
for(int i = n - 1; i >= 2; i--) {
inv[i] = inv[i + 1] * (i + 1) % P;
}
return ;
}
inline ll C(int n, int m) {
if(n > m)return 0;
return fac[m] * inv[n] % P * inv[m - n] % P;
}
inline void solve(int k) {
for(int i = 1; i <= MAX; ++i) {
g[i] = C(k, cnt[i]);
}
for(int i = MAX; i >= 1; --i) {
f[i] = g[i];
for(int j = i + i; j <= MAX; j += i) {
f[i] = (f[i] - f[j]) % P;
}
f[i] = (f[i] + P) % P;
}
return ;
}
int main() {
scanf("%d", &n);
for(int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
if(x > MAX)MAX = x;
a[x]++;
}
init();
for(int i = 1; i <= 7; ++i) {
solve(i);
if(f[1]) {
printf("%d\n", i);
return 0;
}
}
puts("-1");
return 0;
}
CF839D Winter is here
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 2e6 + 7;
int n, N;
int isp[MAXN], pri[MAXN], mu[MAXN], cnt[MAXN], a[MAXN], tot, f[MAXN], g[MAXN];
inline ll ksm(ll x, ll y) {
ll ans = 1;
if(y < 0)return 0;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void init() {
mu[1] = 1;
for(int i = 2; i <= N; ++i) {
if(!isp[i]) {
pri[++tot] = i;
mu[i] = -1;
}
for(int j = 1; j <= tot && i * pri[j] <= N; ++j) {
isp[pri[j]*i] = 1;
if(i % pri[j] == 0) {
mu[i * pri[j]] = 0;
break;
} else {
mu[i * pri[j]] = -mu[i];
}
}
}
for(int i = 1; i <= N; ++i) {
for(int j = i; j <= N; j += i) {
cnt[i] += a[j];
}
f[i] = 1ll * cnt[i] * ksm(2, cnt[i] - 1) % P;
}
return;
}
inline void solve() {
ll ans = 0;
for(int i = N; i > 1; --i) {
if(f[i] == 0)continue;
g[i] = f[i];
for(int j = i + i; j <= N; j += i) {
g[i] = (g[i] - g[j]) % P;
}
ans = (ans + 1ll * g[i] * i % P) % P;
}
ans = (ans + P) % P;
printf("%lld\n", ans);
}
int main() {
scanf("%d", &n);
for(int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
if(N < x)N = x;
a[x]++;
}
init();
solve();
return 0;
}
CF1097F Alex and a TV Show
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN = 2e5 + 7;
const int N = 7000;
int n, m;
int pri[MAXN], isp[MAXN], tot, miu[MAXN];
bitset<7005> a[MAXN], Val[7002], mu[7002], tmp;
inline void init() {
isp[1] = 1;
miu[1] = 1;
for(int i = 2; i <= N; ++i) {
if(!isp[i]) {
miu[i] = -1;
pri[++tot] = i;
}
for(int j = 1; j <= tot && i * pri[j] <= N; ++j) {
isp[i * pri[j]] = 1;
if(i % pri[j] == 0) {
miu[i * pri[j]] = 0;
continue;
} else {
miu[i * pri[j]] = -miu[i];
}
}
}
for(int i = 1; i <= N; ++i) {
for(int j = i; j <= N; j += i) {
Val[j][i] = 1;
mu[i][j] = miu[j / i] != 0;
}
}
return ;
}
int P = 0, ans[MAXN];
int main() {
scanf("%d%d", &n, &m);
init();
for(int i = 1, typ, x, y, z; i <= m; ++i) {
scanf("%d", &typ);
if(typ == 1) {
scanf("%d%d", &x, &y);
a[x] = Val[y];
} else if(typ == 2) {
scanf("%d%d%d", &x, &y, &z);
a[x] = a[z] ^ a[y];
} else if(typ == 3) {
scanf("%d%d%d", &x, &y, &z);
a[x] = a[z] & a[y];
} else if(typ == 4) {
scanf("%d%d", &x, &y);
printf("%d", (a[x] & mu[y]).count() & 1);//this!
}
}
return 0;
}
CF840E In a Trap
#include<iostream>
#include<cstdio>
#include<cstring>
const int B = 255;
using std::max;
const int MAXN = 2e5 + 7;
int n, m;
int a[MAXN];
int home[MAXN], nxt[MAXN], to[MAXN], ccnt;
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
to[ccnt] = y;
home[x] = ccnt;
}
int dep[MAXN], fa[MAXN];
inline void dfs(int u, int F) {
fa[u] = F;
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(v == F)continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
return ;
}
int ch[MAXN][2], T, f[MAXN][B + 10], gp[MAXN];
int main() {
// freopen("test.in", "r", stdin);
// freopen("test1.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
for(int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
ct(x, y);
ct(y, x);
}
dfs(1, 0);
for(int i = 1, x; i <= n; ++i) {
if(dep[i] >= B) {
x = i;
ch[0][0] = 0;
ch[0][1] = 0;
T = 0;
for(int j = 0; j <= B; ++j, x = fa[x]) {
int t = a[x] ^ j;
int nw = 0;
for(int k = 16; k >= 0; --k) {
int c = (t >> k) & 1;
if(!ch[nw][c]) {
ch[nw][c] = ++T;
ch[T][0] = ch[T][1] = 0;
}
nw = ch[nw][c];
}
}
for(int j = 0; j <= B; ++j) {
int t = j << 8;
int nw = 0, S = 0;
for(int k = 16; k >= 0; --k) {
int c = (t >> k) & 1;
if(ch[nw][c ^ 1]) {
nw = ch[nw][c ^ 1];
S += (1 << k);
} else nw = ch[nw][c];
}
f[i][j] = S;
}
gp[i] = x;
}
}
for(int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
int ans = 0;
int qwq = 0;
int st = dep[y];
while(dep[y] - dep[x] >= B) {
ans = max(f[y][qwq], ans);
++qwq;
y = gp[y];
}
while(y != fa[x]) {
ans = max(ans, a[y] ^ (st - dep[y]));
y = fa[y];
}
printf("%d\n", ans);
}
return 0;
}
再这样高浓度压缩好像博客数就少于zhq了
以后不了