Description
Jyc最近在学《现代交换原理》这门传说中的北京市精品课程。本来以为很简单,但晚上在做作业时就被一道题搞的很郁闷。交换单元是交换网络最基本的部件,其有M根入线和N根出线,它的功能就是将这M根入线上的数据按一定的规则交换到N根出线上。这个单元内部连线的不同就造成出线数据的不同,因此会有许多组合。比如说下面就是最简单的两种组合。
当然这种连接有一定的规则。一根入线可以连到多根出线上,以实现广播的功能。但一根出线不能同时和多根入线相连,这样就会造成冲突。题目现在要对一个有M根入线和N根出线的系统进行处理,其要求M根入线和N根出线上都有合法数据在传输(输入输出线都不能出现悬空的情况),并保证是按规则在传输。现在让你计算这个交换单元有多少种不同的连接方案。结果用12345678取模。
Input
Line 1: 一个整数T,表示有T组测试数据
Lines 2..T+1: 有T+1行每行有两个整数M (1 ≤ T≤ 1000),N (1 ≤ T≤ 1000),表示该单元有M条入线和N条出线。
Output
对每个测试数据只有一行,一个整数,表示可能的组合数
Sample Input
3
2 2
2 3
2 4
Sample Output
2
6
14
Hint
线与线之间是有区别的。
题目问的是有多少种方案,没有合法解就是0。
Source
Jyc@EagleHustle
上机复试前看见有人在群里问,所以试了下做的题,dp。
递推公式为:dp[i][j]=i*(dp[i][j-1]+dp[i-1][j-1])//i代表入线,j代表出线
代码:
#include<iostream> using namespace std; long long dp[1005][1005];//dp[i][j]表示i条入线,j条出线 int main() { for(int i=0;i<=1000;i++) dp[0][i]=dp[i][0]=0; dp[1][1]=1; for(int i=1;i<=1000;i++) { for(int j=1;j<=1000;j++) { if(i>j) dp[i][j]=0; else dp[i][j]=((i%12345678)*((dp[i][j-1]+dp[i-1][j-1])%12345678))%12345678; dp[1][1]=1; } } int t; scanf("%d",&t); while(t--) { int m,n; scanf("%d %d",&m,&n); printf("%ld\n",dp[m][n]); } return 0; }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
boj:算法
JAVA_BOJ
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行