当前位置: 首页 > news >正文

宜宾市住房和城乡建设局网站网站推广优化外包公司

宜宾市住房和城乡建设局网站,网站推广优化外包公司,易加网站建设方案,门户网站价格Problem - H - Codeforces 题意&#xff1a; 定义一个集合S为T的孩子是&#xff0c;对于S中的每一个元素x&#xff0c;在T中都能找到x1。 给定n&#xff0c;k&#xff0c;每一个集合中的元素x必须满足 1 < x < k 1<x<k 1<x<k且 c n t [ x ] < 1 cnt[x…

Problem - H - Codeforces

题意:

定义一个集合S为T的孩子是,对于S中的每一个元素x,在T中都能找到x+1。
给定n,k,每一个集合中的元素x必须满足 1 < = x < = k 1<=x<=k 1<=x<=k c n t [ x ] < = 1 cnt[x]<=1 cnt[x]<=1,若n个集合重排后对于 1 < i < = n 1<i<=n 1<i<=n都可以满足 S i − 1 S_{i-1} Si1 S i S_i Si的孩子,则该n个集合是一个合法序列,求所有合法序列的个数。

思路:

定义 f [ i ] f[i] f[i]为最后一个集合中若 i i i存在,只看 i i i的贡献(可以构成合法的之前集合的总个数)。
f [ 1 ] = 1 , f [ i ] = f [ i − 1 ] + 1 f[1]=1,f[i]=f[i-1]+1 f[1]=1,f[i]=f[i1]+1,因为最后一个集合里,1只能是自己冒出来的不能是由前面变来的,之后每一个数都可以是自己冒出来的(贡献为1),也可以是将使集合中出现i-1的那个位置上的数提前出现一位,导致原来的i-1变成现在的i。由于最后一个集合中出现每一个数都是独立的,所以可以用乘法原理算得每种情况,求出 p r e [ i ] pre[i] pre[i]表示至少有n-i个空集的集合有多少情况。

AC代码:
#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod = 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll N = 2e5+50;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
int fac[N],inv[N];ll qp(ll a,ll b){ll ans=1;a%=mod;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}void init(){fac[0]=fac[1]=inv[0]=inv[1]=1;for(int i=2;i<=N;++i){fac[i]=1ll*fac[i-1]*i%mod;  //阶乘inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;  //逆元}for(int i=2;i<=N;++i){inv[i]=1ll*inv[i]*inv[i-1]%mod;}
}void work() {init();int n,k;cin>>n>>k;ll ans=0;for(int i=1;i<=min(n,k);++i){ll res=(fac[i+1]*qp(i+1,k-i)%mod-fac[i]*qp(i,k-i+1)%mod+mod)%mod;//至少有n-(i+1)个空集-至少有n-i个空集ans=(ans+res*fac[n]%mod*inv[n-i]%mod)%mod;//恰有n-i个空集的情况}ans++;cout<<ans<<'\n';
}signed main() {io;int t=1;//cin >> t;while (t--) {work();}return 0;
}
http://www.15wanjia.com/news/37786.html

相关文章:

  • 一个seo良好的网站其主要流量往往来自百度推广seo
  • 宝和网站建设5118数据分析平台
  • web前端发展前景做seo排名
  • 委托做的网站版权归属哪方社群运营的经典案例
  • 哪里提供邢台做网站网络营销教学大纲
  • 做网站后台需要写代码吗关键词排名推广公司
  • 知名的政府网站建设公司指数基金定投技巧
  • 郑州网站优化公司哪家好seo和sem
  • 做婚恋网站的思路网文网站排名
  • 做家装模型的效果图网站餐饮店如何引流与推广
  • 网站制作工作室百度竞价排名正确解释
  • 网站开发设计过程百度问答平台
  • 文创产品设计大赛作品长沙建站优化
  • 菠菜网站开发csjylw软广告经典例子
  • 彩票网站做任务赚钱设计网站的公司
  • 免费的微网站制作平台百度网盘官方下载
  • 做网站 php和javanba排名西部和东部
  • 网站建站及维护企业网站建设论文
  • 衡水龙华的网站建设色盲测试图第六版
  • 玻璃钢产品哪个网站做推广好郑州网络营销与网站推广
  • 北京住房和城乡建设委员会网站公告迅雷磁力
  • 禁止显示网站目录网站引流推广
  • js网站评论框热搜词工具
  • 广州定制网站设搜索引擎搜索器
  • 怎样做网站服务器什么推广软件效果好
  • 有做网站代理运营的吗小学生简短小新闻十条
  • 做金融行业网站app推广接单
  • 做盗版电影网站问题win7系统优化
  • 青岛网站建设平台数字营销软件
  • 杭州建平台网站公司南昌seo优化公司