QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786370#9650. 链覆盖369Pai0 0ms0kbC++233.8kb2024-11-26 21:15:242024-11-26 21:15:24

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 21:15:24]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-26 21:15:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Barrett 
{
	ull b, m;
	Barrett(const ull& b = 2): b(b), m((__uint128_t(1) << 64) / b) {}
	inline ull operator() (const ll& x) const 
	{
		ull r = (__uint128_t(x + b) * m) >> 64;
		ull q = (x + b) - b * r;
		return q >= b ? q - b : q;
	}
} Mod;
const int N = 305;
int n , mod , cof[N][N][N] , f[N][N][N] , g[N][N][N] , ans[N][N];
int Qpow(ll x , ll p)
{
	ll res = 1;
	for(; p ; p >>= 1 , x = x * x % mod) 
		if(p & 1)res = res * x % mod;
	return res;
}
int fac[N] , ifac[N] , inv[N];
void Init(int n)
{
	fac[0] = ifac[0] = inv[0] = inv[1] = 1;
	for(int i = 1 ; i <= n ; i++)
		fac[i] = (ll)fac[i - 1] * i % mod;
	ifac[n] = Qpow(fac[n] , mod - 2);
	for(int i = n - 1 ; i >= 1 ; i--)
		ifac[i] = (ll)ifac[i + 1] * (i + 1) % mod;
	for(int i = 2 ; i <= n ; i++)
		inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
}
int C(int n , int m)
{
	if(n < m || m < 0)return 0;
	return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> mod; 
	Init(n) , Mod = Barrett(mod);
	for(int j = 0 ; j <= n ; j++)
		cof[0][0][j] = 1;
	cof[1][0][0] = 1;
	auto add = [&](auto &x , const auto &y){x = Mod(x + y);};
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 0 ; j <= i ; j++)
		{
			for(int k = 0 ; k <= n - i - j ; k++)
			{
				if(j)add(cof[i][j][k] , cof[i - 1][j - 1][k + 1] * (ll)j);
				add(cof[i][j][k] , cof[i - 1][j][k] * (ll)k);
				// cerr << "cof(" << i << ',' << j << ',' << k << ") = " << cof[i][j][k] << "\n";
			}
		}
	}
	f[n][0][0] = f[n][1][1] = 1;
	for(int i = n ; i > 1 ; i--)
	{
		for(int j = 0 ; i * j <= n ; j++)
		{
			for(int k = j ; k <= n - (i - 1) * j ; k++)
			{
				int v = f[i][j][k];
				if(!v)continue ;
				// cerr << i << ',' << j << ',' << k << ":" << f[i][j][k] << "\n";
				for(int t = j ; t <= n - k && t * (i - 1) <= n ; t++)
				{
					// cerr << "\t f(" << i - 1 << ',' << t << "," << k + t << ") <-- " 
					// 	<< v << " * " << cof[t][j][k - j] << " * " << ifac[t] << "\n";
					add(f[i - 1][t][k + t] , (ll)v * cof[t][j][k - j] % mod * ifac[t]);
				}
			}
		}
	}
	for(int j = 1 ; j <= n ; j++)
		g[1][j][n] = 1;
	for(int i = 2 ; i <= n ; i++)
	{
		for(int j = 0 ; i * j <= n ; j++)
		{
			for(int k = j ; k <= n - (i - 1) * j ; k++)
			{
				for(int t = j ; t <= n - k && t * (i - 1) <= n ; t++)
					add(g[i][j][k] , (ll)g[i - 1][t][k + t] * cof[t][j][k - j] % mod * ifac[t]);
			}
		}
	}
	for(int i = n ; i > 1 ; i--)
	{
		for(int j = 0 ; i * j <= n ; j++)
		{
			for(int k = j ; k <= n - (i - 1) * j ; k++)
			{
				int v = f[i][j][k] , sum = 0;
				if(!v)continue ;
				for(int p = (n - k) / (i - 1) ; p >= max(1 , j) ; p--)
				{
					add(ans[p][k + (i - 1) * p] , (ll)v * sum);
					add(sum , Mod((ll)cof[p][j][k - j] * ifac[p]) * g[i - 1][p][k + p]);
				}
				// for(int t = j ; t <= n - k && t * (i - 1) <= n ; t++)
				// {
				// 	for(int p = max(j , 1) ; p <= min(t , n) - 1 ; p++)
				// 	{
				// 		int m = k + (i - 1) * p;
				// 		// cerr << i << ',' << j << ',' << k << ',' << t << " " << p << ',' << m << ":" << v 
				// 		// 	<< " * " << (ll)cof[t][j][k - j] * ifac[t] % mod << " * " << g[i - 1][t][k + t] << "\n";
				// 		add(ans[p][m] , (ll)v * cof[t][j][k - j] % mod * ifac[t] % mod * g[i - 1][t][k + t]);
				// 	}
				// }
			}
		}
	}
	for(int i = 1 ; i <= n ; i++)
	{
		ans[i][n] = Qpow(n , n - 2);
		// for(int j = 1 ; j <= n ; j++)
		// 	cerr << ans[i][j] << " \n"[j == n];
		for(int j = i ; j < n ; j++)
		{
			ans[i][j] = (ll)ans[i][j] * fac[n] % mod * inv[n] % mod;
			ans[i][n] = (ans[i][n] - ans[i][j] + mod) % mod;
		}
		for(int j = 1 ; j <= n ; j++)
			cout << ans[i][j] << " \n"[j == n];
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1 1033582741

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #8:

0%

Subtask #10:

score: 0
Skipped

Dependency #9:

0%