2018牛客网暑期ACM多校训练营(第六场)C

先从m个不同的颜色选k个然后排列即A(m,k),然后我们开始染色。
假如n为3,那么就是这个样子 _A1_A2_A3,然后把我们选的k种颜色(k<=n)***去然后把每种插入的颜色右边颜色都加上那种颜色。
第一个位置必须有一个颜色,这样才能保证A1不空。因为选颜色时已经排列过了,所以颜色序列也确定了。
那么剩下n-1个空,k-1种颜色就是C(n-1,k-1)。
那么答案就是singma(k(1->min(n,m))) A(m,k)C(n-1,k-1).

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int mod = 998244353;
const int maxn = 1000005;
ll inv[maxn+10];
int main()
{
    inv[1]=inv[0]=1;
    for(int i=2;i<maxn;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    int t;cin>>t;
    for(int ca=1;ca<=t;ca++)
    {
        ll n,m;cin>>n>>m;
        ll ans=0;
        ll sum=1;
        for(ll i=1;i<=min(m,n);i++)
        {
            sum=1ll*sum*((m-i+1)%mod)%mod;
            if(i>1)
            {
                sum=((1ll*sum*((n-i+1)%mod))%mod)*(inv[i-1])%mod;
            }
            ans=(ans+sum)%mod;
        }
        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}
全部评论

相关推荐

秋招进行到现在终于能写总结了。完全没想到战线会拉这么长,过程会如此狼狈,不过更应该怪自己太菜了。好在所有的运气都用在了最后,也是有个去处。背景:双2本硕科班,无竞赛,本科一段研究所实习,硕士一段大厂暑期实习但无转正。技术栈是C++&nbsp;&amp;&nbsp;Golang,实习是客户端音视频(而且是鸿蒙端开发),简历两个C++项目一个Golang项目。主要投递岗位:后端,cpp软开,游戏服务端,测开,以及一些不拘泥于Java的岗位。从8月起总共投递123家公司,笔试数不清了,约面大约30家。offer/oc/意向:友塔游戏(第一个offer,面试体验很好,就是给钱好少南瑞继保(计算机科班点击就送(限男生),不...
乡土丁真真:佬很厉害,羡慕~虽然我还没有到校招的时候,也想讲一下自己的看法:我觉得不是CPP的问题,佬的背书双2,技术栈加了GO,有两段实习。投了123,面了30.拿到11个offer。这个数据已经很耀眼了。这不也是CPP带来的吗?当然也不止是CPP。至少来说在这个方向努力过的也会有好的结果和选择。同等学历和项目选java就会有更好的吗?我个人持疑问态度。当然CPP在方向选择上确实让人头大,但是我觉得能上岸,至于最后做什么方向,在我看来并不重要。至于CPP特殊,有岗位方向的随机性,java不是不挑方向,只是没得选而已。也希望自己以后校招的时候能offer满满
点赞 评论 收藏
分享
offer多多的六边形战士很无语:看了你的博客,感觉挺不错的,可以把你的访问量和粉丝数在简历里提一下,闪光点(仅个人意见)
点赞 评论 收藏
分享
牛客737698141号:他们可以看到在线简历的。。。估计不合适直接就拒了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务