[HNOI]2011卡农

这是一道很好的组合数学题。

对于和我一样五音里面有六音不全的人来说，我们就应该转换一下题目的意思：

一句话题意：

题目的意思就是说要从一个有 n 个元素的集合当中选出一个长度为m的集合，然后满足：

1.无序性

2.这每个音阶出现的次数为偶数

3.这些元素满足单一性

4.不为空集

所以考虑组合：：：

上过高中的应该都知道，一个拥有 n 个元素的集合，那么它的子集的数量就是 \(2^n\) - 1,那么对于每一个 \(i\)，组合的数量就是 \(A_{2^n-1}^{i-1}\) ,之后我们可以发现：

\(2^n\) - 1 的数值大小是固定的，所以我们可以先计算所有的变量之后在最后再去对 \(m!\)进行操作，故可以预处理：

a[0] = 1;//边界

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

     a[i] = a[i-1] * (sum - i + 1) % mod;

说实话，还有一种预处理方式，但我导完式子之后就不想打了，在这里还是推导一遍吧。。。

\[A_{2^n-1}^{i-1} = \frac{(2^n - 1)!}{(2^n -1-i+1)!} = \frac{\prod_{j=1}^{2^n-1}j}{\prod_{j=1}^{2^n-i}j} =
\]

\[\frac{\prod_{j={2^n-i+1}}^{2^n-1}j * \prod_{j=1}^{2^n-i}j}{\prod_{j=1}^{2^n-i}j}
= {\prod_{j={2^n-i+1}}^{2^n-1}j}
\]

这个式子的代码自己敲吧，反正我是不想敲

然后就可以开始dp了：

三种转移：

1.\(f_i = a_i\)

2.\(f_i = f_i - f_{i-1}\)

3.\(f_i = (f_i - f_{i-2} * (i-1) * (2^n - i)\)

相信前面的两个式子大家应该都可以看的懂，那就来解释一下第三个吧：

在选到第\(i\)个数的时候，那么就只剩下\(i-1\)个数来备选，并且我们在实现\(2^n-1\)的时候，我们可以用\(sum - i + 2\)来实现\(sum = 2^n -1\)

所以code：

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline void f()

{cout<<"fuck"<<endl;}

inline void openfile()

{freopen("t.txt","r",stdin);}

namespace xin

{

   #define m(c,num) memset(c,num,sizeof(c))

   int n,m;

   const int maxn = 1e6+10;

   inline int ksm(int x,int y,int mod)

   {

       int ans = 1;

       while(y)

       {

           if(y & 1) ans = ans * x % mod,ans %= mod;

           x = x * x % mod,x %= mod;

           y >>= 1;

       }

       return ans;

   }

   inline void qmod(int &x,int mod)

   {x %= mod;}

   int a[maxn],f[maxn];

   const int mod = 1e8+7;

   inline short main()

   {

       // openfile();

       scanf("%lld%lld",&n,&m);

       int sum = ksm(2,n,mod) - 1;

       a[0] = f[0] = 1;

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

           a[i] = a[i-1] * (sum - i + 1) % mod,qmod(a[i],mod);

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

       {

           f[i] = a[i-1];

           f[i] = f[i] - f[i-1];

           f[i] = (f[i] - f[i-2] % mod * (i - 1)% mod * (sum - i + 2) % mod + mod) % mod;

       }

       int jie = 1;

       for(register int i=1;i<=m;++i) jie = jie * i % mod,qmod(jie,mod);

       int inv = ksm(jie,mod-2,mod);

       cout<<f[m] * inv % mod<<endl;

       return 0;

   }

}

signed main() {return xin::main();}

忽略神仙码风。。。

巴特西

[HNOI]2011卡农

这是一道很好的组合数学题。

一句话题意：

最新文章

热门文章