AtCoder Beginner Contest 327 G. Many Good Tuple Problems (counting of labeled bipartite pictures + placing differentiated balls into differentiated boxes)

Title

An original sequence x with length n (n<=30), x[i] can take the value 0 or 1

A sequence of point pairs (s,t) with length m (m<=1e9),

The i-th item of s sequence and the i-th item of t $(s_{i},t_{i})$ , can take the value [1,n],

If s and t are constructed, for any $(s_{i},t_{i})$ There is a 01 sequence x such that $x_{s_{i}}\ eq x_{t_{i}}$ ,

Then this sequence is said to be legal, ask $n^{2*m}$ How many legal sequences are there in the (s,t) sequence?

The answer is modulo 998244353

Source of ideas

Official solution

https://www.cnblogs.com/chasedeath/p/14567667.html

Solution

Consider a directed graph without self-loops with a total of n points from 1 to n, $C_{n}^{2}$ edge, if (i,j) edge can be used, it means $x[i]\ eq x[j]$

In the end, x will be divided into two piles, a pile of 0 and a pile of 1, which is a bipartite graph.

It is required that a certain labeled edge set solution of the bipartite graph can only be counted once.

It is difficult to count directed graphs. It can be considered as an undirected graph, that is, (1,2) and (2,1) can be regarded as a kind of edge.

Finally, after filling in m positions, decide whether to flip or not, and then multiply by the corresponding $2^m$ Seed selection method

Therefore, what needs to be counted is the number of solutions for labeled bipartite graphs

Counting labeled bipartite graphs

Count $g[i][j]$ represents i The number of bipartite graph solutions with j edges, repetition allowed

$g[i][j]=\sum_{k=1}^{i-1}C_{i}^{k}C_{k*(i-k)}^{j}$

That is to say, k points are selected on the left side of the bipartite graph, i-k points are selected on the right side, and j edges are selected among k*(i-k) edges.

In this case, a bipartite graph with t connected blocks will be counted $2^t$ times,

Because the corresponding connected block parts can be interchanged left and right, they are counted in another legal answer.

So I thought about how to get rid of the weight

Count $h[i][j]$ represents i A bipartite graph that is connected by j edges,

However, the definition of the number of connected blocks in the state is not easy to use for transfer, so subsequent counting considers inclusion and exclusion.

By $g[i][j]$ legal solution,

That is, the size of the connected block where the last point of the enumeration is located,

When did the corresponding connected block and the previous bipartite graph break?

When the size is k, select k-1 points from i-1 points, and then select some edges accordingly

There $h[i][j]=g[i][j]-\sum_{k=1}^{i-1}\sum_{l=0}^{j}C_{i- 1}^{k-1}*h[k][j]*g[i-k][j-l]$

After having the bipartite graph of China Unicom, consider how to merge

As mentioned above, a bipartite graph with t connected blocks will be counted $2^t$ times,

The h scheme is connected, that is, a connected block will be counted twice,

Once on the left and right, so divided by 2 is the actual number of plans

Count $f[i][j]$ represents i A bipartite graph with j edges composed of several connected blocks without repetitions

The transfer still enumerates the size of the connected block where the last point is located,

From the previous f legal scheme, transfer to the new legal scheme via backpack

When the size is k, select k-1 points from i-1 points, and then select some edges accordingly

There is $f[i][j]=\frac{h[i][j]}{2} + \sum_{k=1}^{i-1}\sum_{l=0}^ {j}C_{i-1}^{k-1}*\frac{h[k][l]}{2}*f[i-k][j-l]$

After finding f[i][j], the n points are fixed,

Because f[n-1][j] can be transferred to f[n][j] without using edges

Therefore, you only need to use the state of f[n][j], and there is no need to traverse the values of f[i

When there are j edges, j edges need to be filled in to m positions, and j edges must appear at least once, otherwise the count will be repeated.

Problem with placing the ball in the box

Method 1

This is equivalent to putting m different small balls into j different boxes. Each box cannot be empty.

The second type of Stirling number S(m,j) is the number of options for putting m differentiated balls into j undifferentiated boxes,

So just find the order of multiplying j boxes, which is represented by dp2[i] in the code.

Method 2

Swap the ball and box,

dp[i] means that exactly i kinds of balls are placed in m boxes, and each box can only place one ball.

Then you need to use the full amount and subtract the illegal situations.

There is $dp[i]=i^m-\sum_{j=1}^{i-1}C_{i}^j*dp[j]$

Code

// Problem: G - Many Good Tuple Problems
// Contest: AtCoder - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
// URL: https://atcoder.jp/contests/abc327/tasks/abc327_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc + + .h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b); + + i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d", & amp;(a))
#define scll(a) scanf("%lld", & amp;(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\
",a)
#define ptlle(a) printf("%lld\
",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=31,M=N*N,mod=998244353,inv2=(mod + 1)/2;
int t,n,m,f[N][M],g[N][M],h[N][M],c[M][M],dp[M],dp2[M];
void ADD(int &x,int y){
x=(x + y)%mod;
}
int modpow(int x,int n,int mod){
int res=1;
for(;n;n>>=1,x=1ll*x*x%mod){
if(n & amp;1)res=1ll*res*x%mod;
}
return res;
}
int C(int x,int y){
if(x<0 || y<0 || x<y)return 0;
return c[x][y];
}
voidsol(){
sci(n),sci(m);
c[0][0]=1;
rep(i,1,M-1){
c[i][0]=c[i][i]=1;
rep(j,1,i-1){
c[i][j]=(c[i-1][j] + c[i-1][j-1])%mod;
}
}
rep(i,1,M-1){
dp[i]=modpow(i,m,mod);
rep(j,1,i-1){
ADD(dp[i],mod-1ll*c[i][j]*dp[j]%mod);
}
//printf("i:%d f:%d\
",i,dp[i]);
}
rep(i,1,M-1){
rep(j,1,i){
int sg=((i-j) & amp;1)?-1:1;
ADD(dp2[i],(1ll*sg*C(i,j)%mod*modpow(j,m,mod)%mod)%mod);
}
//printf("i:%d f:%d\
",i,dp2[i]);
}
int ans=0;
rep(i,1,n){
int up=i*(i + 1)/4;
rep(j,0,up){
rep(k,0,i){
ADD(g[i][j],1ll*C(i,k)*C(k*(i-k),j)%mod);
}
h[i][j]=g[i][j];
rep(k,1,i-1){
rep(l,0,j){
ADD(h[i][j],mod-1ll*C(i-1,k-1)*h[k][l]%mod*g[i-k][j-l]%mod);
}
}
f[i][j]=1ll*h[i][j]*inv2%mod;
rep(k,1,i-1){
rep(l,0,j){
ADD(f[i][j],1ll*C(i-1,k-1)*h[k][l]%mod*f[i-k][j-l]%mod*inv2%mod);
}
}
//printf("i:%d j:%d 1:%d 2:%d 3:%d\
",i,j,g[i][j],h[i][j],f[ i][j]);
//printf("i:%d j:%d f:%d\
",i,j,f[i][j]);
//if(i==n & amp; & amp; j<=m)printf("i:%d j:%d f:%d dp:%d add:%d\
",i,j,f[ i][j],dp[j],1ll*f[i][j]*dp[j]%mod);
if(i==n)ADD(ans,1ll*f[i][j]*dp[j]%mod);
}
}
//pte(ans);
ans=1ll*ans*modpow(2,m,mod)%mod;
pte(ans);
}
int main(){
t=1;//sci(t); // t=1
while(t--){
sol();
}
return 0;
}