原题： ZOJ 3785 

题意：当天是星期六，问经过1^1+2^2+3^3....+n^n天后是星期几？

这题开始以为是这种式子的求和问题，翻了半天没翻到公式。结果没搞出来。后来发现有两种方法。

第一种方法： 找规律

打表可以看出，这些数的结果出现42一循环，所以直接就处理出前42个，后面的就用前面的。

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 20007int sum[44];string ss[8] = { "Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};\void init(){ int n,i,j; sum[0] = 0; for(n=1;n<=44;n++) { int flag = n%7; int ans = 1; for(j=1;j<=n;j++) ans = (ans*flag)%7; sum[n] = ans; } for(i=1;i<=44;i++) sum[i] += sum[i-1];}int main(){ int i,j,t,n,ans; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); ans = (((n/42)%7*(sum[42]%7))%7 + sum[n%42]%7)%7; cout<
            
             <
            
           
          
         
        
       
      

 

第二种方法： 矩阵乘法

先把底数对7取模，得出1^1+1^8+1^15+...+ 2^2+2^9+2^16+...

然后就可以分成7组，分别用矩阵加速计算结果，关键就在矩阵的构造了，这个构造我也没太搞懂：

    摘自AB的博客。

 

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 107char s[7][20]={
    "Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};struct Matrix{    int m[2][2];};Matrix Mul(Matrix a,Matrix b){    Matrix c;    memset(c.m,0,sizeof(c.m));    for(int i=0;i<2;i++)        for(int j=0;j<2;j++)            for(int k=0;k<2;k++)                c.m[i][j] += ((a.m[i][k]*b.m[k][j])%7 + 7)%7;    return c;}int fastm(int a,int b){    int res = 1;    while(b)    {        if(b&1)            res = (res*a)%7;        a = (a*a)%7;        b >>= 1;    }    return res;}Matrix MPow(Matrix &res,Matrix a,int n)  //第二种写法{    while(n)    {        if(n&1)            res = Mul(res,a);        n>>=1;        a = Mul(a,a);    }    return res;}int main(){    Matrix res,tmp;    int t,n,i;    int sum,num;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        sum = 0;        for(i=1;i<=7;i++)        {            res.m[0][0] = res.m[0][1] = fastm(i,i)%7;            res.m[1][0] = res.m[1][1] = 0;            tmp.m[0][0] = tmp.m[0][1] = fastm(i,7)%7;            tmp.m[1][0] = 0;            tmp.m[1][1] = 1;            num = n/7;            if(n%7 >= i)                num++;            if(num > 0)            {                num--;                MPow(res,tmp,num);                sum = (sum + res.m[0][1])%7;            }        }        printf("%s\n",s[sum]);    }    return 0;}