程序地带

牛客练习赛76 CG的通关秘籍 数学


链接:https://ac.nowcoder.com/acm/contest/10845/C 来源:牛客网


题目描述 CG最喜欢玩的就是拼图游戏,但是他已经通关了所有拼图游戏,感觉拼图游戏已经没有了任何的乐趣。所以今天他选择玩填数游戏。


CG每次填一个的数到当前位置,如果这个位置填的数比上一次填的数要大,形成顺序,他的兴奋度会增加1点,如果这个数比上一次填的数要小,形成逆序,他的兴奋度会增加2点,如果两个数相等,那么什么都不会发生。(如果是第一次填数,同样不会发生任何事情)


CG认为如果已知他n次填的数,计算出当他填了n个数之后的兴奋度太简单了,所以想要你帮他计算一下他所有填数方案的兴奋度之和。


由于这个结果过大,将这个结果模1e9+7 题解:




f
(
n
)



n









,





:
不妨假设f(n)为填了n位数后的兴奋度之和,考虑递推有:
不妨假设f(n)为填了n位数后的兴奋度之和,考虑递推有:
f
(
n
)
=
m

f
(
n

1
)
+
m
n

2

3

m

(
m

1
)
2
f(n)=m*f(n-1)+m^{n-2}*frac{3*m*(m-1)}{2}
f(n)=m∗f(n−1)+mn−2∗23∗m∗(m−1)​



f
(
n

1
)



f
(
n
)
,

n

1







m







k

[
1
,
m
]
,






k

1





m

k









3
m
(
m

1
)
2
,



n

1

n

m
n

2












首先从f(n-1)转移到f(n),第n-1位上的都要复制m遍, 对于每一个k∈[1,m],向后转移时有k-1个比他小,m-k个比他大,求和可得frac{3m(m-1)}{2},而从第n-1到n有m^{n-2}条路径,根据乘法原理可得
首先从f(n−1)转移到f(n),第n−1位上的都要复制m遍,对于每一个k∈[1,m],向后转移时有k−1个比他小,m−k个比他大,求和可得23m(m−1)​,而从第n−1到n有mn−2条路径,根据乘法原理可得













:
f
(
n
)
=
3
(
n

1
)
(
m

1
)
m
n

1
2
我们可通过待定系数法求通项:f(n)=frac{3(n-1)(m-1)m^{n-1}}{2}
我们可通过待定系数法求通项:f(n)=23(n−1)(m−1)mn−1​


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll n,m;
int cas;
ll pow_mod(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%M;
b>>=1;a=a*a%M;
}
return ans;
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%lld%lld",&n,&m);
//ll a1=3*(n-1)*(m-1)%M;
//ll a2=pow_mod(m,n-1)*pow_mod(2,M-2);
ll ans=((3*(n-1)*(m-1)%M)*pow_mod(m,n-1)%M)*pow_mod(2,M-2);
printf("%lld ",ans%M);
}
return 0;
}

伞b的我把快速幂写错了


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39689721/article/details/112689342

随机推荐

资源过于硬核,8h删!这波福利....请笑纳~

资源过于硬核,8h删!这波福利....请笑纳~

一直以来我经常听到很多粉丝反馈,觉得人工智能是目前最牛X的技术,想要尝试自学入行,将自己的一些想法和创意付诸现实。但大部分人苦于不知从何入手,往...

zenRRan 阅读(662)

Myeclipse 打开卡死白屏解决办法

Myeclipse启动后随便点一下就停止响应了。解决办法如下:找到Myeclipse安装目录下configuration文件夹,一个名为org.eclipse.osgi的文...

yura. 阅读(344)

TJ Wi-Fi不能使用的解决的办法

TJ Wi-Fi不能使用的解决的办法

TJWi-Fi不能使用的解决的办法发现最近有好的同学不能使用TjWi-Fi,包括我,我前段时间在使用我的本科账户,最近也不能使用了,经过与网络中...

Mr.Talpen 阅读(355)

送50本Android畅销书,手慢无!

送50本Android畅销书,手慢无!

经常在后台收到一些小伙伴询问:Android开发,有哪些较好的书单推荐?刚好到年底了,为了感谢大家一直以来的支持,不仅给你们推荐书...

公众号码个蛋 阅读(423)

自定义View——圆环进度条RingProgressBar

自定义View——圆环进度条RingProgressBar

 话不多说先上效果图非常简单的一个圆环进度条主要有以下主要功能1.支持中间文字的显示隐藏,修改样式2.支持自定义进度条背景的颜色宽度以及进度条的颜色宽度3.支持开启关闭动画效果4.支持自...

人生~海海 阅读(136)

2020-12-24

2020-12-24

耿国华数据结构第二版,中序遍历二叉树算法初步为什么L1中可以出现L2...

m0_53386844 阅读(693)