#P9757. 矢巨阝车禾只禾口式 / CF468E Permanent

    ID: 6383 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 10 上传者: 标签>CF2900省选/NOI-贡献法二分图建模无向连通分量状压 DP倒序更新避免重复使用树形 DP回溯搜索可行性剪枝普通多项式乘法阈值划分大小情况

矢巨阝车禾只禾口式 / CF468E Permanent

题目描述

给定一个 n×nn\times n 矩阵 MM。求其积和式

$$\operatorname{perm}(M)=\sum_{\pi}\prod_{i=1}^n M_{i,\pi_i},$$

其中求和遍历 1,…,n1,\ldots,n 的所有排列 π\pi。矩阵中有 kk 个位置的值单独给出,其余位置均为 11。答案对 109+710^9+7 取模。

输入格式

第一行两个整数 n,kn,k。接下来 kk 行,每行三个整数 x,y,zx,y,z,表示 Mx,y=zM_{x,y}=z。

输出格式

输出一行一个整数,表示积和式对 109+710^9+7 取模的结果。

样例

2 2
1 1 4
2 1 4
8

矩阵两行均为 (4,1)(4,1),积和式为 4×1+1×4=84\times1+1\times4=8。

数据范围

1≤n≤1051\le n\le10^5,1≤k≤551\le k\le55,1≤x,y≤n1\le x,y\le n,2≤z≤1092\le z\le10^9。所有给出的 (x,y)(x,y) 互不相同。

子任务 分值 nn 上界 kk 上界
1 25 10
2 1000 20
3 10000 40
4 100000 55

本站原题面 PDF

同题模型的 Codeforces 原题