HDU7191 Count Set Problem Solving Report

HDU7191 Count Set Problem Solving Report

topic link

Topic

n n n numbers form a permutation p i ( 1 ≤ i ≤ n ) p_i(1\le i\le n) pi​(1≤i≤n), the calculation base is k k set of k T T the number of T, where T T T needs to satisfy T ∩ P ( T ) = ∅ T\cap P(T)=\varnothing T∩P(T)=∅, where P ( T ) = { p i ∣ i ∈ T } P(T)=\{p_i|i\in T\} P(T)={pi​∣i∈T}.

in

1 ≤ n ≤ 5 × 1 0 5 , ∑ n ≤ 5 × 1 0 6 , 0 ≤ k ≤ n 1\le n\le 5\times 10^5,\sum n\le 5\times 10^6,0\le k\le n 1≤n≤5×105,∑n≤5×106,0≤k≤n

Problem solving ideas

First, such i → p i i\to p_i The relationship of i→pi​ builds a graph, and there must be several large and small rings in the graph, and their sizes are recorded as c 1 , c 2 , ... , c m c_1,c_2,\dots, c_m c1​,c2​,…,cm​. All we have to do is choose the k k k points.

It is easy to find that the different rings are independent. In a ring, to satisfy T ∩ P ( T ) = ∅ T\cap P(T)=\varnothing T∩P(T)=∅, that is, the points selected in a ring cannot be adjacent. This problem is only related to c c c (the size of the ring) is related.

a size of n n pick on the ring of n m m There are m points and they are not adjacent, how to calculate the number of solutions?

Here's a good blog post: Non-adjacent problem by hht2005.

Consider the on-chain situation first. Let's put this non-adjacent first k k Put down k points, and then insert some balls at the front, between every two balls, and at the end, in order: x 0 , x 1 , ... x k x_0,x_1,\dots x_k x0​,x1​,…xk​ total k k k numbers, and:

x 0 + x 1 + ⋯ + x k = n − k x 0 ≥ 0 , x k ≥ 0 , x i ≥ 1 ( 1 ≤ i ≤ k − 1 ) x_0+x_1+\dots+x_k=n-k \\ x_0\ge 0, x_k\ge 0, x_i\ge 1(1\le i\le k-1) x0​+x1​+⋯+xk​=n−kx0​≥0,xk​≥0,xi​≥1(1≤i≤k−1)

become

x 0 + x 1 + ⋯ + x k = n − 2 k + 1 x i ≥ 0 ( 0 ≤ i ≤ k ) x_0+x_1+\dots+x_k=n-2k+1 \\ x_i\ge 0(0\le i\le k) x0​+x1​+⋯+xk​=n−2k+1xi​≥0(0≤i≤k)

It can be seen from the plug-in method that the number of schemes is f ( n , k ) = ( n − 2 k + 1 + k + 1 − 1 k + 1 − 1 ) = ( n − k + 1 k ) f(n,k)=\binom{n-2k+1+k+1-1}{k+1-1}=\binom{n-k+1}{k} f(n,k)=(k+1−1n−2k+1+k+1−1​)=(kn−k+1​)

Then consider the situation on the ring. For a point on the ring, if it chooses, then in the remaining n − 3 n-3 Select from n−3 points k − 1 k-1 k−1, and the number of schemes is f ( n − 3 , m − 1 ) = ( n − k − 1 k − 1 ) f(n-3,m-1)=\binom{n-k-1}{k-1} f(n−3,m−1)=(k−1n−k−1​); if it is not selected, in the remaining n − 1 n-1 Choose from n−1 points k k k, and the number of schemes is f ( n − 1 , k ) = ( n − k k ) f(n-1,k)=\binom{n-k}{k} f(n−1,k)=(kn−k​). The total number of plans is g ( n , k ) = ( n − k − 1 k − 1 ) + ( n − k k ) g(n,k)=\binom{n-k-1}{k-1}+\binom{n-k}{k} g(n,k)=(k−1n−k−1​)+(kn−k​).

Therefore, we can calculate that the size is c c On the ring of c, choose i ( 0 ≤ i ≤ c ) i(0\le i\le c) What is the number of solutions when there are i(0≤i≤c) points.

Now we're going to combine the answers, this m m Take m rings together k k How many k-point solutions are there? It is easy to think of OGF.

The OGF of each ring is

f i ( x ) = ∑ i = 0 c i g ( c i , i ) x i f_i(x)=\sum_{i=0}^{c_i}g(c_i,i)x^i fi​(x)=i=0∑ci​​g(ci​,i)xi

The final answer is

[ x k ] ∏ i = 1 m f i ( x ) [x^k]\prod_{i=1}^mf_i(x) [xk]i=1∏m​fi​(x)

how to put this m m What about multiplying m polynomials? It is easy to find that the total length of these polynomials is c 1 + c 2 + ⋯ + c m = n c_1+c_2+\dots+c_m=n c1​+c2​+⋯+cm​=n, the cost of each merge is O ( l e n log ⁡ l e n ) ≤ O ( l e n log ⁡ n ) O(len\log len)\le O(len\log n) O(lenloglen)≤O(lenlogn) (where l e n = c i + c j len=c_i+c_j len=ci​+cj​), so it can be merged according to the Huffman tree, the total time complexity O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n).

