题目描述

众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。他将声音分成 n 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 1 到 n 个音阶构成的和声，即从 n 个音阶中挑选若干个音阶同时演奏出来。为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。现在的问题是：小余想知道包含 m 个片段的音乐一共有多少种。两段音乐 a 和 b 同种当且仅当将 a 的片段重新排列后可以得到 b。例如：假设 a

为{{1,2},{2,3}}，b 为{{3,2},{2,1}}，那么 a 与 b 就是同种音乐。由于种数很多，你只需要

输出答案模 100000007（质数）的结果。

输入输出格式

输入格式：

从文件input.txt中读入数据，输入文件仅一行，具体是用空格隔开的两个正整数n和m，分别表示音阶的数量和音乐中的片段数。20%的数据满足n,m≤5，50%的数据满足n,m≤3000，100%

的数据满足n,m≤1000000。

输出格式：

输出文件 output.txt 仅包含一个非负整数，表示音乐的种数模 100000007 的结果。【输入输出样例】

输入输出样例

2 3

1

说明

样例解释：音乐为{{1},{2},{1,2}}

首先题目里说是无序的，但是不要管它，我们先把它看成有序的，最后除以一个m!即可。我们考虑补集转换，首先所有的子集个数应该是2^n−1，我们定义f[i]为挑选i个片段的合法的方案数，此时总数应该是A(2^n−1,i−1)（排列数）。为什么是i−1而不是i呢？因为要保证总数是偶数，也就是说如果你确定了i−1个片段第i个片段也就确定了。而这样肯定多算了，具体来说有两部分： 
1、如果前i−1个已经合法,那么第i个就是空集，这样肯定不合法，所以要减去f[i−1]。 
2、如果根据前i−1个确定出来的第i个集合和前面的某一个重复，这样肯定是不合法的。 
因为考虑顺序，所以那个和第i个重复的集合有i−1种位置，对于每种位置，

当前的总数偶数去掉两个数之后还是偶数，所以剩下其他数的方案数为f[i−2]。

然后我们需要算出有多少种可能重复的方案，因为我们已经确定了(i−2)个位置，所以方案数为(2^n−1−(i−2))。

所以总体的方程就是：f[i]=A(2^n−1,i−1)−f[i−1]−f[i−2]∗(2^n−1−(i−2))∗(i−1) 
最后在乘上一个m!关于mod的逆元即可。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 long long Mod=,s;

 long long n,m;

 long long pre[],A[],f[];

 long long qpow(long long x,int y)

 {

     long long res=;

     while (y)

     {

         if (y%==)

         {

             res=(res*x)%Mod;

         }

       x=(x*x)%Mod;

       y/=;

     }

     return res;

 }

 int main()

 {long long i;

     cin>>n>>m;

      s=(qpow(,n)-+Mod)%Mod;

       //p=qpow(2,n)%Mod;

      pre[]=;

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

      {

             pre[i]=(pre[i-]*(s-i++Mod)%Mod)%Mod;

      }

      A[]=;

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

      A[i]=((Mod-Mod/i)*A[Mod%i]+Mod)%Mod;

       f[]=;f[]=;

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

     {

         f[i]=(pre[i-]+Mod)%Mod;

         f[i]=(f[i]-f[i-]+Mod)%Mod;

         if (f[i]<) f[i]+=Mod;

         f[i]=(f[i]-((f[i-]*(i-)%Mod)*((s-i++Mod)%Mod))%Mod+Mod)%Mod;

         if (f[i]<) f[i]+=Mod;

     }

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

     f[m]=(f[m]*A[i])%Mod;

 cout<<f[m];

 }