原题: ZOJ 3785 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3785
题意:当天是星期六,问经过1^1+2^2+3^3....+n^n天后是星期几?
这题开始以为是这种式子的求和问题,翻了半天没翻到公式。结果没搞出来。后来发现有两种方法。
第一种方法: 找规律
打表可以看出,这些数的结果出现42一循环,所以直接就处理出前42个,后面的就用前面的。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <string> using namespace std; #define N 20007 int 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<<ss[ans]<<endl; } return 0; }
第二种方法: 矩阵乘法
先把底数对7取模,得出1^1+1^8+1^15+...+ 2^2+2^9+2^16+...
然后就可以分成7组,分别用矩阵加速计算结果,关键就在矩阵的构造了,这个构造我也没太搞懂:
摘自AB的博客。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 107 char 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; }