HDU 6050 Funny Function （规律+逆元）

HDU 6050 Funny Function （规律+逆元）

Description

Function Fx,yF1,1=F1,2=1F1,i=F1,i−1+2∗F1,i−2 (i>=3)Fi,j=∑j+N−1k=jFi−1,k (i>=2,j>=1)For given integers N and M,calculate Fm,1

Input

There is one integer T in the first line.The next T lines,each line includes two integers N and M .1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

Sample Input

22 23 3

Sample Output

233

题意

给出 n , m 的值，求 Fm,1 mod 1e9+7 。

思路

先看数据范围： 1<=N,M<263

所以最终的结果一定是有规律，并且可以通过公式计算出来的。

先打表看看

// 当 n = 2 时1 1 3 5 11 21 43 85 171 3412 4 8 16 32 64 128 256 512 10246 12 24 48 96 192 384 768 1536 307218 36 72 144 288 576 1152 2304 4608 921654 108 216 432 864 1728 3456 6912 13824 27648162 324 648 1296 2592 5184 10368 20736 41472 82944486 972 1944 3888 7776 15552 31104 62208 124416 2488321458 2916 5832 11664 23328 46656 93312 186624 373248 7464964374 8748 17496 34992 69984 139968 279936 559872 1119744 2239488// 当 n = 3 时1 1 3 5 11 21 43 85 171 3415 9 19 37 75 149 299 597 1195 238933 65 131 261 523 1045 2091 4181 8363 16725229 457 915 1829 3659 7317 14635 29269 58539 1170771601 3201 6403 12805 25611 51221 102443 204885 409771 81954111205 22409 44819 89637 179275 358549 717099 1434197 2868395 573678978433 156865 313731 627461 1254923 2509845 5019691 10039381 20078763 40157525549029 1098057 2196115 4392229 8784459 17568917 35137835 70275669 140551339 2811026773843201 7686401 15372803 30745605 61491211 122982421 245964843 491929685 983859371 1967718741

首先可以明确的是 F1,1=1

我们来看当 n 为偶数的情况，第一列即 Fm,1 ，发现它们之间存在倍数 3 的关系（除第二行以外），读者可以自己写程序测试其他数据，最终发现这个倍数刚好是 2n−1 ，于是对于偶数， Fm,1=F2,1×(2n−1)m−2

然后我们来看当 n 为奇数的情况，还照之前的做法我们把相邻的两项相除，可以发现这个值无限趋近于 2n−1 ，于是想到会不会相差某一个数字呢，然后计算 Fm−1,1×(2n−1)−Fm,1

当 n=3..5..7..9 时，该常数为： 2..10..42..170

答案当然是有啦~

2=21

10=21+23

42=21+23+25

170=21+23+25+27

也就是公比为 22 的等比数列前 k 项和，公式： Sk=a1(1−qk)1−q ，其中 q=22,a1=2,k=n2

我们设 cha 为刚刚我们所求得的差， F2,1 已知、 2n−1 已知，然后我们如何通过这三者得到 Fm,1

F3,1=F2,1×(2n−1)−cha

F4,1=F3,1×(2n−1)−cha=F2,1×(2n−1)2−cha×(2n−1)−cha

F5,1=F4,1×(2n−1)−cha=F2,1×(2n−1)3−cha×(2n−1)2−cha×(2n−1)−cha

…

Fm,1=Fm−1,1×(2n−1)−cha=F2,1×(2n−1)m−2−cha×(2n−1)m−3...−cha

显然，后面的 cha×(2n−1)m−3+cha×(2n−1)m−2...+cha×(2n−1)+cha 又是一个公比为 2n−1 的等比数列前 k 项和，同样我们可以代入公式求得，我们设其为 add

于是，最终的结果便为： Fm,1=F2,1×(2n−1)m−2−add

此时，整个式子中的未知量只有 F2,1

同样也有规律的，先打表看看~

S[i]: 1 2 5 10 21 42 85 170 341 682 1365 2730 5461 10922 21845 43690 87381 174762 349525F[i]: 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763 349525

Si 代表 F1,i 的前 i 项和，将 S

当 i 为奇数时 Si=Fi+1 ，否则 Si=Fi+1−1

因此我们只需要计算 Fi+1 便可以得到 Si ，而 F1,i+1=(−1)i+2i+13

然后整个问题便可以求解啦~

注意：因为是取模运算，因此在计算中一切除法全部用乘法逆元来代替，记得随时取模以防溢出。

AC 代码

#include #include #include #include #include #includeusing namespace std;typedef __int64 LL;const int mod = 1e9+7;LL n,m;LL mult(LL a,LL n){ LL ans=1; while(n) { if(n&1)ans=(ans*a)%mod; a=(a*a)%mod; n>>=1; } return ans;}void solve(){ if(m==1) { cout<<"1"<>T; while(T--) { cin>>n>>m; solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。