竞赛讨论区 > 牛客网暑期ACM多校训练营(第六场) C

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

头像
ftx456789
发布于 2018-08-05 14:06:08 APP内打开
赞 7 | 收藏 1 | 回复1 | 浏览1434
题意
你对n个集合进行n次操作,第i次操作都从第i个集合开始,每次操作可以向从i到n的集合中插入一个元素,元素范围为 ,n个集合为一个大集合,问你有多少个不同的大集合
思路
我们以n=4,m=4为例,先举一个4,4的两个集合


我们现在只看第n层,两个不同的集合的最后一层的元素都含有1,2,3,但是这两个集合是不同的两个集合,原因是数字出现的顺序会影响上一层的集合,所以最后一层元素的顺序是影响总的个数的,那么我们假设第n层由k个元素,方案数就是相当于从m个数中选k个数的排列数,即 ,选定好这k个数后,答案还不是 ,因为由于他可以插重复的元素,而重复的元素只与其他第一次出现有关,例如


这里是两个不同的集合,而不同的原因是来自于,2出现的位置,由于第一个元素是固定的如
1,1,1,2,1,2{1,2},1,1,2,1,1,2{1,2},第一个出现的数会把第二个出现的数的前面都填满,而第二个出现的数才对答案有贡献,所以就相当于在n-1个位置上填k-1个数即 ,那么答案就应该是 ,如何k从1枚举到min(n,m),即

n和m都比较大,但两者肯定有一个较小,所以最多只用算1e 6个数组合和排列数最多也只有算 ,所以多处理一个1到1e6的逆元就可以了
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
const long long mod=998244353;
const int N=1e6+5;
long long inv[N];
int main()
{
    inv[0]=inv[1]=1;
    for(int i=2; i<N; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        long long n,m;
        scanf("%lld%lld",&n,&m);
        long long ans=m%mod,sum=m%mod;
        long long m_=m%mod,n_=n%mod;
        for(int i=1; i<min(n,m); i++)
        {
            sum=sum*(m_-i)%mod*(n_-i)%mod*inv[i]%mod;
            ans=(ans+sum)%mod;
        }
        printf("Case #%d: %lld\n",cas++,(ans+mod)%mod);
    }
    return 0;
}

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