上午
100 + 10 + 0 \rightarrow 100 + 10 + 100
T1 手机号码
设计的状态略有不同，f_{dig,past,len,opt1,opt2}保存在当前数位、前一位数字、之前数位最长连续所有数字相同的后缀的长度、之前是否存在连续三个相同数字、之前是否有8或4确定时的方案数
在 {dig}\lt{1} 时用 opt1判断是否合法，整个过程中动态维护opt2
ll f[20][20][20][2][3],num[20];//0 no/1 8/2 4
ll dp(ll dig,ll past,ll len,ll opt1,ll opt2,ll lim,ll zero){
if(dig<1) return opt1;
if(!lim&&!zero&&f[dig][past][len][opt1][opt2]!=-1) return f[dig][past][len][opt1][opt2];
ll ret=0,upon=lim?num[dig]:9;
rep(i,0,upon){
if((!i&&zero)||(opt2==1&&i==4)||(opt2==2&&i==8)) continue;
ll now=(i==past?len+1:1);
ret+=dp(dig-1,i,now,opt1|(now>=3),i==8||i==4?(i==8?1:2):opt2,i==upon&&lim,!i&&zero);
}
if(!lim&&!zero) f[dig][past][len][opt1][opt2]=ret;
return ret;
}
T3 代码拍卖会
多的不说，解释一下题解里被一行概括的组合数
n个小球划分为m组，因为可以为空，不能用隔板法直接算
那么考虑再加入m个小球，原来有x个小球的组此时分配到x+1个小球，这样使得所有组非空，可以用隔板法直接算
所以答案为C_{n+m-1}^{m-1}，再用人尽皆知的公式转化为题解的形式（你blog的markdown实在不能再支持更多内容了
下午
爆零 \rightarrow 还是爆零
wwh偷听听力被别校教练铁拳制裁了 (笑