baidu A

题意:
求序列头尾为1的情况,中间n-1个数填充小于等于m的序列的个数

解题思路:
我们考虑DP[N]的情况,
比如{1a1a2....an-11}
那么对于从{a1 到 an-2}我们都有m-1种选择,即
那么对于{an-1}而言,
我们可能有m-1种选择(即它的前一位为1,最后尾也是1),
也可能是m-2种选择(即它的前一位不为1,最后尾是1)
那么我们先让他乘以(m-2),
那么少算的地方在哪里呢?当然是漏掉了前一位为1,最后尾也为1的这个情况
也就是{1a1a2...an-31an-11}
而这时候的{an-1}我们实际上已经遍历了m-2种情况,只剩下一种
自然也就剩下了{1a1a2...an-31}这种情况了,是不是发现了DP公式了?
那么我们可以写出DP公式:
DPn=m-1n-2*(m-2)+DPn-2
等比数列求和就行了
因为N非常大,所以要用nlogn的方法求等比

代码:
const int MO = 1000000007;
long long m, n;
long long powmod(long long a, long long b)
{
long long c = 1;
while (b>0)
{
if (b % 2 != 0)
c = c*a%MO;
a = a*a%MO;
b = b / 2;
}
return c;
}
long long T(long long m, long long n)
{
if (n <= 1) return 1;
long long TN2 = T(m, n / 2);
if (n % 2 == 0)
{
return (TN2 + powmod(m, n / 2) * TN2) % MO;
}
else
{
return (TN2 + powmod(m, n / 2) * TN2 + powmod(m, n - 1)) % MO;
}
}
int main(){
while (cin >> n >> m) {
if (n == 1) {
cout << "1" << endl;
}
else if (n == 2) {
if (m > 1)
cout << "1" << endl;
else
cout << "0" << endl;
}else{
if (m >= 2) {
ll ans = m - 2;
ll a = (m - 1) * (m - 1);
ll nn = (n - 1) / 2;
ans = T(a, nn);
if (n % 2 == 1)
cout << ans * (m - 1) % MO * (m - 2) % MO << endl;
else
cout << ans * (m - 2) % MO << endl;
//cout << sum(a, nn) << endl;
}
else
cout << "0" << endl;
}
}
return 0;
}
#百度#
全部评论
是这个思路,就是写不出来。。。
点赞 回复 分享
发布于 2018-09-12 10:05
楼主你的题意表述有问题吧,表示看不懂
点赞 回复 分享
发布于 2018-09-12 09:59
由于N非常的大,这个DP你不能直接for一圈,要求出等比通项公式,然后求和,得到答案的方法有两种: 1)直接等比求和公式,然后求逆元做出来 2)二分等比 我是用的二分等比
点赞 回复 分享
发布于 2018-09-11 22:32
s(n) = s(n-1)*(m-2)+s(n-2)*(m-1);  这是普通的通项公式
点赞 回复 分享
发布于 2018-09-11 22:22
请问你投的什么岗位c++么?
点赞 回复 分享
发布于 2018-09-11 22:13
这是我的思路,希望大佬们多多指正。。。
点赞 回复 分享
发布于 2018-09-11 22:12

相关推荐

2025-12-10 14:51
门头沟学院 Java
点赞 评论 收藏
分享
2025-12-24 15:25
已编辑
门头沟学院 前端工程师
是腾讯的csig腾讯云,前天晚上九点突然打电话约面,激动的通宵学了一晚上,第二天状态很差改了今天(以后再也不通宵学习了)感觉自己浪费了面试官一个半小时单纯手写+场景,无八股无项目无算法,打击真的很大,全是在面试官提醒的情况下完成的,自己技术方面真的还是有待提高,实力匹配不上大厂和已经面试的两个公司完全不一样,很注重编码能力和解决问题的能力,然而我这两个方面都很薄弱,面试官人很好很耐心的等我写完题目,遇到瓶颈也会提醒我,写不出题也会很耐心的跟我讲解好感动,到最后面试结束还安慰我打算把下周最后一场面试面完之后就不面啦,如果能去实习还是很开心,但是最重要的还是好好努力提高技术以下是面经第一题//&nbsp;实现一个解析&nbsp;url&nbsp;参数的函数function&nbsp;parseUrl(urlStr)&nbsp;{//&nbsp;TODO}parseUrl('*********************************************');//&nbsp;返回&nbsp;{a:&nbsp;1,&nbsp;b:&nbsp;2,&nbsp;c:&nbsp;3}追问:在链接里见过什么部分?用&nbsp;hash&nbsp;路由的话放在哪第二题//&nbsp;考虑有一个异步任务要执行,返回&nbsp;Promise,这个任务可能会失败,请实现&nbsp;retry&nbsp;方法,返回新方法,可以在失败后自动重试指定的次数。/***&nbsp;异步任务重试*&nbsp;@param&nbsp;task&nbsp;要执行的异步任务*&nbsp;@param&nbsp;times&nbsp;需要重试的次数,默认为&nbsp;3&nbsp;次*/function&nbsp;retry(task,&nbsp;times&nbsp;=&nbsp;3)&nbsp;{//&nbsp;TODO:&nbsp;请实现}//&nbsp;---------------测试示例&nbsp;----------------//&nbsp;原方法const&nbsp;request&nbsp;=&nbsp;async&nbsp;(data)&nbsp;=&gt;&nbsp;{//&nbsp;模拟失败if&nbsp;(Math.random()&nbsp;&lt;&nbsp;0.7)&nbsp;{throw&nbsp;new&nbsp;Error('request&nbsp;failed');}const&nbsp;res&nbsp;=&nbsp;await&nbsp;fetch(&#39;https://jsonplaceholder.typicode.com/posts&#39;,&nbsp;{method:&nbsp;'POST',body:&nbsp;JSON.stringify(data),});return&nbsp;res.json();}//&nbsp;新的方法const&nbsp;requestWithRetry&nbsp;=&nbsp;retry(request);//&nbsp;使用async&nbsp;function&nbsp;run()&nbsp;{const&nbsp;res&nbsp;=&nbsp;await&nbsp;requestWithRetry({&nbsp;body:&nbsp;'content'&nbsp;});console.log(res);}run();第三题就是给&nbsp;retry&nbsp;函数添加类型注释,用到泛型第四题:在组件库中将&nbsp;Alert&nbsp;用&nbsp;api&nbsp;的形式实现(应该就是&nbsp;message&nbsp;这个组件)怎么渲染到一个浮层里而不是原地渲染出来
不知道怎么取名字_:技术这个东西,太杂了,而且要下功夫的
查看5道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务