CF294C Shaass and Lights

### 题目大意： 有n盏灯，(0<=n<=1000),有m盏已经点亮，每次只能点亮与已经点亮的灯相邻的灯，求总方案数，答案对1e9+7取模 第一行：两个整数n,m表示灯的总数和已点亮的灯的数目 第二行m个数，表示已点亮的灯的编号 ### 分析： 我们可以借助已经被点亮的灯作为分界点，找到若干个长度不为0的开区间。 对于两边都有开着的灯的区间，我们点亮它每次可以点亮最左边一盏或者最右边一盏，而最后一盏灯只有一种方法，所以点亮长度为len的区间的方案数为：2^(len-1) 特别地，对于两端的区间（一边有灯开着，一边是边界（1或者n）），只有一种方案数（顺着一路点下去） 根据乘法原理，可以先计算出ans*=2^(len2-1)2^(len-2-1)...2^(len(cnt-1)-1)注意开始的时候是i=2，最后一段是i=cnt-1；（最初最末两端算上是没有意义的） 但是由于点灯的时候可以交叉在每个区间内点灯，所以这样的ans还是少了很多。 所以我们重新这样考虑： 考虑将每个区间内考虑成颜色相同的len个球，不同区间球的颜色不同。每一个排列可以当做是一个指令，不同的合法的指令是不同的方案数。 容易知道最初的方案数为：（n-m）！我们将它处理成多重集合的排列，(n-m)!/len1!len2!...lencnt!。这样保证了每个区间内的同一种颜色的球的“单纯相对顺序”（只是这些球之间交换顺序）变化都算作是一种方案。 但是一个区间内，并不是一种方案，对于len的球数，可以有2^(len-1)种合法排列，利用乘法原理再将它们相乘，就可以得出正确的答案。 (需要：快速幂，乘方的乘法逆元） 附代码： ```cpp #include<bits/stdc++.h> #define ll long long #define int long long using namespace std; const int mod=1e9+7; const int N=1005; int n,m; int len[N];//区间长度; ll fac[N];//阶乘; ll ifac[N];//阶乘逆元; ll qm(int x,int y) { ll base=x; ll ans=1; while(y) { if(y&1) ans=(ans*base)%mod; base=(base*base)%mod; y>>=1; } return ans%mod; }//快速幂 int cnt; ll anss=1; int h[N]; signed main() { scanf("%lld%lld",&n,&m); int last=0; int x; for(int i=1;i<=m;i++) {scanf("%lld",&h[i]);} sort(h+1,h+m+1);//注意，编号可能不是单调的。 len[++cnt]=h[1]-last-1; for(int i=2;i<=m;i++) { if(h[i]-h[i-1]>1) len[++cnt]=h[i]-h[i-1]-1; } len[++cnt]=n-h[m]; for(int i=2;i<=cnt-1;i++) anss=(anss*qm(2,len[i]-1))%mod;//先处理2^len fac[0]=1; ifac[0]=1; for(int i=1;i<=n-m;i++) fac[i]=(fac[i-1]*i)%mod;//阶乘 ifac[n-m]=qm(fac[n-m],mod-2)%mod;//费马小定理先算n-m for(int i=n-m-1;i>=1;i--) ifac[i]=(ifac[i+1]*(i+1))%mod;//递推算阶乘逆元 anss=(anss*fac[n-m])%mod; for(int i=1;i<=cnt;i++) anss=(anss*ifac[len[i]])%mod;//多重集合排列处理 printf("%lld",anss%mod); return 0; } ``` 还有一种组合数学的思想， 就是利用乘法原理，每次乘上：在每次剩余的位置放上len个数的方案数。 友链： https://blog.csdn.net/qq_38538733/article/details/76409237