[BZOJ3456][CDQ分治+FNT]城市规划

试题来源 　　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。

  1 /*
  2 宋代朱敦儒
  3 《西江月·世事短如春梦》
  4 世事短如春梦，人情薄似秋云。不须计较苦劳心。万事原来有命。
  5 幸遇三杯酒好，况逢一朵花新。片时欢笑且相亲。明日阴晴未定。 
  6 */
  7 #include cstdio
  8 #include cstring
  9 #include algorithm
 10 #include cmath
 11 #include queue
 12 #include vector
 13 #include iostream
 14 #include string
 15 #include ctime
 16 #define LOCAL
 17 const int MAXN = 130000 * 2 * 2 + 10;
 18 const long long MOD = 1004535809;//费马数论变换的费马素数 
 19 long long G = 3;//元根 
 20 using namespace std;
 21 typedef long long ll;
 22 ll x1[MAXN], x2[MAXN];
 23 ll data[MAXN], Ans[MAXN];
 24 ll f[MAXN], I[MAXN], nI[MAXN], C[MAXN];
 25 ll inv2[MAXN], wn[MAXN], Inv[MAXN];
 26 
 27 ll pow(ll a, ll b){
 28    if (b == 0) return 1 % MOD;
 29    if (b == 1) return a % MOD;
 30    ll tmp = pow(a, b / 2);
 31    if (b % 2 == 0) return (tmp * tmp) % MOD;
 32    else return ((tmp * tmp) % MOD * (a % MOD)) % MOD;
 33 }
 34 ll exgcd(ll a, ll b, ll x, ll y){
 35    if (b == 0){x = 1ll; y = 0; return a;}
 36    ll tmp = exgcd(b, a % b, y, x);
 37    y -= x * (a / b);
 38    return tmp;
 39 }
 40 ll inv(ll a, ll p){
 41    ll x, y;
 42    ll tmp = exgcd(a, p, x, y);
 43    return ((x % MOD) + MOD) % MOD; 
 44 }
 45 void change(ll *x, int len, int loglen){
 46      for (int i = 0; i  len; i++){
 47          int t = i, k = 0, tmp = loglen;
 48          while (tmp--) {k = (k  1) + (t  1); t = 1;}
 49          if (k  i) swap(x[i], x[k]);
 50      }
 51      return;
 52 }
 53 void FNT(ll *x, int len, int loglen, int type){
 54      if (type) change(x, len, loglen);
 55      int t;
 56      t = (type ? 1: (1  loglen));
 57      for (int i = 0; i  loglen; i++){
 58          if (!type) t = 1;
 59          int l = 0, r = l + t;
 60          while (l  len){
 61                ll a, b;
 62                ll tmp = 1ll, w = wn[t];
 63                if (!type) w = Inv[t];
 64                for (int j = l; j  l + t; j++){
 65                    if (type){
 66                       a = x[j] % MOD;
 67                       b = (x[j + t] * (tmp % MOD)) % MOD;
 68                       x[j] = (a + b) % MOD;
 69                       x[j + t] = ((a - b) % MOD + MOD) % MOD; 
 70                    }else{
 71                       a = (x[j] + x[j + t]) % MOD;
 72                       b = ((((x[j] - x[j + t]) % MOD + MOD) % MOD) * tmp) % MOD;
 73                       x[j] = a;
 74                       x[j + t] = b;
 75                    }
 76                    tmp = (tmp * w) % MOD;
 77                }
 78                l = r + t;
 79                r = l + t;
 80          } 
 81          if (type) t = 1;
 82      }
 83      if (!type){
 84         change(x, len, loglen);
 85         for (int i = 0; i  len; i++) x[i] = (x[i] % MOD * inv(len, MOD)) % MOD;
 86      }
 87 }
 88 //CDQ分治 
 89 void solve(int l, int r){
 90      if (l == r){
 91         //T为组合数的, I[l]为阶乘的模 
 92         f[l] = (C[l] - (I[l - 1] * f[l]) % MOD + MOD) % MOD;
 93         return;
 94      }
 95      int mid = (l + r)  1;
 96      solve(l, mid);
 97      int len = max(mid - l + 1, r - mid), loglen = 1;
 98      while ((1loglen)  ((r - l + 1)  1)) loglen++;//要把卷积分成两个部分
 99      
100      for (int i = 0; i  (1loglen); i++) x1[i] = x2[i] = 0;
101      for (int i = l; i = mid; i++) x1[i - l] = (nI[i - 1] * f[i]) % MOD;
102      for (int i = 1; i = r - l; i++) x2[i] = (C[i] * nI[i]) % MOD;
103      
104      FNT(x1, (1loglen), loglen, 1);
105      FNT(x2, (1loglen), loglen, 1);
106      for (int i = 0; i  (1loglen); i++) x1[i] = (x1[i] * x2[i]) % MOD;
107      FNT(x1, (1loglen), loglen, 0);
108      for (int i = mid + 1; i = r; i++) f[i] = (f[i] + x1[i - l] % MOD) % MOD;
109      solve(mid + 1, r);
110 }
111 int n;
112 void init(){
113      scanf("%d", n);
114      inv2[0] = 1;
115      inv2[1] = inv(2, MOD);
116      //预处理2的阶乘的逆元 
117      for (int i = 2; i = n; i++) inv2[i] = (inv2[i - 1] * inv2[1]) % MOD;
118      for (int i = 1; i = 2 * n; i++){
119          if (i != 1  (MOD - 1) / (2 * i) == (MOD - 1) / (2 * (i - 1))){
120             wn[i] = wn[i - 1];
121             Inv[i] = Inv[i - 1];
122          }else{
123             wn[i] = pow(G, (MOD - 1) / (2 * i)) % MOD;
124             Inv[i] = inv(wn[i], MOD) % MOD;
125          }
126      }
127      I[0] = nI[0] = 1;//分别代表阶乘和阶乘的-1次方 
128      for (int i = 1; i = n; i++){
129          I[i] = (long long)(i * I[i - 1]) % MOD;
130          nI[i] = (inv((long long)i, MOD) * nI[i - 1]) % MOD;
131          //printf("%lld\n", nI[i]);
132      } 
133      //预处理组合数2^C(n, 2)
134      for (int i = 1; i = n; i++){
135          C[i] = pow(2ll, (long long)((long long)i * (i - 1)) / 2) % MOD;
136          //printf("%lld\n", C[i]);
137      }
138 }
139 
140 
141 int main() {
142    
143     init();
144     solve(1, n);
145     printf("%lld\n", f[n]);
146     return 0;
147 }

View Code

 

转载于:https://www.cnblogs.com/hoskey/p/4379029.html