【HDOJ 5399】Too Simple
2024-08-29 19:01:57
pid=5399">【HDOJ 5399】Too Simple
函数映射问题 给出m函数 里面有0~m个函数未知(-1)
问要求最后1~n分别相应仍映射1~n 有几种函数写法(已给定的函数不可变 仅仅可更改未知的函数的映射)
假设映射过程中出现多对一 即入度n出度小于n 的函数 必然冲突 即最后必有落单 映射失败 为0
假设映射完整 已知的连续函数可压缩成一个函数 中间出入度可忽略 因此可压缩为-1 f -1 -1 f -1 -1 f这样的形态 进一步深入可发现中间的f仅仅起到通道作用 就可以压缩为连续的-1之间的映射 已知的函数仅仅起到”折射作用” 假设一段连续的函数相应为
1 2 3
3 2 1
仅仅是进行了扭曲 消除后不影响方案数 即经过与否不重要
连续的-1构成的方案数为 n!^(x-1) x为-1的个数
代码例如以下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#define sc "%lld\n"
#define ll long long
#define mod 1000000007
using namespace std;
ll a[101] = { 1, 1};
int f[101][101];
ll pow(ll x,int cnt)
{
int i;
ll ans = 1;
for(i = 0; i < cnt; ++i) ans = ans*x%mod;
return ans;
}
int main()
{
int n,m,i,j,cnt,x;
bool isok;
for(i = 2; i <= 100; ++i) a[i] = a[i-1]*i%mod;
while(~scanf("%d %d",&n,&m))
{
cnt = 0;
isok = 1;
for(i = 1; i <= m; ++i)
{
scanf("%d",&f[i][1]);
set <int> s;
s.insert(f[i][1]);
if(~f[i][1])
{
for(j = 2; j <= n; ++j)
{
scanf("%d",&f[i][j]);
s.insert(f[i][j]);
}
if(s.size() < n) isok = 0;
}
else cnt++;
}
if(!isok) puts("0");
else if(cnt) printf(sc,pow(a[n],(cnt-1)));
else
{
for(i = 1; i <= n; ++i)
{
x = i;
for(j = m; j >= 1; --j)
{
x = f[j][x];
}
if(x != i) break;
}
if(i != n+1) puts("0");
else puts("1");
}
}
return 0;
}
最新文章
- MMORPG大型游戏设计与开发(服务器 游戏场景 地图和区域)
- iframe异步加载技术及性能
- SortedSet有序集合类型
- spring-data-elasticsearch整合elasticsearch
- LeetCode题解——Palindrome Number
- 简单的实现QQ通信功能(二)
- 【POJ1743】 Musical Theme (二分+后缀数组)
- angular2与VS2015 asp.net core集成使用
- 第一部分 代码组织概念,集成开发环境(IDE)
- abstract关键字
- Material使用02 图标MdIconModule、矢量图作为图标使用及改进
- IOS中用到的缓存
- localhost和127.0.01 区别
- 使用MagicOnion实现gRPC
- centos6.5安装python2.7、pip、numpy、scipy
- JavaWeb学习 (十二)————使用Session防止表单重复提交
- CSS3圆角,阴影,透明
- C语言第一个例子hello world
- iOS状态栏标志
- node npm
热门文章
- DFS:POJ3620-Avoid The Lakes(求最基本的联通块)
- Hive元数据启动失败,端口被占用
- python第三方库之openpyxl(1)
- 【LeetCode】Remove Nth Node From End of List(删除链表的倒数第N个节点)
- Codeforces Round #390 (Div. 2) A+B+D!
- POJ 2157 Maze
- iOS大转盘抽奖
- UITableView性能-圆角图片
- [UOJ#130][BZOJ4198][Noi2015]荷马史诗
- haskell 乱搞笔记[原创]