欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

agc023C - Painting Machines(组合数)

程序员文章站 2022-10-18 10:47:19
题意 "题目链接" 有$n$个位置,每次你需要以$1 \sim n 1$的一个排列的顺序去染每一个颜色,第$i$个数可以把$i$和$i+1$位置染成黑色。一个排列的价值为最早把所有位置都染成黑色的次数。问所有排列的分数之和 Sol 神仙题Orz 不难想到我们可以枚举染色的次数$i \in [\lce ......

题意

\(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
*/