http://acm.hit.edu.cn/hoj/problem/view?id=3152
Dice
My Tags (Edit)
Source :
Time limit : sec Memory limit : M Submitted : , Accepted : 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. (<=M, N<=)
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 . Sample Input Sample Output
题目
题目说是求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了，简直屁滚尿流
代码：
#include<stdio.h>
#define MO 1000000007
long long m,n;
long long powmod(long long a,long long b)
{
long long c=;
while(b>)
{
if(b%!=)
c=c*a%MO;
a=a*a%MO;
b=b/;
}
return c;
} long long T(long long n)
{
if(n<=) return ;
long long TN2=T(n/);
if(n%==)
{
return (TN2 + powmod(m,n/) * TN2)%MO;
}
else
{
return (TN2 + powmod(m,n/) * TN2 + powmod(m,n-))%MO;
}
} int main()
{
long long ans,k;
long long i,j,t;
scanf("%lld",&t);
for(i=; i<=t; i++)
{
scanf("%lld%lld",&m,&n);
if(m==) ans=n;
else
{
ans=T(n);
}
printf("%lld\n",ans);
}
return ;
}