Of course, it is also possible to merge with the same divide-and-conquer structure as the line segment tree, but the time complexity O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n).

/*
 * @Author: rijuyuezhu
 * @Date: 2022-08-02 14:42:15
 * @Description: http://acm.hdu.edu.cn/contest/problem?cid=1048&pid=1007
 * @Tag: Polynomials, Graph Theory, Generating Functions
*/
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), tt == ss) ? EOF : *ss++)
ll read() {
   ll x = 0, f = 1; char ch = getchar();
   for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
   for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
   return x * f;
}
const int MAXN = 5e5 + 5;
const int P = 998244353;
namespace MINT {
	struct mint {
		int v;
		mint(int v = 0) : v(v) {}
	};
	int MOD(int v) {return v >= P ? v - P : v;}
	mint operator + (mint a, mint b) {return MOD(a.v + b.v);}
	mint operator - (mint a, mint b) {return MOD(a.v - b.v + P);}
	mint operator * (mint a, mint b) {return 1ll * a.v * b.v % P;}
	mint qpow(mint a, int n=P-2) {mint ret = 1; for(; n; n >>= 1, a = a * a) if(n & 1) ret = ret * a; return ret;}
	mint operator += (mint& a, mint b) {return a = a + b;}
	mint operator -= (mint& a, mint b) {return a = a - b;}
	mint operator *= (mint& a, mint b) {return a = a * b;}
} using namespace MINT;
namespace Poly {
   const int MAXL = (1 << 19) + 5, Bas = 1 << 19;
	typedef vector<mint> poly;
	mint inv[MAXL], fac[MAXL], ifac[MAXL], _g[MAXL];
	int tr[MAXL];
	void init() {
		inv[1] = 1; for(int i = 2; i < MAXL; i++) inv[i] = (P - P / i) * inv[P % i];
		fac[0] = ifac[0] = 1;
		for(int i = 1; i < MAXL; i++) fac[i] = fac[i-1] * i, ifac[i] = ifac[i-1] * inv[i];
		_g[0] = 1; _g[1] = qpow(3, (P-1) / Bas);
		for(int i = 2; i < Bas; i++) _g[i] = _g[i-1] * _g[1];
	}
	int glim(int n) {
		int lim = 1; for(; lim < n; lim <<= 1);
		return lim;
	}
	void DFT(poly& f, int lim) {
		if((int)f.size() < lim) f.resize(lim);
		for(int i = 0; i < lim; i++) tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
		for(int i = 0; i < lim; i++) if(i < tr[i]) swap(f[i], f[tr[i]]);
		for(int l = 2, k = 1; l <= lim; l <<= 1, k <<= 1) 
			for(int i = 0; i < lim; i += l)
				for(int j = i; j < i+k; j++) {
					mint tt = f[j+k] * _g[Bas / l * (j-i)];
					f[j+k] = f[j] - tt;
					f[j] = f[j] + tt;
				}
	}
	void IDFT(poly& f, int lim) {
		DFT(f, lim); reverse(f.begin()+1, f.begin()+lim);
		for(int i = 1; i < lim; i++) f[i] *= inv[lim];
	}
   poly Mul(poly f, poly g) {
      int n = f.size() + g.size() - 1, lim = glim(n);
      DFT(f, lim), DFT(g, lim);
      for(int i = 0; i < lim; i++) f[i] *= g[i];
      IDFT(f, lim); f.resize(n); return f;
   }
} using namespace Poly;
typedef pair<int, int> pr;
int upto[MAXN], dist[MAXN], n, k, p[MAXN], cnt[MAXN], _cnt;
poly F[MAXN], f, g;
int getup(int x) {
   if(upto[x] == x) return x;
   int f = getup(upto[x]);
   dist[x] += dist[upto[x]];
   return upto[x] = f;
}
mint C(int n, int m) {
   if(n < 0 || m < 0 || n < m) return 0;
   return fac[n] * ifac[m] * ifac[n-m];
}
void work() {
   n = read(), k = read();
   _cnt = 0;
   for(int i = 1; i <= n; i++) p[i] = read(), upto[i] = i, dist[i] = 0;
   for(int i = 1; i <= n; i++) {
      int fx = getup(i), fy = getup(p[i]);
      if(fx == fy) {
         cnt[++_cnt] = dist[i] + dist[p[i]] + 1;
         continue;
      }
      upto[fx] = fy;
      dist[fx] = dist[p[i]] + 1;
   }
   priority_queue<pr, vector<pr>, greater<pr> > pq;
   for(int i = 1; i <= _cnt; i++) {
      int n = cnt[i];
      F[i].resize(n+1);
      for(int j = 0; j <= n; j++)
         F[i][j] = C(n-j, j) + C(n-j-1,j-1);
      pq.push(pr(F[i].size(), i));
   }
   while(pq.size() >= 2) {
      int i = pq.top().second; pq.pop();
      int j = pq.top().second; pq.pop();
      F[i] = Mul(F[i], F[j]); 
      pq.push(pr(F[i].size(), i));
   }
   int t = pq.top().second;
   printf("%d\n", F[t][k].v);
}
int main() {
   init();
   int T = read();
   while(T--) work();
   return 0;
}

Tags: Graph Theory

Posted by Nirvana on Sat, 24 Sep 2022 21:24:21 +0300