http://codeforces.com/contest/294/problem/C
把那个数组n分段了,那么有两类。
1、开头和端点那些,就是只有一端在开始的,这个时候,要开完这些灯,只能循序渐进,1--2--3--4
2、第二类就是中间那些,两端都可以开始,那些段的开灯次数是2^(len - 1)。因为这个就是看成一个双端队列,每一次都可以从头或者尾取数字,所以每次的决策有2种,然后最后一次只有一个数,所以直接是它。
现在就是把他们若干段合并后,有多少种情况的问题了。
其实就是
A1、B1、C1
A2、B2、C2
A3、B3、C3
的排列问题,而且,B1要放的话,首先需要A1在它前面,同理C3要放的话,需要A3和B3在它前面。
那么这个其实就是平均分堆问题。
A1、B1、C1其实只有一种合法的排列,就是A1 B1 C1
那么其它的B1、C1、A1这些就是不合法的。
那么就是3!/ 3!
就是只有一种排列是合法的。
所以样例三的答案是9! / (3! * 3! * 3!) * 4
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int MOD = 1e9 + 7; const int maxn = 1e3 + 20; vector<int>pos; vector<int>a; LL quick_pow(LL a, LL b, LL MOD) { //求解 a^b%MOD的值 LL base = a % MOD; LL ans = 1; //相乘,所以这里是1 while (b) { if (b & 1) { ans = (ans * base) % MOD; //如果这里是很大的数据,就要用quick_mul } base = (base * base) % MOD; //notice。注意这里,每次的base是自己base倍 b >>= 1; } return ans; } LL A[maxn]; bool is[maxn]; void work() { A[0] = 1; for (int i = 1; i <= maxn - 20; ++i) { A[i] = A[i - 1] * i % MOD; } int n, m; cin >> n >> m; a.push_back(0); for (int i = 1; i <= m; ++i) { int x; cin >> x; a.push_back(x); } a.push_back(n + 1); sort(a.begin(), a.end()); // for (int i = 0; i < a.size(); ++i) { // cout << a[i] << " "; // } // cout << endl; for (int i = 1; i < a.size(); ++i) { if (a[i] - a[i - 1] - 1 == 0) continue; pos.push_back(a[i] - a[i - 1] - 1); if (a[i] != n + 1 && a[i - 1] != 0) { is[pos.size() - 1] = true; } } // for (int i = 0; i < pos.size(); ++i) { // cout << pos[i] << " "; // } // cout << endl; LL add = 1; for (int i = 0; i < pos.size(); ++i) { if (!is[i]) continue; // cout << "fff" << endl; add = add * quick_pow(2, pos[i] - 1, MOD) % MOD; } LL sum = 0, haha = 1; for (int i = 0; i < pos.size(); ++i) { sum += pos[i]; haha = haha * A[pos[i]] % MOD; } LL ans = A[sum] * quick_pow(haha, MOD - 2, MOD) % MOD; ans = ans * add % MOD; cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }