B. Shortest path
Title Description
Given a rootless tree with \ (n \) nodes, the edge weight of each edge is \ (1 \)
There are \ (m \) key points different from each other on the tree. Randomly select \ (k \) points and mark them. Ask any starting point and ending point what is the expected length of the shortest path passing through all marked points.
\(2\leq k\leq m\leq n\leq 2000,m\leq300\)
solution
Consider that if you need to go back to the starting point, the shortest path length is the number of sides \ (\ times2 \) of the virtual tree. If you don't need to go back to the starting point, subtract the diameter of the virtual tree. Therefore, the problem can be transformed into the expectation of the number of virtual tree edges and the expectation of virtual tree diameter.
The expectation of finding the number of edges of the virtual tree can consider the contribution of each edge. We can calculate the scheme in which this edge appears in the virtual tree by subtracting the scheme in which all marked points only appear on one side of the subtree from the total scheme, and the combination number can be calculated casually.
The expectation of finding the diameter of the virtual tree can directly enumerate the diameter \ ((u,v) \), and then count the scheme of the corresponding tree. If we want to ensure that the length is the longest and the dictionary order is the smallest, it can not be counted as heavy. Then we enumerate a point \ (x \), and the following conditions do not exist, which represents legal:
- \(d (U, V) < D (x, V) \), or \ (d (U, V) = D (x, V), x < u \)
- \(d (U, V) < D (U, x) \), or \ (d (U, V) = D (U, x), x < V \)
This can be understood in combination with the neighborhood theory on the tree, that is, after adding a point, it is necessary and sufficient to consider whether there will be a more optimized diameter. The point pair complexity of our implementation is right, and the time complexity \ (O(m^3) \)
summary
The minimum set of expected problems should be split. To achieve excellent complexity, there is likely to be a known strategy to reach the minimum.
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
const int M = 2005;
const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,ans,a[M],d[M][M],siz[M],C[M][M];
vector<int> g[M];
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
void init()
{
for(int i=0;i<=m;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}
}
void dfs(int u,int fa,int rt)
{
for(auto v:g[u])
{
if(v==fa) continue;
d[rt][v]=d[rt][u]+1;
dfs(v,u,rt);
}
}
void cal(int u,int fa)
{
for(auto v:g[u])
{
if(v==fa) continue;
cal(v,u);
siz[u]+=siz[v];
}
if(u!=1)//the contribution of edge(u,fa)
{
int f=(C[m][k]-C[siz[u]][k]-C[m-siz[u]][k])%MOD;
ans=(ans+f+MOD)%MOD;
}
}
signed main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();m=read();k=read();init();
for(int i=1;i<=m;i++) a[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
//initialize for all distance
for(int i=1;i<=n;i++) dfs(i,0,i);
//first part:edge of trees
for(int i=1;i<=m;i++) siz[a[i]]=1;
cal(1,0);ans=2*ans%MOD;
int tmp=0;
//second part:DD(XYX) of trees
for(int x=1;x<=m;x++)
for(int y=x+1;y<=m;y++)
{
int cnt=0,i=a[x],j=a[y];
for(int z=1;z<=m;z++) if(z!=x && z!=y)
{
int k=a[z];
if(d[i][k]>d[i][j] || d[j][k]>d[i][j])
continue;
if(d[i][k]==d[i][j] && z<y) continue;
if(d[j][k]==d[i][j] && z<x) continue;
cnt++;
}
tmp+=C[cnt][k-2];
ans=(ans-d[i][j]*C[cnt][k-2]%MOD+MOD)%MOD;
}
ans=ans*qkpow(C[m][k],MOD-2)%MOD;
printf("%lld\n",ans);
}
C. Cactus
Title Description
Give a cactus with \ (n \) points and \ (m \) edges, and find the determinant of its adjacency matrix:
\(n\leq 10^5,n-1\leq m\leq 2\cdot 10^5\)
solution
To map the meaning of the determinant to the graph, we can consider the contribution of each permutation \ (p \).
First, consider the tree. Because \ (p_i \) are different from each other and there are edges between \ ((i,p_i) \), only the \ ((u,v) \) in the original graph satisfies \ (p_u u = V, p_v = u \), that is, directly cover these two points with edges. For convenience, we regard it as a special ring.
The ring can also cover the points on the ring. At this time, we consider which edge the ring root chooses, corresponding to these two different cases. Let the number of rings be \ (c \), and the coefficient of contribution we consider is \ ((- 1)^{n-c} \)
The ring corresponds to the permutation decomposition of the original arrangement, because an exchange operation will change the parity of the reverse order pair, and it can become an arrangement of \ (i=p_i \) through \ (n-c \) operations, so \ (inv(p)=n-c\bmod 2 \)
Then go directly to \ (dp \) on the round square tree. For the ring, first consider the overall selection, then consider breaking an edge to cover the edge, and finally consider the influence of this edge. Time complexity \ (O(n) \)
summary
For mathematical problems with special background, we should think about the combinatorial significance of formulas. The relationship between ring, arrangement and reverse order is also very interesting!
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 100005;
const int MOD = 993244853;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,Ind,s[M],a[M],low[M],dfn[M],dp[M][2];
vector<int> g[M];
void add(int &x,int y) {x=(x+y)%MOD;}
int sub(int x,int y) {return ((x-y)%MOD+MOD)%MOD;}
void dfs(int u,int fa)
{
s[++k]=u;low[u]=dfn[u]=++Ind;
dp[u][0]=0;dp[u][1]=1;
for(auto v:g[u])
{
if(v^fa && dfn[v]) low[u]=min(low[u],dfn[v]);
if(dfn[v]) continue;
//then v is not vistied
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]<dfn[u]) continue;
//then u is the root
int len=1;a[len]=u;
do a[++len]=s[k];
while(s[k--]^v);
reverse(a+2,a+len+1);//attention the order
if(len==2)//just a edge,particularly consider
{
dp[u][0]=sub(dp[u][0]*dp[v][0],dp[u][1]*dp[v][1]);
dp[u][1]=dp[u][1]*dp[v][0]%MOD;
continue;
}
int nw[2]={MOD-2,0};
for(int i=1;i<=len;i++)//choose the whole circle
nw[0]=nw[0]*dp[a[i]][1]%MOD;
int f[2][2]={},g[2][2]={};
f[0][0]=sub(dp[u][0]*dp[a[2]][0],dp[u][1]*dp[a[2]][1]);
f[0][1]=dp[u][0]*dp[a[2]][1]%MOD;
f[1][0]=dp[u][1]*dp[a[2]][0]%MOD;
f[1][1]=dp[u][1]*dp[a[2]][1]%MOD;
for(int i=3;i<=len;i++)
{
swap(f,g);
for(int s=0;s<2;s++)
{
f[s][0]=f[s][1]=0;
add(f[s][1],g[s][0]*dp[a[i]][1]);
add(f[s][0],g[s][0]*dp[a[i]][0]);
add(f[s][0],MOD-g[s][1]*dp[a[i]][1]%MOD);
}
}
add(nw[1],f[1][0]);
add(nw[0],sub(f[0][0],f[1][1]));
dp[u][0]=nw[0];dp[u][1]=nw[1];
}
}
signed main()
{
freopen("cactus.in","r",stdin);
freopen("cactus.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
if(n&1) dp[1][0]=MOD-dp[1][0];
printf("%lld\n",dp[1][0]%MOD);
}
D. Black and white chess
Title Description
Click here to see the question
solution
What bothers me most about this problem is that the game may not end, because it may do meaningless actions back and forth first and then.
We try to discuss this situation. If \ (A \) goes to the left and is currently in the must fail state, then \ (B \) can go to the left to maintain this must fail state. At this time, the range of \ (A \) can be reduced. If the current state is A must win state, then \ (A \) will not go to the left at all.
For a more rigorous explanation, we remember a \ (k/2 \) tuple: \ ((b_1-a_1-1,b_2-a_2-1...) \), which can be transformed into an image. Everyone can operate up to \ (m \) piles from \ (k/2 \) stones, and each pile can be completed at most, at least one.
This is a \ (\ tt nim-k \) problem. The current state must fail. If and only if all \ (d_i \) are converted to binary, the number of each bit \ (1 \) \ (\ bmod (m+1)=0 \)
Proof (in fact, the idea is similar to the proof \ (\ tt sg \) function):
1. The situation of all \ (0 \) must be a failure.
2. For any must lose state, you can only reach the must win state. Because the number of operations \ (m \) can change at most \ (m \) per binary bit, the subsequent state \ (\ bmod (m+1)\not=0 \)
3. For any must win state, there is a must lose state. It can be considered from high to low. Assuming that the \ (k \) heap has been changed after making the previous bits legal, this \ (k \) heap can take \ (0 / 1 \), and set \ (sum \) to the number of remaining heaps \ (1 \) \ (\ bmod (m+1)=0 \)
- If \ (sum\leq m-k \), directly operate these heaps, get \ (1 \), and set the previously operated heap as \ (0 \)
- If \ (sum > m-k \), it is legal to select \ (m+1-sum \) from the \ (K \) heap and set it to \ (1 \) and others to \ (0 \).
Now consider how to count, directly plan according to the binary bit, record how many grids of the original sequence are used, and then count the number of schemes at the starting point. Specifically, let \ (f(i,j) \) be the number of schemes considering \ (i \) binary bits, using the number of cells \ (j \) and the number of each bit \ (1 \) \ (\ bmod(m+1)=0 \). During transfer, the binary bits of \ (1 \) need to be allocated to \ (k/2 \) distances.
Time complexity \ (t (n) = \ sum {I = 0} ^ {\ log _2n} \ frac {NK} {2 ^ I} = O (NK) \)
summary
For this "false draw" game problem, we can think about whether we can keep the original state unchanged. Similar problems include ladder game.
In addition, the \ (\ tt sg-k \) problem can be raised, that is, a game problem that can operate multiple sub problems at a single time. At this time, modifying the definition of \ (xor \) can generalize the meaning of the number of \ (1 \) per bit \ (\ bmod(m+1) \).
#include <cstdio>
const int MOD = 1e9+7;
const int M = 10005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,m,ans,fac[M],inv[M],dp[M];
void init()
{
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
}
int C(int n,int m)
{
if(n<0 || n<m) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
void add(int &x,int y) {x=(x+y)%MOD;}
void sub(int &x,int y) {x=((x-y)%MOD+MOD)%MOD;}
signed main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
n=read();k=read();m=read();init();
dp[0]=1;ans=C(n,k);n-=k;k/=2;
for(int w=0;w<14;w++)
for(int i=n;i>0;i--)
for(int j=m+1;(1<<w)*j<=i && j<=k;j+=m+1)
add(dp[i],dp[i-(1<<w)*j]*C(k,j));
for(int i=0;i<=n;i++)
sub(ans,dp[i]*C(n-i+k,k));
printf("%lld\n",ans);
}