题目描述

十三号星期五真的很不常见吗？

每个月的十三号是星期五的频率是否比一周中的其他几天低？

请编写一个程序，计算 $N$ 年内每个月的 $13$ 号是星期日，星期一，星期二，星期三，星期四，星期五和星期六的频率。

测试的时间段将会开始于 $1900$ 年 $1$ 月 $1$ 日，结束于 $1900+N−1$ 年 $12$ 月 $31$日。

一些有助于你解题的额外信息：

1. $1900$ 年 $1$ 月 $1$ 日是星期一。
2. 在一年中，$4$ 月、$6$ 月、$9$ 月、$11$ 月每个月 $30$ 天，$2$ 月平年 $28$ 天，闰年 $29$ 天，其他月份每个月$31$天。
3. 公历年份是 $4$ 的倍数且不是 $100$ 的倍数的年份为闰年，例如 $1992$ 年是闰年，$1990$ 年不是闰年。
4. 公历年份是整百数并且是 $400$ 的倍数的也是闰年，例如$1700$年，$1800$年，$1900$年，$2100$年不是闰年，$2000$年是闰年。

样例

输入格式

共一行，包含一个整数 $N$。

输出格式

共一行，包含七个整数，整数之间用一个空格隔开，依次表示星期日，星期一，星期二，星期三，星期四，星期五，星期六在十三号出现的次数。

数据范围

$1≤N≤400$,

输入样例：

20

输出样例：

36 33 34 33 35 35 34

基姆拉尔森计算公式秒解法

$O(nm)$

题意分析

题目要求我们计算从$1900$年$1$月$1$日至$1990+n-1$年$12$月$31$日中$13$号落在周一到周日的次数。非常简单而又朴素的想法是枚举各年各月的$13$号，并通过一个函数week_day(year, month, day)将该日期转换成星期，并用一个数组count[7]进行储存。

关键日期转星期函数的编写

有关于Kim larsen calculation formula的百度百科。该公式可以直接通过年月日求出当天星期。还有一个相似的Zeller’s formular，均为秒杀日期模拟题的利器。

基姆拉尔森计算公式：

$week = (day + 2 \times month + [3 \times (month + 1) \div 5] + year + [year \div 4] - [year \div 100] + [year \div 400] + 1) \bmod 7$

其中$[num]$表示取整，实际中直接用int除就完事了QwQ。需要注意的是，该公式将每年的$1$月与$2$月份作为前一年的$13$与$14$月份进行计算，所以需要在代码中进行一个小小的特判即可完成。

时间复杂度

双重循环枚举年月，所以是$O(mn)$。

C++ 代码

#include <iostream>
using namespace std;
int week_day(int year, int month, int day)
{
    if (month == 1 || month == 2) month += 12, year--;
    return (day + 2 * month + 3 * (month + 1) / 5 + year + year / 4 - year / 100 + year / 400 + 1) % 7;
}
int main()
{
    int year_len = 0;
    cin >> year_len;
    int count[7] = {0};
    for (int current_year = 1900; current_year < 1900 + year_len; current_year++)
        for (int current_month = 1; current_month <= 12; current_month++)
            count[week_day(current_year, current_month, 13)]++;
    cout << count[6] << " "<<count[0]<< " "<<count[1]<< " "<<count[2]<< " "<<count[3]<< " "<<count[4]<< " "<<count[5];
    return 0;
}