洛谷·[集训队作业2013]城市规划
程序员文章站
2022-03-13 16:49:23
...
初见安~这里是传送门:洛谷P4841 城市规划
题解
这一类的问题好像还是挺常见的——给你n个不同的点,求可组成的无向连通图数。
【我当然知道有两种解法啊,但我只会这一个QAQ】
设表示i个点的无向连通图数和i个点的无向图数。显然,,其中为i个点时的可选边数。
再来,对于我们还可以换一种表示:划分为有点1的集合和没有点1的集合,有点1的集合一定联通,另一个集合则随便,就有:
确认点1拨给f那个集合。
所以两个式子联立一下:
看起来分数线上面的内容比分数线下的多很多啊。所以为了简便我们两边同时除以一下:
现在看起来变量已经比较稳定了呢。我们尝试化卷积,上NTT:令原式变成多项式相乘的形式:
【为什么要把求和符号分开?因为放在生成函数外面就没法求逆元了啊】
所以这个题就求一下多项式G的逆元,再和多项式A相乘,倒转就可以得到数组f的值了。
上代码——
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
//#define int long long
#define maxn 300005
using namespace std;
typedef long long ll;
const int mod = 1004535809, mx = 3e5;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
ll pw(ll a, ll b) {ll res = 1; while(b) {if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
int r[maxn], len, l;
void NTT(ll *c, int flag) {
for(int i = 1; i <= len; i++) if(i < r[i]) swap(c[i], c[r[i]]);
for(int mid = 1; mid < len; mid <<= 1) {
ll gn = pw(3, (mod - 1) / (mid << 1));
if(flag == -1) gn = pw(gn, mod - 2);
for(int ls = 0, L = mid << 1; ls < len; ls += L) {
ll g = 1;
for(int k = 0; k < mid; k++, g = g * gn % mod) {
ll x = c[ls + k], y = g * c[ls + mid + k] % mod;
c[ls + k] = (x + y) % mod, c[ls + mid + k] = (x - y + mod) % mod;
}
}
}
ll rev = pw(len, mod - 2);
if(flag == -1) for(int i = 0; i <= len; i++) c[i] = c[i] * rev % mod;
}
ll f[maxn], g[maxn], fac[maxn], inv[maxn], tmp[maxn], tmpb[maxn];
void get_inv(ll *a, ll *b, int n) {//多项式求逆元,有不同的板子,差别细微但致命
if(n == 1) {b[0] = pw(a[0], mod - 2); return;}
get_inv(a, b, (n + 1) >> 1);
len = 1, l = 0;
while(len <= n + n) len <<= 1, l++;
for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
for(int i = 0; i < n; i++) tmp[i] = a[i];
for(int i = n; i <= len; i++) tmp[i] = 0;
NTT(tmp, 1), NTT(b, 1);
for(int i = 0; i <= len; i++) b[i] = b[i] * (1ll * 2 - tmp[i] * b[i] % mod + mod) % mod;
NTT(b, -1); for(int i = n; i <= len; i++) b[i] = 0;
}
int n;
signed main() {
n = read();
fac[0] = inv[0] = 1;
for(int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % mod;
inv[mx] = pw(fac[mx], mod - 2);
for(int i = mx - 1; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
f[0] = 1;//一定要处理这里
for(int i = 1; i <= n; i++) f[i] = pw(2, 1ll * i * (i - 1) / 2 % (mod - 1)) * inv[i] % mod;
get_inv(f, g, n + 1);
for(int i = 1; i <= n; i++) f[i] = f[i] * i % mod; f[0] = 0;
len = 1, l = 0;
while(len <= n + n) len <<= 1, l++;
for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
NTT(f, 1), NTT(g, 1);
for(int i = 0; i <= len; i++) f[i] = f[i] * g[i] % mod;
NTT(f, -1);
printf("%lld\n", f[n] * fac[n - 1] % mod);//从F到f
return 0;
}
迎评:)
——End——
上一篇: GitHub Pages 绑定域名
推荐阅读
-
洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
-
洛谷P4396 [AHOI2013]作业(树套树)
-
洛谷P4841 城市规划(生成函数 多项式求逆)
-
洛谷P1792 [国家集训队]种树(链表 贪心)
-
BZOJ 4415 洛谷 3988 [Shoi2013]发牌
-
洛谷P4555 [国家集训队]最长双回文串(manacher 线段树)
-
Bzoj 2038 洛谷1494 [2009国家集训队]小Z的袜子(hose) 这辈子都学不会的莫队算法
-
洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB(莫比乌斯反演)
-
洛谷P1501 [国家集训队]Tree II(LCT)
-
洛谷 P1494 [国家集训队] 小Z的袜子