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

南昌网站建设一般多少钱一年公司企业网站制作

南昌网站建设一般多少钱一年,公司企业网站制作,单页网站建设平台哪个好,长沙 汽车 网站建设New Year Garland 题意 ​ 用m种颜色的球装饰n层的圣诞树,圣诞树的第i层由 l i l_{i} li​个彩球串成,且同一层相邻的球颜色不同,相邻的层之间彩球颜色的集合不同,问有多少种方案,对p取模。 分析 ​ 首先先计算每一…

New Year Garland

题意

​ 用m种颜色的球装饰n层的圣诞树,圣诞树的第i层由 l i l_{i} li个彩球串成,且同一层相邻的球颜色不同,相邻的层之间彩球颜色的集合不同,问有多少种方案,对p取模。

分析

​ 首先先计算每一层各种小球选取情况下的方案数,因为限制每层小球只有 l i l_{i} li个,且 l i ≤ 5000 l_{i} \leq 5000 li5000,所以可以预处理出 g [ l i ] [ j ] g[l_{i}][j] g[li][j]表示 l i l_{i} li个球中有 j j j种颜色时放置的方案数,递推方程就是
g [ i ] [ j ] = g [ i − 1 ] [ j − 1 ] + g [ i − 1 ] [ j ] ∗ ( j − 1 ) g[i][j]=g[i-1][j-1]+g[i-1][j]*(j-1) g[i][j]=g[i1][j1]+g[i1][j](j1)

边界是 g [ 0 ] [ 0 ] = 1 g[0][0]=1 g[0][0]=1,递推方程的意思是要么在第 i − 1 i-1 i1个球后面放一个未出现的颜色的小球,要么放一个已经出现过的颜色的小球,因为相邻颜色不同,所以有 ( j − 1 ) (j-1) (j1)种方式,第i层放j种颜色小球的放置方案数就成了
j ! ∗ ( m j ) ∗ g [ l i ] [ j ] j!*\binom{m}{j}*g[l_{i}][j] j!(jm)g[li][j]

​ 然后再考虑层与层之间的限制,假如没有这个限制的话,dp就可以写成
d p [ i ] [ j ] = j ! ∗ ( m j ) ∗ g [ l i ] [ j ] ∗ ∑ k = 1 m i n ( m , l i − 1 ) d p [ i − 1 ] [ k ] dp[i][j]=j!*\binom{m}{j}*g[l_{i}][j]*\sum_{k=1}^{min(m,\ l_{i-1})}{dp[i-1][k]} dp[i][j]=j!(jm)g[li][j]k=1min(m, li1)dp[i1][k]

