HDU 5399 数学 Too Simple

题意：有m个1~n的映射，而且对于任意的 i 满足 f₁(f₂(...f_m(i))) = i

其中有些映射是知道的，有些是不知道的，问一共有多少种置换的组合。

分析：

首先这些置换一定是1~n的一个置换(也就是1~n的一个排列)才行，因为如果某两个数映射到同一个数的话，那么这个数往后无论怎么映射，这两个数最终映射的结果还是一样的。

如果所有的f都给出来的话，那么只要判断一下就行。

如果有一个置换不知道的话，这个置换是可以通过前后的置换计算出来的，所以只有唯一解。

如果有两个置换不知道的话，第一个置换可以任意确定，有n!种情况，第二个置换根据第一个置换确定。

以此类推，有c个未知的置换的话，其中c-1个可以自由确定，而且互补影响，最后一个置换根据前面所有置换唯一确定，所以中的方案数是(n!)^c-1

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn =  + ;

 const LL MOD = ;

 int n, m;

 bool vis[maxn];

 int a[maxn][maxn];

 inline LL mul_mod(LL a, LL b) { return a * b % MOD; }

 LL pow_mod(LL a, int n)

 {

     LL ans = 1LL, base = a;

     while(n)

     {

         if(n & ) ans = mul_mod(ans, base);

         base = mul_mod(base, base);

         n >>= ;

     }

     return ans;

 }

 LL fac[maxn];

 int main()

 {

     fac[] = ;

     for(int i = ; i < maxn; i++) fac[i] = fac[i - ] * i % MOD;

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         int cnt = ;

         bool ok = true;

         for(int i = ; i <= m; i++)

         {

             scanf("%d", &a[i][]);

             if(a[i][] == -) { cnt++; continue; }

             for(int j = ; j <= n; j++) scanf("%d", &a[i][j]);

             memset(vis, false, sizeof(vis));

             for(int j = ; j <= n; j++)

             {

                 if(vis[a[i][j]]) { ok = false; break; }

                 vis[a[i][j]] = true;

             }

         }

         if(!ok) { puts(""); continue; }

         if(!cnt)

         {

             bool ok = true;

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

             {

                 int t = i;

                 for(int j = m; j >= ; j--) t = a[j][t];

                 if(t != i) { ok = false; break; }

             }

             if(ok) puts(""); else puts("");

         }

         else printf("%I64d\n", pow_mod(fac[n], cnt - ));

     }

     return ;

 }

代码君

巴特西

HDU 5399 数学 Too Simple

最新文章

热门文章