题目名称 1880. [国家集训队2011]画圈圈
输入输出 nt2011_circle.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 20
题目来源 Gravatarcstdio 于2014-12-16加入
开放分组 全部用户
提交状态
分类标签
插头DP 状态压缩
分享题解
通过:11, 提交:22, 通过率:50%
Gravatarsui 100 0.064 s 1.53 MiB C++
Gravatarmikumikumi 100 0.206 s 1.14 MiB C++
Gravatarmikumikumi 100 0.242 s 1.14 MiB C++
GravatarrpCardinal 100 0.243 s 1.67 MiB C++
GravatarrpCardinal 100 0.343 s 2.20 MiB C++
GravatarrpCardinal 100 0.354 s 3.45 MiB C++
Gravatarztx 100 0.717 s 32.30 MiB C++
Gravatarztx 100 0.950 s 30.82 MiB C++
Gravatarthomount 100 1.778 s 2.66 MiB C++
Gravatarwjyi 100 3.073 s 38.56 MiB C++
关于 画圈圈 的近10条评论(全部评论)
评测姬好慢。。
Gravatar_Horizon
2016-07-06 08:01 3楼
发现了一种非常优美的插头DP的写法
Gravatarmikumikumi
2016-03-26 11:42 2楼
题水,数据更水。虽然这题在COGS上有4颗星的难度,但恶心程度连Formula I这道例题都不如。
GravatarrpCardinal
2015-01-01 22:25 1楼

1880. [国家集训队2011]画圈圈

★★★   输入文件:nt2011_circle.in   输出文件:nt2011_circle.out   简单对比
时间限制:1 s   内存限制:512 MiB

【试题来源】

2011中国国家集训队命题答辩

【问题描述】

有N行M列的点组成一个点阵。你通过用水平和竖直的线段连接一些相邻的点画若干闭合的回路,将所有的点连接起来,组成一个图形。连的线被视为是内部和外部的界限。其中,有一些点(用*和#表示)不用被连接,且用*表示的点在必须在图形内部,用#表示的点必须在图形外部。
例如:(用+表示点,-和|表示线,x表示图形内部)

以及
注意:这个点是在外部!
你要写一个程序来计算一共有多少种连线的方法。我们只关心它模一个大质数123456791的余数。

【输入格式】

输入的第一行包含两个正整数,分别表示行数N和列数M。
接下来N行,每行M个字符表示点的情况(用.*#来表示三种点)。
50%的数据满足:
总的方法数小于220000
100%的数据满足:
M≤12,N≤20

【输出格式】

输出一个整数,表示总方法数模123456791的余数。

【样例输入】

5 6
......
....*.
..#...
......
......

【样例输出】

117