【ZOJ】3785 What day is that day? ——KMP 暴力打表找规律

转自：http://www.cnblogs.com/kevince/p/3887827.html

首先声明一下，这里的规律指的是循环，即找到最小循环周期。

这么一说大家心里肯定有数了吧，“不就是next数组性质的应用嘛”，没错，正是如此。

在ACM的比赛中有些时候会遇到一些题目，可以或必须通过找出数据的规律来编写代码，这里我们专门来讨论下如何运用KMP中next数组的性质来寻找一个长数组中的最小循环周期。

先来看一道题

ZOJ 3785

What day is that day?

Time Limit: 2 Seconds Memory Limit: 65536 KB

It's Saturday today, what day is it after 1¹ + 2² + 3³ + ... + N^N days?

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is only one line containing one integer N (1 <= N <= 1000000000).

Output

For each test case, output one string indicating the day of week.

Sample Input

Sample Output

Sunday

Thursday

Hint

A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

题目的大意是知道今天是周六，让你求 f = 1¹ + 2² + 3³ + ... + N^N 这么多天之后是星期几。

也就是求f % 7对于每个输入的N的值。这题在网上一搜题解，都说是打表找规律，当然这题有两种找法，一是对于每个iⁱ % 7 的值都找规律。

这里我们打表可知前100个值如下所示

1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2 5 1 5 1 0 1 4 1 4 4 6 0 1 1 3 2 6 1 0 1 2 2 1 2 6 0 1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2 5 1 5 1 0 1 4 1 4 4 6 0 1 1 3 2 6 1 0 1 2 2 1 2 6 0 1 4 6 4 3 1 0 1 1 4 2 1 6 0 1 2

有一种找规律的方法是当有数字等于第一个数的时候做个标记，再人工判断是否能够构成一个循环。

不可否认的，对于周期较短的一组数字这样找周期并不难，可是如果周期大到数百数千甚至数万时，靠这种方法找周期恐怕是杯水车薪。

当时我就迷茫在了这一长串的数字中不知所措，猛然想起前不久看过的KMP中next数组的性质，当即想到了用KMP求最小重复子串长度的方法，于是脑洞大开……

该性质为：令j=leni-next[i],如果i%j==0且i/j>1，j就是Pi的最小循环节( Pi表示文本串的前i个字符，leni表示该字符串的长度，一般表示为leni = i + 1)

还有一种找规律的方法是直接对 f % 7 的值进行打表找规律，按照上述方法找到的周期为294，下面要做的就很简单了~

 #include <iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define N 605

 #define M 200

 #define ll long long

 using namespace std;

 int i,j;

 int T;

 int l;

 int a[N],sum[N];

 char s[N];

 int next[N];

 int fun(int n)

 {

     int re = ;

     for(int i=;i<=n;i++){

         re*=n;

         re%=;

     }

     return re;

 }

 void ini()

 {

     a[]=sum[]=;

     a[]=sum[]=;

     s[]='';

     s[]='';

     for(i=;i<=N-;i++){

         a[i]=fun(i);

         sum[i]+=a[i]+sum[i-];

         sum[i]%=;

         s[i]=sum[i]+'';

     }

     s[i]='\n';

     //printf("%s\n",s);

    // for(i=1;i<=M;i++){

        // printf(" %d %d %d\n",i,a[i],sum[i]);

        // printf(" %d",sum[i]);

     //}

     return;

 }

 void ini2()

 {

     int  j = -,  i = ;

     next[] = -;

     while(i < N-)

     {

           if(j == - || s[i] == s[j])

          {

                     i++;

                     j++;

                     next[i] = j;

          }

          else

         {

                    j = next[j];

         }

     }

 }

 void ini3()

 {

     for(int i = ; i <= N-; ++i)

         {

             int length = i - next[i]; //循环节的长度

             if(i != length && i % length == ) //如果有多个循环

             {

                 printf("%d %d\n", i, i / length);

                 break;

             }

         }

 }

 int main()

 {

     int x;

     int ans;

     ini();

     //ini2();

    // ini3();

     //freopen("data.txt","r",stdin);

     scanf("%d",&T);

     //while(scanf("%d",&n)!=EOF)

     while(T--)

     {

         scanf("%d",&x);

         ans=sum[x%];

         if(ans==) printf("Saturday\n");

         else if(ans==) printf("Sunday\n");

         else if(ans==) printf("Monday\n");

         else if(ans==) printf("Tuesday\n");

         else if(ans==) printf("Wednesday\n");

         else if(ans==) printf("Thursday\n");

         else if(ans==) printf("Friday\n");

     }

     return ;

 }

后来又练了一次，用了map

4172110

2016-03-15 15:26:39

Accepted

3785

C++

820

280

njczy2010

 #include <iostream>

 #include <cstdio>

 #include <map>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <string>

 using namespace std;

 #define N 1005

 #define ll long long

 #define mod 7

 int TT;

 int n;

 int s[N];

 int next[N];

 map<int,string> mp;

 void get_next()

 {

     int i,j;

     i = ;

     j = -;

     next[] = -;

     while(i<N)

     {

         if(j == - || s[i] == s[j]){

             i++;j++;next[i] = j;

         }

         else{

             j = next[j];

         }

     }

 }

 int quickpow(int x,int n)

 {

     int re = ;

     while(n)

     {

         if(n&){

             re = (re * x) % mod;

         }

         n /= ;

         x = (x * x) % mod;

     }

     return re;

 }

 void fi()

 {

     int i;

     for(i = ;i < N;i++){

         int length = i - next[i]; //循环节的长度

         if(i != length && i % length == ) //如果有多个循环

         {

             printf("%d %d %d\n", i, length, i / length);

             break;

         }

     }

 }

 void ini()

 {

     int i;

     s[] = ;

     for(i = ;i < N;i++){

         s[i] = (s[i - ] + quickpow(i,i) )%mod;

     }

     mp[] = "Saturday";

     mp[] = "Sunday";

     mp[] = "Monday";

     mp[] = "Tuesday";

     mp[] = "Wednesday";

     mp[] = "Thursday";

     mp[] = "Friday";

     //get_next();

     //fi();

     //

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     ini();

     scanf("%d",&TT);

     while(TT--){

     //while(scanf("%d",&n)!=EOF){

         scanf("%d",&n);

         cout << mp[ s[ n% ] ] << endl;

     }

     return ;

 }

巴特西