小衣同学的博客

这两部分重复统计了，重复统计的部分有9种，左上角（x,y）（1<=x<=3,1<=y<=3)比如，左上角的块是（1,1）时，有（1,1）（1,4）（4,1）（4,4）这种。枚举起始第几行填的，有1、4、7、10，2、5、8，3、6、9三种可能。也就是说（1,1）填1之后，（1,4）要填1，（1,7）要填1，然后第一行共线了之后，第四行共线，第七行共线，……事实上，可以给（1，x）（1<=x<=3)填1，要么是列共线，和行对称的，方法数相同。所以，答案是2*135-9=261种。

第三种情况暴力转移是O(n^2)的，但可以一边求一边暴力维护卷积mul，这样转移就是O(n)的了。第二三种情况1xxx11和11xxx1是可以合并成一种转移，给系数乘2的，转移是O(n)的，dp[i][0]表示没有前导0限制的方案数，dp[i][1]表示有前导0限制的方案数。能通过每次消除3个一样的数字，最终把数字消成空的数字是合法的，求串长度不超过n的，没有前导0的数字中，合法的数字的个数。这些，下划线的3个1不是位于最后的3个1，就会计数重复。求了f、dp[i][0]、dp[i][1]三个数组，