HDU-5351
MZL's Border
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 671 Accepted Submission(s): 209
MZL is really like Fibonacci Sequence, so she defines Fibonacci Strings in the similar way. The definition of Fibonacci Strings is given below.
1) fib1=b
2) fib2=a
3) fibi=fibi−1fibi−2, i>2
For instance, fib3=ab, fib4=aba, fib5=abaab.
Assume that a string s whose length is n is s1s2s3...sn. Then sisi+1si+2si+3...sj is called as a substring of s, which is written as s[i:j].
Assume that i<n. If s[1:i]=s[n−i+1:n], then s[1:i] is called as a Border of s. In Borders of s, the longest Border is called as s' LBorder. Moreover, s[1:i]'s LBorder is called as LBorderi.
Now you are given 2 numbers n and m. MZL wonders what LBorderm of fibn is. For the number can be very big, you should just output the number modulo 258280327(=2×317+1).
Note that 1≤T≤100, 1≤n≤103, 1≤m≤|fibn|.
Then for the following T lines, each has two positive integers n and m, whose meanings are described in the description.
/**
题意:给一个A串,一个B串,然后str[i] = str[i-1]+str[i-2];
求解对于第n个串的第前m位最长的LBorder,LBorder 是指s[1:i]=s[n−i+1:n],
做法:画几个串可以找到规律,比如第九个串
a b a a b a b a a b a a b a b a a b a b a a b a a b a b a a b a
[0] [0 1] [1 2 3] [2 3 4 5 6] [4 5 6 7 8 9 10 11] [7 8 9 10 11 12 13 14 15 16 17 18 19]
Java
**/
import java.util.*;
import java.math.*; public class Main
{
public static void main(String args[])
{
BigInteger AA[] = new BigInteger [1000+5];
BigInteger A[] = new BigInteger [1000+5];
A[1] = BigInteger.ONE;
A[2] = BigInteger.valueOf(2);
BigInteger MOD = BigInteger.valueOf(258280327);
BigInteger mm = BigInteger.valueOf(1);
for (int i = 3; i <= 1001; i++) {
A[i] = A[i-1].add(A[i-2]);
}
for(int i=2;i<=1001;i++)
{
A[i] = A[i].add(A[i-1]);
}
AA[1] = BigInteger.ZERO;
AA[2] = BigInteger.ZERO;
for(int i=3;i<=1001;i++)
{
AA[i] = AA[i-1].add(AA[i-2]).add(mm);
}
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t-- > 0)
{
int n = in.nextInt();
BigInteger m = in.nextBigInteger();
if (m.equals(BigInteger.valueOf(1)) || m.equals(BigInteger.valueOf(2)))
{
System.out.println(0);
continue;
}
boolean ok = false;
int tt = 0;
for (int i = 1; i <= 1001; i++)
{
int yy = A[i].compareTo(m);
if(yy == 1) break;
tt = i;
}
if(A[tt].compareTo(m) == 0)
{
BigInteger temp = BigInteger.ZERO;
BigInteger res = A[tt].subtract(A[tt-1]);
BigInteger tmp = AA[tt].add(res) ;
tmp = tmp.subtract(mm);
System.out.println(tmp.mod(MOD));
}
else
{
BigInteger temp = BigInteger.ZERO;
BigInteger res = m.subtract(A[tt]);
BigInteger tmp = AA[tt+1].add(res);
tmp = tmp.subtract(mm);
System.out.println(tmp.mod(MOD));
}
}
}
}
最新文章
- copy()之绝版应用
- Winform窗体用对象数组做一个小项目
- WCF自动添加消息头
- Convertion of grey code and binary 格雷码和二进制数之间的转换
- Random
- Codeforces 552C Vanya and Scales(思路)
- Java 泛型,了解这些就够用了。
- lua class(table)
- 手把手教你用C++ 写ACM自动刷题神器(冲入HDU首页)
- Java 网络编程 字符流的发送与接收 自定义数据边界
- 设置android:supportsRtl=&;quot;true&;quot;无效问题
- BZOJ 1965: [Ahoi2005]SHUFFLE 洗牌( 数论 )
- PHP做负载均衡回话保持问题参考
- 翻译 | 关键CSS和Webpack: 减少阻塞渲染的CSS的自动化解决方案
- 实用的HTML优化技巧
- 后端分布式系列:分布式存储-HDFS 与 GFS 的设计差异
- java day02 记录
- newinstance()和new有什么区别?
- 在html中做表格以及给表格设置高宽字体居中和表格线的粗细
- 29:ISBN号码
热门文章
- 数据库sharding,横向扩展
- bzoj2216: [Poi2011]Lightning Conductor(分治决策单调性优化)
- ACE_Message_Block功能简介
- ZOJ1586:QS Network (最小生成树)
- c#知识梳理
- [mysql]mysql弱密码字典检测
- 线程池 ------ linux C实现
- HDU 2154 跳舞毯 | DP | 递推 | 规律
- log4net 性能测试
- python初步学习-python数据类型之strings(字符串)