2023 省选联测41
A. 冤家路窄
找出 \(Deg\) 用总路径数减去相遇的路径数
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2e5 + 55, mod = 1e9 + 7;
int n, m, S, T, head[maxn], tot;
struct edge{int to, net, val;}e[maxn << 1 | 1];
void add(int u, int v, int w){
e[++tot] = {v, head[u], w};
head[u] = tot;
}
void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
ll diss[maxn], dist[maxn]; bool vis[maxn];
priority_queue<pli, vector<pli>, greater<pli>>Q;
vector<int>g1[maxn], g2[maxn];
int f[maxn][2], deg1[maxn], deg2[maxn];
queue<int>q;
int main(){
freopen("avoid.in","r",stdin);
freopen("avoid.out","w",stdout);
n = read(), m = read(); S = read(); T = read();
for(int i = 1; i <= m; ++i) {
int u = read(), v = read(), w = read();
add(u, v, w); add(v, u, w);
}
memset(diss, 0x3f, sizeof(diss));
diss[S] = 0; Q.push(pli(0, S));
while(!Q.empty()){
int x = Q.top().second; Q.pop();
if(vis[x])continue; vis[x] = true;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(diss[v] > diss[x] + e[i].val){
diss[v] = diss[x] + e[i].val;
Q.push(pli(diss[v], v));
}
}
}
memset(dist, 0x3f, sizeof(dist));
memset(vis, 0, sizeof(vis));
dist[T] = 0; Q.push(pli(0, T));
while(!Q.empty()){
int x = Q.top().second; Q.pop();
if(vis[x])continue; vis[x] = true;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(dist[v] > dist[x] + e[i].val){
dist[v] = dist[x] + e[i].val;
Q.push(pli(dist[v], v));
}
}
}
for(int i = 1; i <= tot; i += 2){
int u = e[i].to, v = e[i + 1].to;
if(diss[u] > diss[v])swap(u, v);
if(diss[u] + dist[v] + e[i].val == diss[T]){
g1[u].push_back(v); ++deg1[v];
g2[v].push_back(u); ++deg2[u];
}
}
f[S][0] = 1; q.push(S);
while(!q.empty()){
int x = q.front(); q.pop();
for(int v : g1[x]){
--deg1[v]; if(deg1[v] == 0)q.push(v);
add(f[v][0], f[x][0]);
}
}
f[T][1] = 1; q.push(T);
int ans = 1ll * f[T][0] * f[T][0] % mod;
while(!q.empty()){
int x = q.front(); q.pop();
if(diss[x] == dist[x])add(ans, mod - 1ll * f[x][1] * f[x][0] % mod * f[x][1] % mod * f[x][0] % mod);
for(int v : g2[x]){
--deg2[v]; if(deg2[v] == 0)q.push(v);
if(max(diss[v], dist[x]) < min(diss[x], dist[v]))
add(ans, mod - 1ll * f[x][1] * f[v][0] % mod * f[x][1] % mod * f[v][0] % mod);
add(f[v][1], f[x][1]);
}
}
printf("%d\n",ans);
return 0;
}
B. 夹克姥爷win了win了
结论是 \(k! + k\) 证明用到 \(HAll\) 定理啥的
\(C_{n}^{k} <= P_{n}^{k - 1}\)
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e5 + 55, base = 10000;
struct big{
int a[maxn];
void init(int x){while(x){a[++a[0]] = x % base; x /= base;}}
void mul(int x){
int res = 0, tmp;
for(int i = 1; i <= a[0]; ++i){
tmp = a[i] * x + res;
a[i] = tmp % base;
res = tmp / base;
}
while(res){a[++a[0]] = res % base; res /= base;}
}
void add(int x){
int res = x, now = 0;
while(res){
++now;
a[now] += res;
res = a[now] / base;
a[now] %= base;
}
a[0] = max(a[0], now);
}
void print(){
printf("%d",a[a[0]]);
for(int i = a[0] - 1; i >= 1; --i)printf("%04d",a[i]);
printf("\n");
}
}a;
int main(){
freopen("win.in","r",stdin);
freopen("win.out","w",stdout);
int k; cin >> k;
if(k == 1){
printf("-1\n");
return 0;
}
a.init(1);
for(int i = 2; i <= k; ++i)a.mul(i);
a.add(k);
a.print();
return 0;
}
C. 39与93
\(sort\) 后，每次只需枚举到与 \(b\) 位数相同的部分，复杂度是正确的
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 5e5 + 55, mod = 1e9 + 7;
int n, s, b[maxn], sum;
int mp[13][maxn * 4], tmp[13][maxn * 4];
void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
n = read(), s = read();
for(int i = 1; i <= n; ++i)b[i] = read(), sum ^= b[i];
sort(b + 1, b + n + 1);
mp[0][0] = 1;
for(int l = 1; l <= n; ++l){
int up = 1; while(up <= b[l]) up <<= 1; --up;
for(int i = 0; i < s; ++i){
for(int j = 0; j <= up; ++j)if(mp[i][j])
add(tmp[(i + 1) % s][j xor b[l]], mp[i][j]),
add(tmp[i][j], mp[i][j]);
}
for(int i = 0; i < s; ++i){
for(int j = 0; j <= up; ++j)mp[i][j] = tmp[i][j], tmp[i][j] = 0;
}
}
add(mp[n % s][sum], mod - 1);
printf("%d\n", mp[0][sum]);
return 0;
}
D. Zbox的刷题I
把贡献分开算，变成算期望轮数和操作数
gtm巨佬的题解
https://www.luogu.com.cn/blog/663705/xing-xuan-lian-ce-41-post
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int mod = 998244353, maxn = 2e6 + 55;
int qpow(int x, int y){
int ans = 1;
for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
return ans;
}
int pp[maxn], pq[maxn], f[maxn], fac[maxn], ifac[maxn];
int n, p, q, a, b;
int c(int n, int m){return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;}
int main(){
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
n = read(), p = read(), q = read(), a = read(), b = read();
p = 1ll * p * qpow(q, mod - 2) % mod; q = (mod + 1 - p) % mod;
pp[0] = fac[0] = ifac[0] = 1;
for(int i = 1; i <= n; ++i)pp[i] = 1ll * pp[i - 1] * p % mod;
for(int i = 0; i <= n; ++i)pq[i] = qpow((mod + 1 - pp[i]) % mod, mod - 2);
for(int i = 1; i <= n; ++i)fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = qpow(fac[n], mod - 2);
for(int i = n - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
int ans = 0;
for(int i = 1; i <= n; ++i){
int res = 1ll * c(n, i) * pq[i] % mod;
if(i & 1)ans = (ans + res) % mod;
else ans = (ans - res + mod) % mod;
}
ans = 1ll * ans * b % mod;
ans = (ans + 1ll * a * n % mod * qpow(q, mod - 2) % mod) % mod;
printf("%d\n",ans);
return 0;
}