CF C.Ivan the Fool and the Probability Theory【思维·构造】

题目传送门

题目大意:

一个$n*m$的网格图,每个格子可以染黑色、白色,问每个格子最多有一个相邻格子颜色相同的涂色方案数
$n,m<=1e5$

分析:

首先,考虑到如果有两个相邻的格子颜色相同,那么这两行/列的格子状态就确定了。比如:

分享图片

 

 

 在中间两个爱心格子被确定的情况下,第二列和第三列的涂色情况就已经被确定了。实际上,第一列和第四列涂的颜色也确定了。(最后这句话我们留着待会儿分析)

分享图片

 

 

 同理,在中间两个星星确定的时候,第二行和第三行的涂色情况也唯一确定。实际上,第一行和第四列涂的颜色也确定了。

 


假如说在一个方格中,既有横着出现的两个连续的一样颜色的格子,也有竖着出现的两个连续的一样颜色的格子,就像这样:

分享图片

 

 分享图片

 

 分享图片

 

 

 

那么一定会产生矛盾,无论怎么挪都会产生矛盾。(橙色的部分是既需要用灰色,也需要用蓝色涂的格子,是矛盾的地方)

所以,在一种着色方案中,这种相邻两个颜色一样的情况只会在一个方向中出现,我们只需要考虑一个方向那么多行的方案数,另外一个方向的同理就好。

 


 

如果已经确定相邻两个颜色一样的格子出现的方向(为方便讨论,下面我们假设这两个格子是竖着的),那么每一行的格子颜色一定是交错的,两行之间要么一样,要么颜色相反,而且颜色一样的不能连着出现3次及以上。

在第一行确定的情况下,如果要求每一个格子的每个相邻格子的颜色都和他不一样,那么这是一个棋盘染色,就唯一确定了。

但是,按照这道题的条件来说的话,后面的格子可以有两行,也可以只有一行。(就是一次性确定两行或一次性确定一行)

Like this:

分享图片

 

 

 

分享图片

 

 

 设$f[i]$表示铺到第$i$行(前$i$行)的方案总数,那么递推式就是$f[i]=f[i-1]+f[i-2]$

(初始化$f[0]=1$是一开始就是两行连着一样的情况)

答案就是$f[n]$。

然后,还有相邻两个颜色一样的格子是竖着的,方案数就是$f[m]$,这两类在前面已经说过没有交集,答案就是$f[n]+f[m]$

然后,棋盘染色的情况在两种情况中都被计算了,所以答案要减1。

最后,黑白颜色可以反过来,所以乘2.

做完了,$Nice!$

分享图片
 1 /*
 2 ID: Starry21               
 3 */ 
 4 #include<iostream>
 5 #include<string>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<map>
 9 #include<algorithm>
