首页 > 其他 > 详细

hoj3152-Dice 等比数列求和取模

时间:2014-06-26 14:55:33      阅读:438      评论:0      收藏:0      [点我收藏+]

http://acm.hit.edu.cn/hoj/problem/view?id=3152

bubuko.com,布布扣
Dice
My Tags      (Edit)
    Source :
    Time limit : 1 sec         Memory limit : 128 M

Submitted : 82, Accepted : 18

    You have a dice with M faces, each face contains a distinct number.

    Your task is to calculate the expected number of tosses until a number facing up for consecutive N times.

    We assume when we tossing the dice, each face will occur randomly and uniformly.
Input

  Each test cases contains only one line with two integers M, N. (1<=M, N<=100000000)
Output

   For each test case, display a single line with the answer to the question above, the answer maybe very large, you need to MOD it with  1000000007.

Sample Input

5
6 1
6 2
6 3
6 4
6 5


Sample Output

1
7
43
259
1555
题目

题目说是求M面骰子投出N次相同点数所需要投的次数的期望值,看样例可以知道其实是求1+M+M^2+.......+M^(N-1),等比数列求和取模!

这个好像是某次校赛的题,当时我是直接等比数列慢慢加起来,没用等比数列求和公式,就得了。不过现在这题数据好像加强了…不能这样撸啦!而等比数列求和公式又有除法,不好搞取模。于是我也不会了。

然后我找到了一个叫kk303的人写的这个题解:

http://blog.csdn.net/kk303/article/details/9332513

虽然还是不太懂为什么不过得到了超碉的公式:

求等比为k的等比数列之和T[n]..当n为偶数..T[n] = T[n/2] + pow(k,n/2) * T[n/2]

                                            n为奇数...T[n] = T[n/2] + pow(k,n/2) * T[n/2] + 等比数列第n个数的值

    比如 1+2+4+8 = (1+2) + 4*(1+2) 

     1+2+4+8+16 = (1+2) + 4*(1+2) + 16 

哇,终于A了,简直屁滚尿流

 

代码:

bubuko.com,布布扣
 1 #include<stdio.h>
 2 #define MO 1000000007
 3 long long m,n;
 4 long long powmod(long long a,long long b)
 5 {
 6     long long c=1;
 7     while(b>0)
 8     {
 9         if(b%2!=0)
10             c=c*a%MO;
11         a=a*a%MO;
12         b=b/2;
13     }
14     return c;
15 }
16 
17 long long T(long long n)
18 {
19     if(n<=1) return 1;
20     long long TN2=T(n/2);
21     if(n%2==0)
22     {
23         return (TN2 + powmod(m,n/2) * TN2)%MO;
24     }
25     else
26     {
27         return (TN2 + powmod(m,n/2) * TN2 + powmod(m,n-1))%MO;
28     }
29 }
30 
31 int main()
32 {
33     long long ans,k;
34     long long i,j,t;
35     scanf("%lld",&t);
36     for(i=1; i<=t; i++)
37     {
38         scanf("%lld%lld",&m,&n);
39         if(m==1) ans=n;
40         else
41         {
42             ans=T(n);
43         }
44         printf("%lld\n",ans);
45     }
46     return 0;
47 }
View Code

 

hoj3152-Dice 等比数列求和取模,布布扣,bubuko.com

hoj3152-Dice 等比数列求和取模

原文:http://www.cnblogs.com/yuiffy/p/3809176.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!