题意
有(n)个位置,每次你需要以(1 sim n-1)的一个排列的顺序去染每一个颜色,第(i)个数可以把(i)和(i+1)位置染成黑色。一个排列的价值为最早把所有位置都染成黑色的次数。问所有排列的分数之和
sol
神仙题orz
不难想到我们可以枚举染色的次数(i in [lceil frac{n}{2} rceil, n – 1])。那么问题转化为求有多少排列是在(i)次之后把所有位置染成黑色(需要o(1)的复杂度)
我们把这个问题具体化一下,首先第一个位置必须要染,用去一次操作,此时还有(t = n-2)个位置没有染。对于一次染色,我们可以把两个位置染成黑色,也可以把一个位置染成黑色。那么问题转化为每次可以让(t)(-1)或者(-2)。问在(i – 1)操作后(t = 0)的方案数。
这个问题好像还是不好做,但是我们可以去求至多(i-1)次操作后(t=0)的方案。可以先把每次的(-1)算进去,这样每次就变成了(-0/-1)那么只要在剩下的(i-1)次操作中有((n-2)-(i-1))次选了(-1)就一定可行。
因此方案数为(c_{i-1}^{n-i-1}),最后每次计算的时候在乘上排列的系数就行了
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e6 + 10, inf = 1e9 + 7, mod = 1000000007; template<typename a, typename b> inline void chmax(a &x, b y) { x = x > y ? x : y; } template<typename a, typename b> inline void chmin(a &x, b y) { x = x < y ? x : y; } template<typename a, typename b> inline int mul(a x, b y) { return 1ll * x * y % mod; } template<typename a, typename b> inline void add2(a &x, b y) { if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y); } template<typename a, typename b> inline int add(a x, b y) { if(x + y < 0) return x + y + mod; else return x + y >= mod ? x + y - mod : x + y; } template<typename a, typename b> inline int fp(a a, b p) { int base = 1; while(p) { if(p & 1) base = mul(base, a); a = mul(a, a); p >>= 1; } return base; } inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, fac[maxn], ifac[maxn], f[maxn]; int c(int n, int m) { if(m > n) return 0; return mul(fac[n], mul(ifac[m], ifac[n - m])); } int main() { n = read(); fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = mul(i, fac[i - 1]); ifac[n] = fp(fac[n], mod - 2); for(int i = n; i >= 1; i--) ifac[i - 1] = mul(ifac[i], i); int down = n / 2 + (n & 1); for(int i = down; i < n; i++) f[i] = mul(mul(c(i - 1, n - i - 1), fac[i]), fac[n - i - 1]); int ans = 0; for(int i = down; i < n; i++) add2(ans, mul(i, add(f[i], -f[i - 1]))); cout << ans; return 0; } /* 3 0 1 1 5 7 3 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605106.html