首页 > 其他分享 >## HDU7328 Snake

## HDU7328 Snake

时间:2023-08-05 21:13:38浏览次数:56  
标签:std HDU7328 ## res ll int Snake inv mod

HDU7328 Snake

tag: 容斥,生成函数

题目链接

题意:

1到n个数,分成m组,组队元素排列顺序不同则为不同的组,且每组元素个数不能超过k,问有多少种方案。

容斥做法:

  • 暂且不管排列的事情,先把问题看成求n个球,m个盒子,盒子不能为空,且每个盒子中球数不能超过k。
  • 要保证每盒球数不超过k,我们可通过容斥来解决,定义f(i)为至少i个盒子球数超过k了,最终答案ans即为: f(0)-f(1)+f(2)-....f(m)
  • 保证有i个盒子超过k,我们可以先给这x个盒子放k个,排列组合为$C_{m}^{i}$
    ,那么现在还剩n-xk个球,再用隔板法把他们分成m份,排列组合为$C_{n-ki-1}^{m-1}$
  • 最后再将 ans*(n!)/(m!),算上排序的组合数,而多重集之间没有排序关系,所以要除m的阶乘
  • 这题可以说是2021威海M的简单版本,推荐去写。

代码:

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+50;
const int mod=998244353;
ll fac[N],inv[N];

ll qsm(ll n,ll m){
    ll res = 1;;
    while(m){
        if(m&1) res = res*n%mod;
        n = n*n%mod;
        m >>= 1;
    }
    return res;
}

void init(){
    int mz =  1e6;
    fac[0] = inv[0] = 1;
    for(int i=1;i<=mz;i++) fac[i] = fac[i-1]*i%mod;
    inv[mz] = qsm(fac[mz],mod-2);
    for(int i = mz-1;i>=1;i--) inv[i] = inv[i+1]*(i+1)%mod;
}

ll C(int a,int b){
    if(a<b||b<0||a<0) return 0; 
    return (fac[a]*inv[b]%mod)*inv[a-b]%mod;
}

void solve(){
    int n,m,k; cin>>n>>m>>k;
    ll ans = 0;
    bool f = 1;
    for(int i=0;i<=m;i++){
       ll tmp = f ? 1 : mod-1;
       f ^= 1;
       ans = (ans+tmp*C(m,i)%mod*C(n-1-i*k,m-1)%mod)%mod;
    }
    ans = ans*fac[n]%mod*inv[m]%mod;
    cout<<ans<<le;
}
int main(){
    fst;
    init();
    int t; cin>>t;
    while(t--){
        solve();
    }
    return 0;
}   

生成函数做法:

  • 同上面一样先将问题看成小球分盒子问题,这回我们用生成函数求解ans
  • 因为首先不考虑内部排序,且盒子不能为空,那么一个盒子的生成函数为: $x+x{2}+x+...+x^{n} = \frac {x}{x-1}$
  • 同时不能超过k个,那么生成函数应该是:
    $x+x{2}+x+...+x^{k} = \frac {(x^k-1)x}{x-1}$
  • 我们要求的ans为$(\frac{(xk-1)x}{x-1})$的第n项,展开得到答案为 $(x^{k} − 1)^{m}(1 − x)^{-m}$的第 n − m 项, $(x^{k} − 1)^{m}$用二项式定理展开即可,$(1 − x){-m}$则需要用到广义二项式定理:$(1+x) = \sum_{i=0}{+\infty}C_{n+i-1}x^{i}$
  • 剩下步骤同上

代码:

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+50;
const int mod=998244353;
ll fac[N],inv[N];

ll qsm(ll n,ll m){
    ll res = 1;;
    while(m){
        if(m&1) res = res*n%mod;
        n = n*n%mod;
        m >>= 1;
    }
    return res;
}

void init(){
    int mz =  1e6;
    fac[0] = inv[0] = 1;
    for(int i=1;i<=mz;i++) fac[i] = fac[i-1]*i%mod;
    inv[mz] = qsm(fac[mz],mod-2);
    for(int i = mz-1;i>=1;i--) inv[i] = inv[i+1]*(i+1)%mod;
}

ll C(int a,int b){
    if(a<b||b<0||a<0) return 0; 
    return (fac[a]*inv[b]%mod)*inv[a-b]%mod;
}

