【线性容斥】最后的晚餐dinner

Myth丶恋晨 2024-03-22 17:17 36阅读 0赞

[C-最后的晚餐(dinner)\_牛客竞赛数学专题班容斥原理 (nowcoder.com)][C-_dinner_ _nowcoder.com]

题意：

![11831078d96e46ddb025d8940afcc1ae.png][]

思路：

![c9881eb43f2041468b1f57acf9798d1b.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=3e7+10;
    const int mod=1e9+7;
    ll quick_pow(ll x,ll n)
    {
        ll ans=1;
        while( n )
        {
            if( n&1 )    ans = ans*x%mod;
            x = x*x%mod; n>>=1;
        }
        return ans;
    }
    int fac[maxn],n,inv[maxn];
    int C(int n,int m)
    {
        return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    signed main()
    {
        cin >> n;
        if(n==1) {printf("0");return 0;}
        fac[0]=1;
        for(int i=1;i<=n*2;i++)
            fac[i] = (ll) fac[i-1] * i % mod;
        inv[n] = quick_pow( (ll)fac[n],(ll)mod-2 );
        for(int i=n-1;i>=0;i--)
        {
            inv[i] = (ll)inv[i+1]*(i+1)%mod;
        }
        ll er=quick_pow(2,n),ans=0,FAC=fac[n-1];
        for(int i=n;i>=0;i--)
        {
            ll temp = (ll)C(n,i)*er%mod*FAC%mod;
            er = (ll)er*inv[2]%mod;  FAC = FAC*(2*n-i)%mod;
            if( i&1 )    ans = (ans-temp)%mod;
            else    ans = (ans+temp)%mod;
            ans = (ans+mod)%mod;
        }
        printf("%lld", (ans%mod+mod)%mod );
    }

[C-_dinner_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/22529/C
[11831078d96e46ddb025d8940afcc1ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/be1626ccd2a54e858a14a2eb2f05dd41.png
[c9881eb43f2041468b1f57acf9798d1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4b104c0d816d42be9b6c1bd44f44a5d1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，36人围观）

还没有评论，来说两句吧...

相关阅读

相关【线性容斥】最后的晚餐dinner

[C-最后的晚餐(dinner)\_牛客竞赛数学专题班容斥原理 (nowcoder.com)][C-_dinner_ _nowcoder.com] 题意： ![118310

Myth丶恋晨/ 2024年03月22日 17:17/ 0 赞/ 37 阅读

相关容斥原理

公式 ![在这里插入图片描述][20201112232850897.png_pic_center] 例题 ![2020111223365493.png][] 求

- 日理万妓/ 2022年12月20日 14:59/ 0 赞/ 185 阅读

相关容斥原理详解

翻译：vici@cust 对容斥原理的描述容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。描述容斥原理

亦凉/ 2022年06月18日 07:25/ 0 赞/ 255 阅读

相关广义容斥原理

![Center][] ![Center 1][] ![Center 2][] ![Center 3][] ![Center 4][] ![Center 5][] ![Cent

布满荆棘的人生/ 2022年06月10日 12:17/ 0 赞/ 245 阅读

相关组合数学容斥原理

![20180410143512519][]如图中划线所示，容斥原理就是运用集合中具有性质的对象来算出不具有所有性质的对象个数。 [20180410143512519]:

男娘i/ 2022年05月27日 02:55/ 0 赞/ 273 阅读

相关 HDU1695GCD 容斥

原来用莫比乌斯写过这个[传送门][Link 1]，发现这个用容斥挺好理解，就是跑的比莫比乌斯慢，莫比乌斯跑了40ms，这个跑了400ms。估计复杂度是O(n\6\2^6)大

Love The Way You Lie/ 2022年05月16日 02:55/ 0 赞/ 240 阅读

相关 HDU 5514 巧妙的容斥

题意：给你一些数，对于每一个数a，可以得到t=(t+a)%m,t可以无限制算下去，问0~m-1之间能被得到的数的和。思路：根据欧几里得原理，a能得到的数就是a和m的最大公约

迈不过友情╰/ 2022年05月08日 08:36/ 0 赞/ 191 阅读

相关容斥原理解释

容斥原理各种地方各种解释，又是画图又是举例，但是我单单觉得百度百科解释的很好！容斥原理：在[计数][Link 1]时，必须注意没有重复，没有遗漏。为了使[重叠][Link

刺骨的言语ヽ痛彻心扉/ 2022年03月18日 07:04/ 0 赞/ 291 阅读

相关容斥原理

目录容斥原理基本的容斥原理反演二项式反演 Möbius反演容斥原理大力推荐《组合数

深碍√TFBOYSˉ_/ 2021年12月16日 03:04/ 0 赞/ 379 阅读

相关集合计数：容斥原理

[zkt大神的同题题解：][zkt][ https://www.cnblogs.com/hzoi-DeepinC/articles/11102979.html][zkt] D

Myth丶恋晨/ 2021年10月30日 05:08/ 0 赞/ 391 阅读