HDU 6397 Character Encoding（容斥）

╰半橙微兮° 2022-05-16 04:36 171阅读 0赞

[传送门][Link 1]

挑选m个数 ，和为k，数的取值为0~n-1，相当于将每个数加1，使挑的m个数和是k+m，可以看成k+m个1，用m-1个隔板，隔成m分，所以总数为C(m+k-1, m-1)，减去不合法的，就是大于n的情况。先看只有一个位置大于n，有C(m,1)\*C(m+k-n-1, m-1)种情况，但是有重复，比如1，3，2，1   。  3，1，2 ，1这两种情况，n是2，k是8的话，3、3、2、1是一种情况，而选①②两个位置的时候，会算两遍。以此类推，就是容斥思想。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n, m, k;
    ll p=998244353;
    /**************************/
    const int N =2e5+5;
    
    ll inv[N] = {1,1};  //inv[i] i的逆元。
    ll fac[N] = {1,1};    // fac[i] i!%p
    ll facv[N] = {1,1};   // facv[i] i!的逆元
    void init()
    {
        for(int i = 2 ; i < N ; i ++)
            inv[i] = (p-p/i) * inv[p%i] % p;
        for(int i = 2 ; i < N ; i ++)
            facv[i] = facv[i-1] * inv[i] % p;
        for(int i = 2 ; i < N ; i ++)
            fac[i] = fac[i-1]*i % p;
    }
    ll C(ll n,ll m)
    {
        if(n<m) return 0;
        if(m < 0) return 0;
        return fac[n]*facv[m]%p*facv[n-m]%p;
    }
    /********************************/O(1)求1e5之内的组合数
    
    int main(){
        init();
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%lld%lld%lld", &n, &m, &k);
            ll ans=C(m+k-1, m-1);
    
            ll f=1;
            for(ll i=1; i*n<=k; i++){
                f=-f;
                ans=(ans+f*C(m, i)*C(m+k-i*n-1, m-1)%p+p)%p;
            }
            printf("%lld\n", ans);
    
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6397

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu1695（容斥原理）

求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。 b和d分别除以k之后的区间里面，只需要求gcd(x,

一时失言乱红尘/ 2024年02月17日 23:41/ 0 赞/ 59 阅读

相关 Hdu 1695 GCD (数论容斥原理)

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

落日映苍穹つ/ 2022年08月26日 08:10/ 0 赞/ 161 阅读

相关 Hdu 4451 Dressing (简单容斥)

题意：有N种衣服，M种裤子和K种鞋子，已知哪些衣服和哪些裤子不能搭配，哪些裤子和哪些鞋子不能搭配，现在要选择一套(衣服+裤子+鞋子)，问有多少种搭配方法。思路：所有的不和谐

逃离我推掉我的手/ 2022年08月26日 08:04/ 0 赞/ 147 阅读

相关 HDU 1695 GCD （容斥原理）

[HDU 1695][] 题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。题解：注意到gcd(x,y)=k,说明x,y

男娘i/ 2022年07月12日 09:55/ 0 赞/ 242 阅读

相关 HDU 2197 本原串（数学+容斥）

题目链接： [HDU 2197][] 题意：由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本

朱雀/ 2022年06月15日 12:07/ 0 赞/ 186 阅读

相关 HDU-4135 Co-prime(容斥原理)

Co-prime Given a number N, you are asked to cou

野性酷女/ 2022年06月10日 13:55/ 0 赞/ 214 阅读

相关 hdu4135Co-prime——容斥定理

Given a number N, you are asked to count the number of integers between A and B inclusiv

灰太狼/ 2022年05月18日 00:10/ 0 赞/ 207 阅读

相关 HDU 6397 Character Encoding（容斥）

[传送门][Link 1] 挑选m个数，和为k，数的取值为0~n-1，相当于将每个数加1，使挑的m个数和是k+m，可以看成k+m个1，用m-1个隔板，隔成m分，所以总数为C

╰半橙微兮°/ 2022年05月16日 04:36/ 0 赞/ 172 阅读

相关 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 阅读