加上限制后,只需要减去相同颜色集合的对应方案数即可,那就成了
d p [ i ] [ j ] = j ! ( ( m j ) ∗ g [ l i ] [ j ] ∗ ∑ k = 1 m i n ( m , l i − 1 ) d p [ i − 1 ] [ k ] − g [ l i ] [ j ] ∗ d p [ i − 1 ] [ j ] ) dp[i][j]=j!(\binom{m}{j}*g[l_{i}][j]*\sum_{k=1}^{min(m,\ l_{i-1})}{dp[i-1][k]}-g[l_{i}][j]*dp[i-1][j]) dp[i][j]=j!((jm)g[li][j]k=1min(m, li1)dp[i1][k]g[li][j]dp[i1][j])
最终的答案就是
a n s = ∑ i = 1 m i n ( m , l n ) d p [ n ] [ i ] ans = \sum_{i=1}^{min(m,\ l_{n})}{dp[n][i]} ans=i=1min(m, ln)dp[n][i]
现在思考一下能够预处理的是 g [ l i ] [ j ] g[l_{i}][j] g[li][j]以及 j ! j! j! ( m j ) \binom{m}{j} (jm)好似能预处理出来,又好似因为p不一定是素数,不一定能求逆,尝试把 j ! j! j!带入方程观察,发现 ( m j ) \binom{m}{j} (jm)就变成了 A m j A_{m}^{j} Amj,可以开心的预处理了。前面都解决了,但里面还有一个 d p [ i − 1 ] [ k ] dp[i-1][k] dp[i1][k]的求和每次都要跑满循环,再次观察能否 O ( 1 ) O(1) O(1)求出。当然一定是可以边计算边求出上一轮dp的和,所以这个值也可以 O ( 1 ) O(1) O(1)求出了。边界就是第一轮的dp的和为1。但这就结束了嘛?显然没有:(。因为 n ≤ 1000000 n \leq 1000000 n1000000导致dp数组空间巨大,此时,不难发现,该轮的dp只与上一轮的dp值有关,即好似可以滚动数组优化之类的操作,用两个数组即可完成dp过程。

AC代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int g[5010][5010], fac[5010], fac1[1000010], dp[5010], tmp[5010];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, p;cin >> n >> m >> p;vector<int> l(n + 1);for (int i = 1; i <= n; i++) {cin >> l[i];}g[0][0] = 1;for (int i = 1; i <= 5000; i++) {for (int j = 1; j <= i; j++) {g[i][j] = (g[i - 1][j - 1] + 1LL * (j - 1) * g[i - 1][j] % p) % p;}}fac[0] = 1;for (int i = 1; i <= 5000; i++) {fac[i] = 1LL * fac[i - 1] * i % p;}fac1[0] = 1;for (int i = 1; i <= m; i++) {fac1[i] = 1LL * fac1[i - 1] * (m - i + 1) % p;}LL sum = 1;for (int i = 1; i <= n; i++) {LL res = 0;for (int j = 1; j <= l[i]; j++) {tmp[j] = (1LL * fac1[j] * g[l[i]][j] % p * sum % p - 1LL * fac[j] * g[l[i]][j] % p * dp[j] % p + p) % p;res = (tmp[j] + res) % p;}sum = res;for (int j = 1; j <= l[i - 1]; j++) {dp[j] = 0;}for (int j = 1; j <= l[i]; j++) {dp[j] = tmp[j];}}cout << sum << '\n';return 0;
}
http://www.ritt.cn/news/22115.html

相关文章:

  • 湖南省做网站那个企业便宜站长统计网站
  • 做网站类型的营业执照证明如何填写百度网页版
  • 南平购物网站开发设计如何制作app软件
  • 公司找私人做网站网络广告营销方案策划
  • 张家界做网站找哪家好seo评测论坛
  • 网站策划文案健康码防疫核验一体机
  • 数字媒体艺术网站建设微博seo营销
  • 西藏网站建设公司徐州百度快照优化
  • 无锡网站维护高佣金app软件推广平台
  • wordpress文章分类设置网络优化app
  • 郑州免费自助建站模板镇江seo公司
  • 哪个网站可以兼职做效果图互联网产品推广是做什么的
  • 微信做模板下载网站什么样的人适合做策划
  • wordpress建数据库seo入门免费教程
  • 孝南区城乡建设局网站黑马程序员培训机构在哪
  • 投票制作网站网页版
  • 济南网站建设jnwuyi哪个推广网站好
  • 俄语网站建站360应用商店
  • 济南网站建设求职搜索推广渠道
  • 云适配 网站推广软件的渠道有哪些
  • 一个做BAT笔试题的网站推广普通话宣传周活动方案
  • 兰州网站建设平台分析一键优化是什么意思
  • 企业形象墙淘宝关键词排名优化技巧
  • 网络服务器故障怎么解决seo培训机构
  • 阿里云服务器搭建个人网站成品网站货源1
  • 网站url自定义竞价排名深度解析
  • 网站开发需要会的东西杭州seo按天计费
  • wordpress换域名换服务器优化网站怎么真实点击
  • 谁有wap网站谷歌关键词搜索
  • 做网站的找哪个运营推广怎么做