NOI2013

最近做一下历年真题，写一些题解吧。

Day2T1

这是这年六道题里最水的一道，不过也没有1A，真是太弱了。

很容易由递推公式推出来通项公式，令

[tex]p = a^{m-1},\\r = \frac{a^{m-1}-1}{a-1}*b[/tex]

则有

[tex]f[i][m] = p*f[i][1]+r,\\f[i][1] = c*p*f[i-1][1]+c*r+d (i \ne 1)[/tex]

注意到此时已经推出来了第一列的递推公式，再依据每一行的递推公式，很容易得到每个数的通项公式，这里不再赘述，请看官自行推导。可是看一下数据就会发现，n，m的值很大最多有1000000位，这里我们采用一种类似于费马小定理的方法进行加速。下面具体来说，

费马小定理：

[tex]a^{\varphi(p)} \equiv 1 \pmod{p}[/tex]

注意到，当

[tex]m = base - 1[/tex]

时，[tex]p = 1[/tex],所以当[tex]m \leftarrow m \,\bmod\,\ (base - 1)[/tex]时，对答案无任何影响，对n同理。由此我们将原问题等价为[tex]n,m < base[/tex]的简单问题，结合我上面的公式即可写出程序。

注意：1.当a或c为1，时上面的公式会出现错误，请看官自行解决这个问题，我就是因为这个没有1A的。

     2.除以(a-1)时采用逆元，具体方法见我之前的博文 OI数论总结

代码

#include<cstdio>
#include<cstring>
#define base 1000000007
#define dec(x) ((x - 1 + base) % base)
int n,nn,m,mm,a,b,c,d,p,r,p1,r1,p2,r2,x,n1,m1;
int getint(int &n){
    int ret = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while('0' <= c && c <= '9') ret = ((long long)ret * 10LL + (long long)(c - '0')) % (long long)(base-1), n = ((long long)n * 10LL + (long long)(c - '0')) % (long long)(base), c = getchar();
    return ret;
}
int MultiMod(int a,int b,int p){//a*b % p
    int ret = 0,m = a;
    while(b){
        if(b & 1) ret = (ret + m) % p;
        m = (m + m) % p;
        b >>= 1;
        }
    return ret;
}     
int PowerMod(int a,int b,int p){//a^b % p
    int ret = 1,m = a;
    while(b){
        if(b & 1) ret = (long long)ret*(long long)m%(long long)p;
        m = (long long)m*(long long)m%(long long)p;
        b >>= 1;
        }
    return ret;
}
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    n = getint(n1),m = getint(m1);
    nn = dec(n),mm = dec(m);
    scanf("%d%d%d%d",&a,&b,&c,&d);
    p = PowerMod(a,mm,base);
    r = MultiMod(MultiMod(dec(p),PowerMod(a-1,base-2,base),base),b,base);
    if(a == 1) r = MultiMod(dec(m1),b,base);
    p1 = MultiMod(c,p,base);
    r1 = (MultiMod(c,r,base) + d) % base;
    p2 = PowerMod(p1,nn,base);
    r2 = MultiMod(MultiMod(dec(p2),PowerMod(p1-1,base-2,base),base),r1,base);
    if(p1 == 1) r2 = MultiMod(dec(n1),r1,base);
    x = (p2+r2) % base;
    x = (MultiMod(p,x,base)+r) % base;
    printf("%d\n",x);
    return 0;
}