梦熊 10 连测的第八个了。
写在亲前面的总结：因为下午班级合唱比赛，所以不太想打比赛，想去看演出的。鉴于我们第一个唱完，以及班主任说节目可以看到 15:40，所以一直在玩上去的很晚。之后在机房继续看完了节目。所以本场打的还挺抽象。
更加难评的是这竟然是我打的最好的一场（？），有点开心，但还是破防了。
一开始根据爆搜想的 \(O(n)\) 的递推式子。
设 \(f[i]\) 表示长度为 \(i\) 时的方案数。
第 \(i\) 位有两种放发：若放 \(0\) 则答案不受限，同 \(f[i-1]\)；放 \(1\)，考虑 \(i-1\) 位放 \(0\)，则 \(i-2\) 受限只能放 \(0\)，答案即为 \(f[i-3]\)；考虑 \(i-1\) 位放 \(1\)，则第 \(i-2\) 位只能放 \(0\)，此时 \(i-3\) 只能放 \(0\)，则答案为 \(f[i-4]\)。这样就有 60pts 的好成绩了。
综上，\(f[i]=f[i-1]+f[i-3]+f[i-4]\)。
在我写完了这个递推式之后有了一个逆天的想法：它一定能打表预处理。于是我就开动了。
在这里详细记录一下我的打表方法。感觉最近打表能力日益增加。某种意义上讲，这是不可多得的第一手宝贵经验，很不容易的。
没有原因的写了一个答案取模之后的标记，标记取模后答案的分布情况个数。发现在去到大于模数的答案之后，这个统计就没有变过了。
这说明取模后的答案种类数固定，也就是可能出现了循环节。于是每次到达这个统计的极值之后，记录当前位置。最后输出，发现他们的差一样。整理了一下，就找到了循环节作为模数。完美结束。
赛后考虑到，递推式的取模序列，是否一定存在循环节？bdfs 了一下，只看到一篇 blog 提到了这个问题，感觉挺有道理的但是我无法证明他的正确性。
于是找了同机房大佬 @御坂17379号 帮忙看。他认为差不多是正确的，所以这里就认为它是正确的。
结论：递推式的取模序列一定存在循环节。
只是找起来有些麻烦。有一种暴力的美。嗯。个人认为打表有助于提升专注度，愉悦身心，陶冶情操。
下面是我美丽的码。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
const int mod=10007;
ll t;
int n;
int a[N];
void solve(){
a[0]=1,a[1]=2,a[2]=4,a[3]=6,a[4]=9;
for(int i=5;i<=20016;i++){
a[i]=a[i-1]+a[i-3]+a[i-4];
a[i]=a[i]%mod;
}
n=(t%20016);
printf("%d",a[n]);
}
int main(){
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
scanf("%lld",&t);
if(t>=N-10){
solve();
return 0;
}
n=(int)t;
a[1]=2,a[2]=4,a[3]=6,a[4]=9;
for(int i=5;i<=n;i++){
a[i]=a[i-1]+a[i-3]+a[i-4];
a[i]=a[i]%mod;
}
printf("%d",a[n]);
}
正解是矩阵乘法。鉴于我不熟练这种东西，遂暂无下文。
我写的链结果他说忘了放链的数据忘记放了。我说我的分怎么没了。破防了。
链的写法是求最最多的不相交的区间个数。这是道橙的贪心，之前博客里还写过，第一反应是不太会写的。成煞笔了。题目传送门
正解 lca 相关，正在看。同机房大佬写了 n^2 的 dp。啊。我是飞舞啊。
赛时并没有看这道题，现在也没看。所以咕咕了。
P5188 [COCI2009-2010#4] PALACINKE
最后 9s 的时候交上了爆搜的码，有足足 15pts 我太开心了。然后其他还没写。
你看吧，我只会咕咕咕咕咕。