首页 > ACM题库 > HDU-杭电 > HDU 4290-Counting Formations-递推-[解题报告]HOJ
2015
05-23

HDU 4290-Counting Formations-递推-[解题报告]HOJ

Counting Formations

问题描述 :

  With the coming release of Marcohard Balconies 100 operating system, people are more and more interested in its new UI (User Interface), code-named “Subway”.
  This UI presents your desktop as a grid that is divided into N rows and M columns (so you have N * M cells). In each cell, you can place one icon of an application of a certain type. Your applications can be of one of K types, numbered 1 through K. You’re an expert in this filed, so it is assumed that there is an unlimited number of applications of each type.
  Any placement is called an icon formation. Some of the icon formations are beautiful. An icon formation is called beautiful if and only if no pair of rows are similar. Two rows are similar if and only if for each X that 1 <= X <= K, they contain exactly the same number of applications of type X.
  GivenN,M, andK, you should solve for the number of different icon formations that are beautiful, modulo 109+7. Two formations are different if and only if there is a cell where the type of application in one formation is not the same as the type in another formation.
  You may assume that 1 <= N,M,K <= 32

输入:

  There are several test cases. For each test case there are 3 integers, named N,M,K, in a single line.
  Please process until EOF (End Of File).

输出:

  There are several test cases. For each test case there are 3 integers, named N,M,K, in a single line.
  Please process until EOF (End Of File).

样例输入:

2 2 2
5 3 2
3 5 7

样例输出:

10
0
894953467

Staginner剽悍地抽象出了数学模型并推出了各项数据,万事俱备只欠东风,可惜最后一步推错了,比赛时候这题没过。。

插板法组合数对应了不同icon的分配方案。

每种分配方案又对应了很多种摆放方案。

假设有s种分配方案,x[1]~x[s]分别对应了每种分配方案的摆放方案,可通过DP求得∑x 。

也可求得∑(x^2),∑(x^3)…

设M[p] = ∑(x^p)。

设S[p] = x[i1]*x[i2]*x[i3]…*x[ip],i1~ip为互不相同的1~s的序列。

题目所给棋盘是N行,我们求的就是S[N] * N!

——————————分割线——————————

以上是Staginner得到的数据与结论,详细的推导他应该会写博客的。

 

接下来要解决的就是如何用M[1]~M[p]来推S[p],没想到被我一推一推推出来了。

首先S[1] == M[1]

S[1] * M[1]的结果是两两不同x的积和相同x的平方项,那么去掉平方项就是S[2]的若干倍。

在S[1] * M[1]的过程中每一个S[2]的项都由两个组成它的x乘得一次,所以这个“若干倍”是2。

S[2] = (S[1] * M[1] – M[2]) / 2

递推过去,最终

S[p] = (S[p - 1] * M[1] – S[p - 2] * M[2] + S[p - 3] * M[3] – S[p - 4] * M[4] ….) / p

这样就得到了S[N]。

中间该取模取模,该求逆元求逆元,就OK了。

 

代码是在Staginner代码上改的。

 #include<stdio.h>
 #include<string.h>
 #define MAXD 33
 #define MOD 1000000007
 typedef __int64 LL;
 int N, M, K;
 LL C[MAXD][MAXD][MAXD], f[MAXD][MAXD], X[MAXD], S[MAXD];
 LL fac(LL a, int n)
 {
     int i;
     LL ans = 1;
     for(i = 0; i < n; i ++) ans = ans * a % MOD;
     return ans;
 }
 void exgcd(LL a, LL b, LL &x, LL &y)
 {
     if(b == 0) x = 1, y = 0;
     else exgcd(b, a % b, y, x), y -= x * (a / b);
 }
 LL getinv(LL a)
 {
     LL x, y;
     exgcd(a, MOD, x, y);
     x %= MOD;
     if(x < 0) x += MOD;
     return x;
 }
 void prepare()
 {
     int i, j, t;
     memset(C, 0, sizeof(C));
     C[1][0][0] = 1;
     for(i = 1; i <= 32; i ++)
     {
         C[1][i][0] = 1;
         for(j = 1; j <= i; j ++)
             C[1][i][j] = (C[1][i - 1][j] + C[1][i - 1][j - 1]) % MOD;
     }
     for(t = 2; t <= 32; t ++)
         for(i = 0; i <= 32; i ++)
             for(j = 0; j <= 32; j ++)
                 C[t][i][j] = fac(C[1][i][j], t);
 }
 void solve()
 {
     int i, j, k, t;
     LL ans;
     for(t = 1; t <= N; t ++)
     {
         memset(f, 0, sizeof(f)), f[0][0] = 1;
         for(i = 1; i <= K; i ++)
             for(j = 0; j <= M; j ++)
                 for(k = 0; k <= j; k ++)
                     f[i][j] = (f[i][j] + f[i - 1][k] * C[t][M - k][j - k]) % MOD;
         X[t] = f[K][M];
     }
     S[0] = 1, S[1] = X[1];
     for(i = 2; i <= N; i ++)
     {
         S[i] = 0;
         for(j = 1; j <= i; j ++)
         {
             if(j & 1) S[i] = (S[i] + S[i - j] * X[j] + MOD) % MOD;
             else S[i] = (S[i] - S[i - j] * X[j] + MOD) % MOD;
         }
         S[i] = S[i] * getinv(i) % MOD;
     }
     ans = S[N];
     for(i = 2; i <= N; i ++) ans = ans * i % MOD;
     if(ans < 0) ans += MOD;
     printf("%I64d\n", ans);
 }
 int main()
 {
     prepare();
     while(scanf("%d%d%d", &N, &M, &K) == 3)
         solve();
     return 0;
 }

 

参考:http://www.cnblogs.com/CSGrandeur/archive/2012/09/17/2688142.html