惊奇地发现自己 OI 没有白学

你们这些不函数式的语言就没有这些烦恼……

今天上午的题很鬼畜。。

死于GBK && UTF-8

去雅礼会被虐的

Day -1

吾辈是蒟蒻，标程嘛，还没有

出题人mk。

呐。。第一次出题。。。 感谢mk，wcg，kZime，zf验题 感谢zf提供T3 本文链接：https://margatroid.xyz/2017-09-29-contest-20170929-solve/

数论

• 拓欧
• 线性筛
• 求欧拉函数
• 组合数

[COGS 1517] 放国王

题目描述

原题地址：COGS

思路

对于此题，先考虑一个弱化版的题目：

• 在$n\times n$的棋盘上放国王，有多少种方法？

[COGS 1516] 棋盘上的车

题目描述

原题地址：COGS

思路一

乘法原理水过，计算$n!$即可，复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子，一行一行放，可以用一个二进制数表示状态，如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数，可以知道，$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$，类似地，我们可以推出方程：