QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786370 | #9650. 链覆盖 | 369Pai | 0 | 0ms | 0kb | C++23 | 3.8kb | 2024-11-26 21:15:24 | 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%