【HDU6198 2017 ACM ICPC Asia Regional Shenyang Online E】【找规律 + 矩阵快速幂 + 粗略证明】number number number 无法用K

本文主要是介绍【HDU6198 2017 ACM ICPC Asia Regional Shenyang Online E】【找规律 + 矩阵快速幂 + 粗略证明】number number number 无法用K,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

number number number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 235    Accepted Submission(s): 151


Problem Description
We define a sequence  F :

  F0=0,F1=1 ;
  Fn=Fn1+Fn2 (n2) .

Give you an integer  k , if a positive number  n  can be expressed by
n=Fa1+Fa2+...+Fak  where  0a1a2ak , this positive number is  mjfgood . Otherwise, this positive number is  mjfbad .
Now, give you an integer  k , you task is to find the minimal positive  mjfbad  number.
The answer may be too large. Please print the answer modulo 998244353.

Input
There are about 500 test cases, end up with EOF.
Each test case includes an integer  k  which is described above. ( 1k109 )

Output
For each case, output the minimal  mjfbad  number mod 998244353.

Sample Input
  
1

Sample Output
  
4

Source
2017 ACM/ICPC Asia Regional Shenyang Online

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1010, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int K;
int fib[N];
bitset<100010>f[24];
void table()
{fib[0] = 0; fib[1] = 1;for (int i = 2; i <= 30; ++i){fib[i] = fib[i - 1] + fib[i - 2];}f[0][0] = 1;for (int i = 0; i <= 20; ++i){for (int k = 0; k <= 30; ++k){f[i + 1] |= (f[i] << fib[k]);}for (int j = 1; j < 100000; ++j)if (!f[i][j]){printf("%d %d\n", i, j);break;}}
}
namespace FAST_MATRIX
{
#define rep(i) for(int i = 0; i < G; ++i)
#define matrix0(a) rep(i)rep(j)a[i][j] = 0;const int G = 2;int a[G][G], b[G][G], c[G][G];void mul(int a[][G], int b[][G], int c[][G]){static int tmp[G][G];matrix0(tmp);rep(i)rep(j)rep(k)tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % Z;rep(i)rep(j)c[i][j] = tmp[i][j];}void qpow(int x[][G], int y[][G], LL p){matrix0(y);rep(i)y[i][i] = 1;while (p){if (p & 1)mul(x, y, y);mul(x, x, x);p >>= 1;}}void solve(int K){matrix0(a); a[0][1] = 1;b[0][0] = 0; b[0][1] = 1;b[1][0] = 1; b[1][1] = 1;qpow(b, c, K * 2 + 3);mul(a, c, b);printf("%d\n", (b[0][0] + Z - 1) % Z);}
}
int main()
{//table();while(~scanf("%d", &K)){FAST_MATRIX::solve(K);//printf("%d\n", DU::solve(K));}return 0;
}/*
【trick&&吐槽】
找规律要不一定要盲目做,可以适当考虑结合其它数列一起做考虑。【题意】
输入一个K(1e9)范围的数,让你求出,无法用K个斐波那契数表示的最小整数。【分析】
这道题打表可以发现前几项的答案是项数		0	1	2	3	4	5	6	71	4	12	33	88	232	609但是只从这些数上找递推关系好难啊。
郑经诗这次发现规律好快呀——我们只要与斐波那契数列一起考虑就好啦!斐波那契	0	1	1	2	3	5	8	13	21	34	55	89
发现没有?ans[i] = fib[i * 2 + 3] - 1于是一个矩阵快速幂就可以解决这道题。
输入K,则求fib[K * 2 + 3]============================================================
fibonacci 矩阵
初始态a:
[0 1]
转移态b:
[0 1]
[1 1]
最终:
c = a * (b ^ (K * 2 + 3))
c.v[0][0]就是答案
============================================================
证明——
我们再考虑一下这道题的证明:
假如说,我们用K个数不构成的最小整数为X,且X = fib[x] - 1
并且有fib[x] + fib[y] = fib[z]那么现在有了第K+1个斐波那契数,我们要证明[1, fib[z] - 2]的正整数都可以构成,而fib[z] - 1恰好不行。
因为[1, fib[x] - 2]都可以构成呀,所以加上fib[y],显然[1, fib[z] - 2]都可以构成。
那么,为什么fib[z] - 1构成不了呢?1,如果选了fib[y],则因为其他K个数构不成fib[x] - 1,于是整体上无法构成fib[z] - 1
2,如果不选fib[y](即不选f[z-1]),我们发现——要至少使用K+1个数才能构成fib[z-1] - 1fib[z-1] - 1 + f[z-1] == f[z],这里至少要还要一个f[z-1],但是已经说了不取了,而f[z-1]要至少2个数,GG要至少使用K-1个数才能构成fib[z-2] - 1fib[z-2] - 1 + f[z-2]+f[z-2] == f[z],这里至少要还要两个f[z-2],但是已经说了不取了,而构成一个f[z-2]要也至少2个数,GG要至少使用K-2个数才能构成fib[z-3] - 1fib[z-3] - 1 + f[z-3]+f[z-3]+... == f[z],发现数量依然是不够的。总之,就GG了……【时间复杂度&&优化】
O(8 * log(K))*/



这篇关于【HDU6198 2017 ACM ICPC Asia Regional Shenyang Online E】【找规律 + 矩阵快速幂 + 粗略证明】number number number 无法用K的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

三国地理揭秘:为何北伐之路如此艰难,为何诸葛亮无法攻克陇右小城?

俗话说:天时不如地利,不是随便说说,诸葛亮六出祁山,连关中陇右的几座小城都攻不下来,行军山高路险,无法携带和建造攻城器械,是最难的,所以在汉中,无论从哪一方进攻,防守方都是一夫当关,万夫莫开;再加上千里运粮,根本不需要打,司马懿只需要坚守城池拼消耗就能不战而屈人之兵。 另一边,洛阳的虎牢关,一旦突破,洛阳就无险可守,这样的进军路线,才是顺势而为的用兵之道。 读历史的时候我们常常看到某一方势

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

Regionals 2004 Asia - Beijing Argus 小根堆

点击打开链接 小根堆 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokeni

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn