Mex Partition#11808

Mex Partition (Omówienie)

Problem Author:	wuhudsm
Prepared by:	wuhudsm
Editorial:	wuhudsm

Let $d p [i] [j] [v]$ dp[i][j][v] represent the number of ways to arrange the first $i$ numbers into $j$ segments with a mex value of $v$ . We have:

d p [i] [j] [v] = x = 1 \sum i d p [i - x] [j - 1] [v] \times f (x, v)

dp[i][j][v] = \sum_{x=1}^{i} dp[i - x][j - 1][v] \times f(x, v)

Here, $f (x, v)$ f(x, v) is the number of different ways to arrange an array of length $x$ with a mex value of $v$ . To compute $f (x, v)$ f(x, v), we can use the inclusion-exclusion principle:

f (x, v) = i = 0 \sum v (- 1)^{i} \times C (v, i) \times (m - i)^{x}

f(x, v) = \sum_{i=0}^{v} (-1)^i \times C(v, i) \times (m - i)^x

An important observation is that the length of a subsegment with a mex value of $v$ should be at least $v$ . So only the state where $v \times j \leq n$ v \times j \leq n is legal. In other words, we only need to compute $O (n^{2} lo g n)$ O(n^2 \log n) $d p [i] [j] [v]$ dp[i][j][v] states. The total complexity is $O (n^{3} lo g n)$ O(n^3 \log n).

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int M=401;
const int LOGN=28;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T;
ll n,m,R;
ll f[M][M];
ll dp[M][M][M];

/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */


//-------------------------------------------------
//涉及变量:fac[],inv[],TMD,N(上界)
//注意:TMD自取

ll fac[N],inv[N];

ll pw(ll x,ll p)
{
	if(!p) return 1;
	ll y=pw(x,p>>1);
	y=(y*y)%TMD;
	if(p&1) y=(y*(x%TMD))%TMD;	//典中典:若底数太大要对底数取模!
	return y;
}

void init_C()
{
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
	inv[N-1]=pw(fac[N-1],TMD-2);
 	for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%TMD;
}

ll C(int n,int m)
{
	if(n<m||n<0||m<0) return 0;	//特殊情况
	return fac[n]*inv[m]%TMD*inv[n-m]%TMD;
}

ll A(int n,int m)
{
	if(n<m||n<0||m<0) return 0;	//特殊情况
	return fac[n]*inv[n-m]%TMD;
}

ll INV(ll x)
{
    return pw(x,TMD-2);
}

//-------------------------------------------------

void init_f()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(j>m+1) continue;
            for(int k=0;k<=j;k++)
            {
                ll sig=((k&1)?-1:1);
                if(j<=m) f[i][j]=(f[i][j]+sig*C(j,k)*pw(m-k,i)%TMD+TMD)%TMD;
                else f[i][j]=(f[i][j]+sig*C(j,k)*pw(m+1-k,i)%TMD+TMD)%TMD;
                //
                //if(i==2&&j==2) printf("k=%d f[2][2]=%I64d",k,f[2][2]);
                //
            }
        }
    }
}

void init()
{
    cin>>n>>m>>R;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                dp[i][j][k]=0;
    init_f();
}

void solve()
{
    //dp[1][1][0]=m-1;
    //dp[1][1][1]=1;
    //
    //printf("f[2][0]=%I64d f[2][1]=%I64d f[2][2]=%I64d\n",f[2][0],f[2][1],f[2][2]);
    //
    for(int i=0;i<=n;i++) dp[0][0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k*j<=i;k++)
            {
                for(int l=1;l<=i;l++)
                {
                    dp[i][j][k]=(dp[i][j][k]+dp[i-l][j-1][k]*f[l][k])%TMD;
                }
            }
        }
    }
    for(int i=1;i<=R;i++)
    {
        ll ans=0;
        for(int k=0;k<=n;k++)
            ans=(ans+dp[n][i][k])%TMD;
        cout<<ans<<(i==R?'\n':' ');
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    fastio;

    init_C();
	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

C++