XTU 1238 Binary String

2023-12-15 17:59
文章标签 string binary xtu 1238

本文主要是介绍XTU 1238 Binary String,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Binary String

[ Submit Code ] [ Top 20 Runs ]
Acceteped : 31   Submit : 45
Time Limit : 1000 MS Memory Limit : 65536 KB
 

Description

题目描述

求n位01串含连续至少2个1的串的个数。

输入

第一行是一个整数K(K≤10000),表示样例的个数。 每行样例是一个整数n(1≤1000000)。

输出

每行输出一个样例的结果,因为数目可能很大,请对109+7取模。

样例输入
5
1
2
3
4
1000000
样例输出
0
1
3
8
782550144
 

Sample Input

 

Sample Output

 

Source

 
[ Submit Code ] [ Top 20 Runs ]


思路:递推。考虑i位时,设f[i]为结果,那么显然可知,i位是在i-1位的基础上,由最高位加0和加1形成,加0结果就为f[i-1],加1分两种情况:一种是i-1位的最高位为0,结果显然是f[i-2];另一种是最高位为1,那么加1肯定至少有两个1连续,结果必为i-1位二进制总数的一半,即2^(i-2)。所以得到递推式f[i]=f[i-1]+f[i-2]+2^(i-2)。先预处理一下,然后直接输出即可(节约时间)。详见代码。

AC代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000005;
const int mod = 1000000007;
int f[maxn], dp[maxn];
int n;void init(){dp[1] = 1;for (int i=2; i<maxn; ++i)dp[i] = 2ll*dp[i-1]%mod;f[2] = 1;for (int i=3; i<maxn; ++i)f[i] = (1ll*f[i-1]+f[i-2]+dp[i-1])%mod;
}int main(){ios::sync_with_stdio(false);cin.tie(0);init();int T;cin >> T;while (T--){cin >> n;cout << f[n] << endl;}return 0;
}

这篇关于XTU 1238 Binary String的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/497348

相关文章

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

hdu2072(string的应用)

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25447    Accepted Submission(s): 5957 Problem Description lily的好朋友xiaoou333最近很空,他

【UVA】10739 - String to Palindrome(动态规划)

比较水的动态规划 dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数 其中删除操作和添加操作本质上是一样的。 三个状态转移方程: dp[i][j] = min(dp[i][j] ,dp[i + 1][j]); dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]); dp[i][j] = min(dp[i][j] ,dp[

理解String的compareTo()方法返回值

compareTo()的返回值是整型,它是先比较对应字符的大小(ASCII码顺序), 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值。 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符作比较, 以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度。 我们可以通过阅读源码加深对compareTo()的理解: comp

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

leetcode#541. Reverse String II

题目 Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of