2017多校赛 Function
Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 838 Accepted Submission(s): 369
Define that the domain of function f is the set of integers from 0 to n−1, and the range of it is the set of integers from 0 to m−1.
Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i from 0 to n−1.
Two functions are different if and only if there exists at least one integer from 0 to n−1 mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo 109+7.
For each case:
The first line contains two numbers n, m. (1≤n≤100000,1≤m≤100000)
The second line contains n numbers, ranged from 0 to n−1, the i-th number of which represents ai−1.
The third line contains m numbers, ranged from 0 to m−1, the i-th number of which represents bi−1.
It is guaranteed that ∑n≤106, ∑m≤106.
1 0 2
0 1
3 4
2 0 1
0 2 3 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
ll a[],b[];
vector<ll> edgea,edgeb;
const ll mod=1e9+;
ll n,m;
void solve(int Case)
{
ll visa[],visb[];
memset(visb,,sizeof(visb));
memset(visa,,sizeof(visa));
for(int i=;i<m;i++)
{
if(visb[i]) continue;
ll ret=;
ll next_pos=b[i];
visb[next_pos]=;
while(next_pos!=i)
{ ret++;
next_pos=b[next_pos];
visb[next_pos]=;
}
// cout<<ret<<endl;
edgeb.push_back(ret);
}
ll f=;
for(int i=;i<n;i++)
{
if(visa[i]) continue;
ll ret=;
ll next_pos=a[i];
visa[next_pos]=;
while(next_pos!=i)
{
ret++;
next_pos=a[next_pos];
visa[next_pos]=;
}
ll temp=;
//cout<<ret<<endl;
for(int j=;j<edgeb.size();j++)
{
if(ret%edgeb[j]== || ret==edgeb[j]) temp=(temp+edgeb[j])%mod;
}
f=f*temp%mod;
}
printf("Case #%d: %d\n",Case,f);
}
int main()
{
cin.sync_with_stdio(false);
int Case=;
while(cin>>n>>m)
{
edgea.clear();
edgeb.clear();
for(int i=;i<n;i++) cin>>a[i];
for(int j=;j<m;j++) cin>>b[j];
solve(Case++);
}
return ;
}
最新文章
- Java集合系列:-----------04fail-fast总结(通过ArrayList来说明fail-fast的原理以及解决办法)
- linux下安装小鹤双拼-鹤形
- 阿里Linux Shell脚本面试25个经典问答
- MVC Action Filter
- Unity中Mecanim工作流
- UITabBarController详细说明(简介和设置)
- JavaScript(第二十二天)【动态加载js和css】
- 利用css3+js实现简单带立体过渡效果的图片切换(chrome浏览器)
- [Android] Android Error: Suspicious namespace and prefix combination [NamespaceTypo] when I try create Signed APK
- Django——图书管理系统
- cf1051d 简单的状态压缩dp
- 具有键“XXX”的 ViewData 项属于类型“System.Int32”,但它必须属于类型“IEnumerable<;SelectListItem>;
- 00011 - find中的-print0和xargs中-0的奥妙
- xilinx IP核配置,一步一步验证Xilinx Serdes GTX最高8.0Gbps
- KATANA Owin 资料收集
- 安装部署OpenPAI + VSCode 提交
- jsoup-1.7.2.jar 包
- Android JNI中的数据传递
- ubuntu和centos安装docker
- STM32 时钟配置的坑