首页 > 代码库 > hoj3152-Dice 等比数列求和取模

hoj3152-Dice 等比数列求和取模

2024-07-09 16:15:44   223人阅读

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

DiceMy Tags      (Edit)    Source :    Time limit : 1 sec         Memory limit : 128 MSubmitted : 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 Input56 16 26 36 46 5Sample Output17432591555
题目

题目说是求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了，简直屁滚尿流

 

代码：

 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     else26     {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         else41         {42             ans=T(n);43         }44         printf("%lld\n",ans);45     }46     return 0;47 }
View Code

 


联系
我们