BZPRO
#3785. 分配房间
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
正整数1…N编号，房间i和房间j之间的距离为|i-j|。
现在总共有m名同学，用1…m编号，每个人选择一个房间住下。有些同学是好友，
就希望住的近一些，不是好友的就希望住的远一些。好友关系是双向的，并且能保证对应
的无向图是连通的。假如两位同学互为好友，他们住的房间距离就不能超过D，否则必须
严格大于D。
陶陶交给你的任务是：计算出有多少种分配房间的方案。由于答案可能很大，你只需
要输出答案mod1,000,000,007后的值。
输入格式
第一行包含三个正整数N,M,D�。
下面�M行用于描述好友关系，第i行第j个字符表示编号为i的同学和编号为j是否为好
友，Y表示是好友，N表示不是好友。第i行第�j个字符一定为N，但没任何特殊含义。数
据保证一定满足题目的要求。
输出格式
包含一个非负整数，表示答案mod1,000,000,007后的值。
样例
样例输入
522
NY
YN
样例输出
14
数据范围与提示
N<=100,M<=50,D<=8
BZPRO