正文

【BZOJ3456】【CDQ分治+FNT】城市规划

IP云
IP云V管理员/2 阅读
11/30
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
试题来源
2013中国国家集训队第二次作业
问题描述
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.
刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通.
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.
好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目.
由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.
输入格式
仅一行一个整数n(<=130000)
输出格式
仅一行一个整数, 为方案数 mod 1004535809.
样例输入
3
样例输出
4
样例输入
4
样例输出
28
样例输入
100000
样例输出
829847355
数据规模和约定
对于 20%的数据, n <= 10
对于 40%的数据, n <= 1000
对于 60%的数据, n <= 30000
对于 80%的数据, n <= 60000
对于 100%的数据, n <= 130000
【分析】
非常巧妙的题目。
首先可以推递推式，用f(n) = 2^C(n,2) - sigma{(2 ^ C(n - i, 2)) * C(n - 1, i - 1) * f(i) |  1<= i <n  }
相当于选定一个点不动，逐步扩大该点所在的联通快的大小。
可以保证不会出现重复。
经过化简将C(n-1,i-1)中的(n-1)!提出来以后，可以通过一种非常巧妙的构造卷积的方式解决问题(详见代码)。
为什么可以用FFT？。。。。FFT怎么取模啊，不会QAQ。 
 /*

 宋代朱敦儒

 《西江月·世事短如春梦》

 世事短如春梦，人情薄似秋云。不须计较苦劳心。万事原来有命。

 幸遇三杯酒好，况逢一朵花新。片时欢笑且相亲。明日阴晴未定。

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <string>

 #include <ctime>

 #define LOCAL

 const int MAXN =  *  *  + ;

 const long long MOD = ;//费马数论变换的费马素数

 long long G = ;//元根

 using namespace std;

 typedef long long ll;

 ll x1[MAXN], x2[MAXN];

 ll data[MAXN], Ans[MAXN];

 ll f[MAXN], I[MAXN], nI[MAXN], C[MAXN];

 ll inv2[MAXN], wn[MAXN], Inv[MAXN];

 ll pow(ll a, ll b){

    if (b == ) return  % MOD;

    if (b == ) return a % MOD;

    ll tmp = pow(a, b / );

    if (b %  == ) return (tmp * tmp) % MOD;

    else return ((tmp * tmp) % MOD * (a % MOD)) % MOD;

 }

 ll exgcd(ll a, ll b, ll &x, ll &y){

    if (b == ){x = 1ll; y = ; return a;}

    ll tmp = exgcd(b, a % b, y, x);

    y -= x * (a / b);

    return tmp;

 }

 ll inv(ll a, ll p){

    ll x, y;

    ll tmp = exgcd(a, p, x, y);

    return ((x % MOD) + MOD) % MOD;

 }

 void change(ll *x, int len, int loglen){

      for (int i = ; i < len; i++){

          int t = i, k = , tmp = loglen;

          while (tmp--) {k = (k << ) + (t & ); t >>= ;}

          if (k < i) swap(x[i], x[k]);

      }

      return;

 }

 void FNT(ll *x, int len, int loglen, int type){

      if (type) change(x, len, loglen);

      int t;

      t = (type ? : ( << loglen));

      for (int i = ; i < loglen; i++){

          if (!type) t >>= ;

          int l = , r = l + t;

          while (l < len){

                ll a, b;

                ll tmp = 1ll, w = wn[t];

                if (!type) w = Inv[t];

                for (int j = l; j < l + t; j++){

                    if (type){

                       a = x[j] % MOD;

                       b = (x[j + t] * (tmp % MOD)) % MOD;

                       x[j] = (a + b) % MOD;

                       x[j + t] = ((a - b) % MOD + MOD) % MOD;

                    }else{

                       a = (x[j] + x[j + t]) % MOD;

                       b = ((((x[j] - x[j + t]) % MOD + MOD) % MOD) * tmp) % MOD;

                       x[j] = a;

                       x[j + t] = b;

                    }

                    tmp = (tmp * w) % MOD;

                }

                l = r + t;

                r = l + t;

          }

          if (type) t <<= ;

      }

      if (!type){

         change(x, len, loglen);

         for (int i = ; i < len; i++) x[i] = (x[i] % MOD * inv(len, MOD)) % MOD;

      }

 }

 //CDQ分治

 void solve(int l, int r){

      if (l == r){

         //T为组合数的, I[l]为阶乘的模

         f[l] = (C[l] - (I[l - ] * f[l]) % MOD + MOD) % MOD;

         return;

      }

      int mid = (l + r) >> ;

      solve(l, mid);

      int len = max(mid - l + , r - mid), loglen = ;

      while ((<<loglen) < ((r - l + ) << )) loglen++;//要把卷积分成两个部分

      for (int i = ; i < (<<loglen); i++) x1[i] = x2[i] = ;

      for (int i = l; i <= mid; i++) x1[i - l] = (nI[i - ] * f[i]) % MOD;

      for (int i = ; i <= r - l; i++) x2[i] = (C[i] * nI[i]) % MOD;

      FNT(x1, (<<loglen), loglen, );

      FNT(x2, (<<loglen), loglen, );

      for (int i = ; i < (<<loglen); i++) x1[i] = (x1[i] * x2[i]) % MOD;

      FNT(x1, (<<loglen), loglen, );

      for (int i = mid + ; i <= r; i++) f[i] = (f[i] + x1[i - l] % MOD) % MOD;

      solve(mid + , r);

 }

 int n;

 void init(){

      scanf("%d", &n);

      inv2[] = ;

      inv2[] = inv(, MOD);

      //预处理2的阶乘的逆元

      for (int i = ; i <= n; i++) inv2[i] = (inv2[i - ] * inv2[]) % MOD;

      for (int i = ; i <=  * n; i++){

          if (i !=  && (MOD - ) / ( * i) == (MOD - ) / ( * (i - ))){

             wn[i] = wn[i - ];

             Inv[i] = Inv[i - ];

          }else{

             wn[i] = pow(G, (MOD - ) / ( * i)) % MOD;

             Inv[i] = inv(wn[i], MOD) % MOD;

          }

      }

      I[] = nI[] = ;//分别代表阶乘和阶乘的-1次方

      for (int i = ; i <= n; i++){

          I[i] = (long long)(i * I[i - ]) % MOD;

          nI[i] = (inv((long long)i, MOD) * nI[i - ]) % MOD;

          //printf("%lld\n", nI[i]);

      }

      //预处理组合数2^C(n, 2)

      for (int i = ; i <= n; i++){

          C[i] = pow(2ll, (long long)((long long)i * (i - )) / ) % MOD;

          //printf("%lld\n", C[i]);

      }

 }

 int main() {

     init();

     solve(, n);

     printf("%lld\n", f[n]);

     return ;

 }

相关阅读

目录[+]