void solve(){
    int n,m,k; cin>>n>>m>>k;
    vector<ll> a(n+1),b(n+1);
    for(int i=0;i*k<=n-m;i++){
        ll tmp = (i&1) ? mod-1: 1;
        a[i*k] = C(m,i)*tmp%mod;
    }

    for(int i=0;i<=n-m;i++){
        b[i] = C(m+i-1,i)%mod;
    }
    ll ans = 0;
    for(int i=0;i<=n-m;i++) ans = (ans+a[i]*b[n-m-i]%mod)%mod;
    ans = ans*fac[n]%mod*inv[m]%mod;
    cout<<ans<<le;
}
int main(){
    fst;
    init();
    int t; cin>>t;
    while(t--){
        solve();
    }
    return 0;
}   

标签:std,HDU7328,##,res,ll,int,Snake,inv,mod
From: https://www.cnblogs.com/touchfishman/p/17608629.html

相关文章

  • 第六周训练总结
    比赛总结牛客多校第五场3/4/10AC:C、D、G补题:H总结:本场比赛我们三个人开题是4,3,3分配的,然后有谁发现签到题,就会找另外一个说一下思路,然后开始敲代码。首先发现G题就和之前做过的一道题很相似,直接遍历加上尺取法就可以了,ska很快就敲完代码,然后交上去就直接ac了。然后就......
  • 2023-07-30~08-05第四周暑假生活
    本周每天学习一个小时hdfs,web设计hdfs和linux的操作主要用到命令窗口,大量陌生的命令操作是学习的一大难点主要学习了:hdfs的目录操作cd/usr/local/hadoop./bin/hdfsdfs-mkdir-p/user/hadoop在HDFS中创建一个“/user/hadoop”目录,“–mkdir”是创建目录的操作,“-p”表......
  • 前端面试经典手写题
    1、手写PromiseclassPromise2{state="pending";callbacks=[];constructor(fn){fn(this.resolve.bind(this),this.reject.bind(this));}resolve(result){if(this.state!=="pending")return;this.state="......
  • 高级 / 资深前端面试题集锦
    以下是一线互联网公司高级前端面试题总结,包括百度、腾讯、网易、字节、知乎、京东、滴滴,小米,感兴趣的欢迎留言交流。1、请简述JsBridge2、请说一下SSR的单机QPS3、请说一下eggJs的初始化原理4、前端错误如何捕获,promise的错误是如何捕获的5、vue的domdiff算法6、vue的Chil......
  • 前端面试经典算法题
    前言现在面试流行考核算法,做过面试官,也被面试。问算法对面试官来说,是一种解脱,找出了一个看似很高明且能偷懒的办法选择人,避免了不知道问啥的尴尬;被面试者,也找到了一种新的面试八股文,刷就对了;算法题让面试与被面试找到了一种平衡。在实际的开发中,很多被考核的算法确实没啥卵用,面......
  • gRPC Test
    目录简单使用ghzgithub:https://github.com/bojand/ghzghz官方文档:https://ghz.sh/简单使用下载后解压,将目录配置到path上,方便命令调用:ghz--insecure--protoxxx\Hello.proto--callpackage_name.service_name.rpc_method_name-d"{\"name\":\"a\"}"localho......
  • 2023年多校联训NOIP层测试4+洛谷 8 月月赛 I & RiOI Round 2
    2023年多校联训NOIP层测试4爆零了T1幸运数字\(0pts\)T2密码\(0pts\)没做到,咕了。T3小X和他的朋友们\(0pts\)没做到,咕了。T4树上询问\(0pts\)没做到,咕了。【LGR-150-Div.2】洛谷8月月赛I&RiOIRound2T1luoguP9496「RiOI-2」hacker\(100pts\)......
  • 练习曲
    这是一个做题记录。洛谷P1725琪露诺2023.8.5题目链接标签:动态规划、单调队列。一道动态规划题,先考虑暴力一点的做法:设\(dp[i]\)表示跳到第\(i\)个位置时所能获得的最大冰冻指数。那么\(i\)位置的状态可以从区间\([i-L,i-R]\)转移过来。转移方程:$dp[i]=max(dp[j]......
  • cookie封装
    cookie封装当提到"cookie封装",通常是指在开发中对浏览器cookie的处理进行封装和管理,以简化代码和提高可维护性。在Web开发中,cookie是一种用于存储少量数据的小文件,存储在用户的浏览器中。它们被广泛用于跟踪用户会话,记录用户偏好,进行用户身份验证等。在进行cookie封装时,你可......
  • 大数据总结
    我这周学了修改表操作、Hive支持的复杂数据类型等修改表操作  修改和删除分区都是修改元数据记录  Hive支持的复杂数据类型  ......