10 using namespace std;
11 #define N 100005
12 #define ll long long
13 #define MOD 1000000007
14 int n,m;
15 ll f[N];
16 int main()
17 {
18     scanf("%d %d",&n,&m);
19     f[0]=f[1]=1;
20     for(int i=2;i<=max(n,m);i++)
21         f[i]=(f[i-1]+f[i-2])%MOD;
22     printf("%lld\n",2*((f[n]+f[m])%MOD-1+MOD)%MOD);
23     return 0;
24 }
代码贼短
相关文章
相关标签/搜索
四肖八码期期准精选资料 乌苏市| 祁连县| 通州市| 东乡县| 孝感市| 汤原县| 环江| 乐昌市| 准格尔旗| 景宁| 六盘水市| 甘谷县| 清苑县| 井冈山市| 越西县| 阿坝县| 明星| 塔河县| 司法| 太康县| 咸阳市| 峨眉山市| 裕民县| 九寨沟县| 平度市| 自贡市| 乌拉特中旗| 利川市| 光山县| 宾阳县| 新安县| 湘潭县| 抚松县| 安徽省| 徐汇区| 郓城县| 晋江市| 石嘴山市| 栾城县| 香格里拉县| 曲靖市| 松溪县| 信丰县| 柳河县| 阿合奇县| 江西省| 体育| 北宁市| 武宁县| 从江县| 连州市| 丰都县| 犍为县| 庄河市| 遂溪县| 宝坻区| 思南县| 上犹县| 康定县| 黄大仙区| 海丰县| 三明市| 富阳市| 泸定县| 伊宁县| 汉阴县| 板桥市| 新巴尔虎右旗| 化德县| 屏南县| 巨鹿县| 伊通| 安宁市| 茶陵县| 桃江县| 榆中县| 哈巴河县| 大名县| 巴塘县| 绍兴县| 彰化县| 铜川市| 丘北县| 卫辉市| 兴山县| 泗水县| 奇台县| 永寿县| 化德县| 瑞安市| 赞皇县| 修水县| 江阴市| 石城县| 宜宾县| 界首市| 建湖县| 涿鹿县| 息烽县| 滦南县| 广西| 新竹县| 南华县| 桦甸市| 米林县| 紫阳县| 丰原市| 文山县| 宁城县| 蒙山县| 华容县| 娱乐| 肥东县| 临汾市| 肃北| 多伦县| 通许县| 清苑县| 四川省| 景谷| 宁河县| 伊金霍洛旗| 高淳县| 达日县| 繁昌县| 霸州市| 张家口市| 万盛区| 雅江县| 额尔古纳市| 海林市| 比如县| 嘉兴市| 鹰潭市| 辉县市| 利川市| 封丘县| 万宁市| 三原县| 静海县| 临泉县| 灵璧县| 文水县| 茂名市| 务川| 南通市| 浦县| 师宗县| 阜新市| 巧家县| 蒙山县| 巴里| 安新县| 广德县| 姜堰市| 卢湾区| 禹州市| 乌兰浩特市| 怀安县| 永登县| 太原市| 全南县| 兴业县| 兴业县| 朔州市| 蛟河市| 白朗县| 思茅市| 蚌埠市| 玉龙| 南开区| 峨眉山市| 平江县| 康保县| 珠海市| 长春市| 金湖县| 二连浩特市| 灌南县| 宜良县| 阿克| 通许县| 郧西县| 汾西县| 林口县| 安溪县| 泸定县| 平武县| 米林县| 南漳县| 兴国县| 婺源县| 柯坪县| 宜黄县| 玉屏| 平湖市| 潢川县| 五寨县| 周宁县| 黄陵县| 大宁县| 彰化市| 六枝特区| 濉溪县| 巢湖市| 北碚区| 攀枝花市| 涿鹿县| 水城县| 北宁市| 东安县| 万年县| 德兴市| 吉隆县| 淮安市| 南木林县| 越西县| 邵东县| 微山县| 恩施市| 南投县| 古蔺县| 忻州市| 且末县| 衡水市| 碌曲县| 临桂县| 南宫市| 龙井市| 吴忠市| 安丘市| 大田县| 肃北| 乌兰浩特市| 马边| 化德县| 自贡市| 肇东市| 金坛市| 修水县| 沈阳市| 沁源县| 安庆市| 尼勒克县| 中牟县| 交城县| 临江市| 岳西县| 泌阳县| 榆社县| 遂平县| 璧山县| 宜章县| 津南区| 南木林县| 太湖县| 荣成市| 昌乐县| 天祝| 寻乌县| 宁明县| 贵州省| 涿州市| 聊城市| 广丰县| 元阳县| 鹤山市| 忻城县| 鄢陵县| 类乌齐县| 高雄县| 辽中县| 鄂伦春自治旗| 逊克县| 县级市| 吐鲁番市| 新乐市| 汕尾市| 丹阳市| 阿克苏市| 宁陵县| 元江| 浏阳市| 祥云县| 包头市| 馆陶县| 阳西县| 深泽县| 彭阳县| 承德市| 沾化县| 海门市| 华宁县| 慈利县| 祁连县| 饶河县| 漯河市| 涞水县| 临清市| 工布江达县| 安顺市| 麟游县| 杂多县| 萨迦县| 青州市| 正宁县| 昌都县| 沾化县| 惠水县| 凭祥市| 德兴市| 名山县| 青州市| 获嘉县| 高邑县| 澳门| 萨嘎县| 青川县| 通渭县| 大冶市| 客服| 平泉县| 板桥市| 翁源县| 承德市| 阳东县| 泾川县| 崇文区| 石狮市| 多伦县| 明溪县| 措美县| 精河县| 博客| 衡水市| 白城市| 祥云县| 贵定县| 东乌珠穆沁旗| 始兴县| 宁海县| 德格县| 恭城| 邛崃市| 丹江口市| 微博| 开平市| 沙田区| 大方县| 三江| 屏东县| 松桃| 兴宁市| 上饶市| 安多县| 修水县| 黑水县| 德江县| 南丰县| 翁牛特旗| 临沂市| 昆明市| 台东县| 彭州市| 孝昌县| 白城市| 万宁市| 巴南区| 高青县| 武夷山市| 海城市| 汾西县| 安宁市| 扶余县| 陆丰市| 绥阳县| 磴口县| 青铜峡市| 仙居县| 尚义县| 新巴尔虎右旗| 延边| 阜南县| 保靖县| 右玉县| 长沙市| 綦江县| 庄河市| 新乡市| 博乐市| 德惠市| 黄冈市| 同仁县| 宜兴市| 尚志市| 南投市| 普定县| 曲周县| 巴青县| 碌曲县| 宜宾市| 阳江市| 吉林省| 桐梓县| 历史| 阿克苏市| 侯马市| 奉新县| 铅山县| 马鞍山市| 济阳县| 北碚区| 旬邑县| 海原县| 宁津县| 无为县| 土默特右旗| 楚雄市| 黑水县| 武威市| 周至县| 平定县| 梁河县| 德安县| 湖南省| 邵东县| 兴隆县| 横峰县| 辽宁省| 桃园县| 沂源县| 德清县| 鄯善县| 剑川县| 乐安县| 铅山县| 聊城市| 宝坻区| 贞丰县| 洛浦县| 广南县| 永城市| 通许县| 永城市| 简阳市| 高州市| 长沙县| 盖州市| 札达县| 台中县| 岗巴县| 赤峰市| 定边县| 莱州市| 志丹县| 永新县| 洛南县| 渝中区| 大英县| 琼海市| 吉水县| 广汉市| 石渠县| 化州市| 舞阳县| 麦盖提县| 潢川县| 宁河县| 双桥区| 都江堰市| 革吉县| 柳江县| 喀什市| 翁源县| 湖南省| 花莲县| 西安市| 蚌埠市| 邓州市| 固阳县| 开阳县| 新绛县| 常山县| 漳平市| 毕节市| 双牌县| 德州市| 车险| 界首市| 延长县| 义乌市| 镇沅| 绍兴县| 拜泉县| 诸暨市| 鹰潭市| 安义县| 普洱| 德州市| 纳雍县| 孝义市| 永新县| 仙居县| 漾濞| 金昌市| 分宜县| 巩义市| 南和县| 泽库县| 阜平县| 碌曲县| 彰化市| 翁牛特旗| 巴南区| 漳浦县| 北票市| 赤峰市| 南澳县| 绥芬河市| 东安县| 逊克县| 清远市| 鸡西市| 永定县| 莆田市| 凌海市| 会宁县| 当雄县| 沐川县| 英吉沙县| 大关县| 巴塘县| 平塘县| 明光市| 寿阳县| 西充县| 夏邑县| 项城市| 巴彦淖尔市| 喀什市| 萨嘎县| 和田市| 余姚市| 乡宁县| 伊金霍洛旗| 广州市| 白山市| 远安县| 体育| 和田县| 苗栗县| 灵川县| 红河县| 余干县| 商洛市| 曲靖市| 信丰县| 辽阳市| 麻城市| 库车县| 谢通门县| 榆树市| 宜丰县| 丹江口市| 雅江县| 宜良县| 永宁县| 双江| 卢龙县| 澎湖县| 石家庄市| 礼泉县| 宣汉县| 万安县| 繁峙县| 奈曼旗| 鄂托克旗| 开化县| 丹江口市| 盘锦市| 黎城县| 石楼县| 盱眙县| 定陶县| 含山县| 阿城市| 于都县| 绥宁县| 广德县| 唐海县| 西城区| 徐汇区| 武陟县| 内黄县| 屏南县| 青川县| 辽源市| 明溪县| 马关县| 宝兴县| 手游| 镇赉县| 平昌县| 东兰县| 钟山县| 德庆县| 襄垣县| 宝兴县| 滁州市| 陵川县| 乐昌市| 凌云县| 邵阳县| 洛川县| 敦煌市| 井陉县| 绥棱县| 尚志市| 凤翔县| 宜丰县| 凤山县| 民权县| 嘉善县| 广东省| 青神县| 安乡县| 文山县| 新泰市| 正宁县| 凌海市| 余庆县| 和政县| 德化县| 古交市| 高要市| 唐海县| 汝南县| 安多县| 新竹县| 山阴县| 扶绥县| 开平市| 溆浦县| 广东省| 凉山| 双辽市| 金秀| 凤凰县| 浦北县| 安庆市| 花莲县| 榆树市| 安图县| 穆棱市| 怀化市| 禹城市| 禄丰县| 项城市| 绥江县| 桐庐县| 尉犁县| 淮阳县| 丹巴县| 绥阳县| 前郭尔| 襄垣县| 正蓝旗| 林芝县| 辉县市| 紫金县| 仁怀市| 新巴尔虎右旗| 台前县| 司法| 卫辉市| 浦北县| 达尔| 察隅县| 嫩江县| 潞城市| 灵寿县| 江北区| 江北区| 华蓥市| 石屏县| 石泉县| 宽甸| 静海县| 平潭县| 库尔勒市| 乐东| 汽车| 关岭| 界首市| 大兴区| 和顺县| 荥阳市| 六安市| 上思县| 双辽市| 金门县| 高碑店市| 浦城县| 开平市| 平定县| 金乡县| 布拖县| 正定县| 尤溪县| 新和县| 余干县| 林周县| 秦皇岛市| 新源县| 静海县| 怀化市| 栖霞市| 正宁县| 城固县| 闽侯县| 琼海市| 增城市| 连南| 濮阳市| 万山特区| 东宁县| 石楼县| 榕江县| 酒泉市| 舒城县| 綦江县| 罗甸县| 新密市| 柳河县| 甘孜县| 五家渠市| 兰西县| 博白县| 霍林郭勒市| 珲春市| 澄城县| 新晃| 萨嘎县| 城固县| 昆山市| 蓝田县| 湘潭县| 怀安县| 永宁县| 乡宁县| 廉江市| 金阳县| 湖北省| 南平市| 宿州市| 南和县| 清苑县| 报价| 龙海市| 车险| 威远县| 通河县| 阆中市| 西乌| 六枝特区| 资讯| 阳曲县| 通许县| 武宣县| 涡阳县| 义乌市| 海安县| 谢通门县| 乌兰察布市| 隆德县| 吕梁市| 洛川县| 静海县| 句容市| 崇阳县| 清水县| 永州市| 汨罗市| 宜君县| 固阳县| 南和县| 偏关县| 喀什市| 盈江县| 封丘县| 乾安县| 沾化县| 贡嘎县| 嘉兴市| 西畴县| 蒙城县| 阜南县| 长汀县| 黄冈市| 龙门县| 宽甸| 太康县| 黎川县| 太白县| 彩票| 东丽区| 鹤山市| 中西区| 墨江| 新化县| 若尔盖县| 宿松县| 太仆寺旗| 龙江县| 友谊县| 德格县| 甘泉县| 翁源县| 汤阴县| 高雄县| 理塘县| 勃利县| 开平市| 嘉鱼县| 旅游| 凤山市| 洮南市| 和政县| 民勤县| 海阳市| 闵行区| 漳平市| 勃利县| 贡嘎县| 邵东县| 仪征市| 长丰县| 泗水县| 普宁市| 搜索| 新巴尔虎左旗| 天等县| 隆德县| 高碑店市| 阿克苏市| 康保县| 天气| 甘洛县| 桑植县| 本溪市| 理塘县| 瑞安市| 信宜市| 临西县| 桦南县| 云林县| 西乡县| 清徐县| 准格尔旗| 天全县| 太谷县| 巍山| 田林县| 泰兴市| 顺义区| 临澧县| 桂东县| 永胜县| 任丘市| 长沙市| 乌鲁木齐县| 泉州市| 任丘市| 乌鲁木齐市| 陇南市| 青川县| 灵宝市| 常熟市| 电白县| 金川县| 苍南县| 罗定市| 钟山县| 纳雍县| 镇原县| 南投市| 法库县| 兴义市| 元江| 平泉县| 萨迦县| 青海省| 德保县| 二手房| 宁阳县| 吕梁市| 景德镇市| 平和县| 迁安市| 富顺县| 望奎县| 大英县| 三都| 尉犁县| 祥云县| 连南| 泌阳县| 德昌县| 合水县| 沈丘县| 琼结县| 江口县| 缙云县| 平顶山市| 噶尔县| 东莞市| 郁南县| 井陉县| 肥乡县| 嘉峪关市| 婺源县| 乌拉特前旗| 法库县| 桐乡市| 育儿| 白城市| 大丰市| 巫山县| 称多县| 全州县| 碌曲县| 从江县| 安仁县| 抚顺市| 和平县| 万载县| 普宁市| 休宁县| 中阳县| 徐汇区| 即墨市| 桃园市| 广安市| 枣强县| 和政县| 肇东市| 华容县| 新宾| 阜宁县| 南雄市| 扶沟县| 蒙阴县| 静宁县| 来凤县| 毕节市| 包头市| 江都市| 太保市| 瓦房店市| 长武县| 四子王旗| 永昌县| 樟树市| 营山县| 休宁县| 凤冈县| 定边县| 张掖市| 汶川县| 仪陇县| 灵山县| 和政县| 山阳县| 邹平县| 阳高县| 巴马| 贵港市| 文化| 宣恩县| 新闻| 库伦旗| 黄冈市| 厦门市| 宁乡县| 海门市| 金溪县| 民和| 巢湖市| 四子王旗| 石泉县| 镇雄县| 拉萨市| 平乡县| 建湖县| 大渡口区| 崇仁县| 郑州市| 军事| 靖江市| 枣强县| 咸丰县| 宁河县| 图木舒克市| 金湖县| 托里县| 开远市| 武强县| 湖北省| 陇南市| 静宁县| 乌鲁木齐县| 榆中县| 孝义市| 河北省| 鱼台县| 太保市| 大丰市| 南漳县| 修水县| 万全县| http://www.bo2020bids.fun http://www.gz1980averagec.fun http://m.yqo6j7rl6v.fun http://www.yqo2j0rl2v.fun http://wap.bo2020seezs.fun http://wap.gz1980obtainc.fun http://www.gz1980handc.fun http://www.yqo0j7rl0v.fun http://m.gz1980forzatc.fun http://www.yqo7j2rl4v.fun http://m.gz1980forgetc.fun http://www.yqo4j1rl9v.fun http://m.gz1980bikec.fun http://www.yqo7j5rl5v.fun http://m.gz1980clubc.fun http://m.gz1980roundc.fun http://wap.bo2020zeshs.fun http://www.bo2020rests.fun http://wap.yqo0j7rl4v.fun http://wap.bo2020accesss.fun http://m.jvz0j0r6o.fun http://m.yqo2j5rl3v.fun http://www.bo2020presss.fun http://www.gz1980carec.fun http://wap.bo2020holes.fun