TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5414
  • 問題
  • P5414【继续欢乐】正确的理解
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 2s 256MB
    問題説明

    nodgd正确的理解了题意。

    正确的题目是这样的:有一个 \(n\times n\) 的棋盘,有些位置已经放了棋子,有些位置已经标记了不允许放棋子,其他的位置都可以自由选择放棋子或者不放棋子。

    那么问题来了,有多少种方案,使得每行、每列、每条对角线都不被填满呢?

    为了体现坑爹,你需要自己去算出恰比 $10^{9.001}$ 大的第一个素数 \(p\) ,求方案数 \(\bmod p\) 的结果。

    入力形式

    输入 \(m + 1\) 行。 第一行两个整数 \(n,m\) 表示棋盘的大小和带有限制的位置数量。 接下来每行三个数 \(x,y,z\) ,表示第 \(x\) 行第 \(y\) 列放棋子 \((z=1)\) 或者不放棋子 \((z=0)\)

    出力形式

    输出一行,一个整数,表示答案。

    サンプル入力

    2 1
    0 0 0

    サンプル出力

    4

    ヒント

    输入输出样例1说明

    $2\times 2$ 的棋盘,一个角上不许放棋子。

    另外三个地方,可以都不放,也可以任选一个位置放,共 $4$ 种方案。

    数据规模与约定

    $0\leq n\leq 18, 0\leq m\leq n^2, 0\leq x,y\leq n-1$

    保证不会对同一个位置设置多条限制。


    ソース  感谢nodgd命题坑人