第9题
描述
有一个整数数列，第一项是a，以后的每一项都是前一项乘以b再加c的结果，求数列第m项的后两位数字（即十位数和个位数）
输入
一个正整数n，表示有n组测试案例。
每组案例由4个正整数a、b、c、m组成（a、b、c均小于1e+7，m小于1e+9）
输出
针对每组案例，输出一个整数，表示数列第m项的后两位数字。
每组案例输出完都要换行。
样例输入
1
12 3 5 3
样例输出
28
思路
用dzt都会写的“朴实无华”方法可以通过大概40~50%的数据，但暴力方法要拿到AC必定会遇到黄色超时的阻挠
既然一般的方法又不行，那我们就再看看二般的方法
回到计算机底层对数字处理的方式，我们可以知道，当我们输入一个10进制数字，计算机虽然执行指令时还是需要执行2进制指令，具体的次数则由我们对循环的定义进行
举个例子，当我们定义一个for循环时，如果我们让他循环10次，那么计算机也就是按序循环10次，但如果我们通过一些已知的原则或是规律，就能从根源上起到“不用循环到10次”的效果
这里就需要介绍一下一种叫做“快速幂”的算法，众所周知，7的10次方可以表示为10个7相乘。这里如果我们按着这个表述去实现我们的程序，那么这个程序就需要执行10次7的相乘。但如果我们知道，7的10次方可以表示为7的平方和7的5次方相乘，那么我们的循环次数就是2+5=7次，这样我们就可以不用循环10次也能够得到正确的结果.以此类推的，我们可以尽可能想出执行次数少的方法来得到正确结果。而这一思想的宗旨就是去拼凑出“大底数小指数”的组合。
我们将这种方法和位运算结合，就可以得到以超大值m为幂的值的结果。为什么呢？如果你知道2进制与10进制的转换方式，其实很简单，当m每次右移1时，如果该位是1，那么计数器ans就乘上b的该位次序的次方。而根据int的性质，我们可以知道，这样的计算方法将计算次数压缩成小到极致的小于等于32次。
下面我们再来分析一下数学公式。
原始代数式是（…（（（a_b+c）_b+c）b+c）…b+c）
经过展开后可以得到a_b^（m-1）+c（从1到b^（m-1）的等比数列）
首先，我们可以根据上面的方法算出a_b^（m-1）的值，接着再通过等比数列的数学性质来解决后面的值，也就是1+b+b^2+b^3+…b^（m-1）=（1+b^（（m-1）/2））（1+b+b^2+b^3+…b^（（m-1）/2））.【如果m是奇数，那么就会有偶数项，所有前面m-1就要改成m-2，再在最后加个b^（m-1）】
不废话，下面上代码
代码
[Forlogin]
#include <bitset>
using namespace std;
typedef long long ll;
int MOD=10000;
ll quick(ll a,ll b)
{
ll ans=1;
a%=MOD;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans%MOD;
}
ll sum1(ll a,ll b)
{
if(b==0) return 1;
if(a==0) return 0;
if(b&1)
return ((1+quick(a,b/2+1)) * sum1(a,b/2))%MOD;
else
return ((1+quick(a,b/2+1)) * sum1(a,b/2-1) + quick(a,b/2))%MOD;
}
int main(){
int n;
scanf("%d",&n);
while (n--){
ll a,b,c,m,num;
scanf("%lld%lld%lld%lld",&a,&b,&c,&m);
if (m==1)printf("%lld\n",a%100);
else {
num=((a* quick(b,m-1))+c*(sum1(b,m-2)))%100;
printf("%lld\n",num);
}
}
return 0;
}[/Forlogin]