十月总结

10.11 广二

T1：计数、容斥原理

有一个计数的做法，大致做法是在最后面的开头统计，然后要求后面不能出现，这样贡献就是唯一的，需要fail树上跑下来dfn这样

容斥原理就比较直接，加上序列中有一个开头的，减去有两个开头的，加上有三个开头的...

我们假定一个位置集合S,我们只需要保证相临的位置的贡献即可，若它们两个没交，那贡献为它们两个中间没有被钦定的，若有交判断合不合法即可。

当然这个还需要考虑开头结尾因为是循环数组，发现这个贡献只与mx-mn有关，这启发我们去根据长度DP转移，而且每个位置能填的数都一样，所以我们用这个长度在好多种位置开始。

点击查看代码

int Fm(int a,int b){int s=1;while(b){if(b&1)s=s*a%P;a=a*a%P;b>>=1;}return s;}int n,m,K,b[N],pw[N];int xs[N],f[N],g[N];bool ok[N];bool MB_2;signed main() {cin>>n>>m>>K;     pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*K%P;for(int i=1;i<=m;i++) b[i]=read();for(int i=1;i<m;i++) {ok[i]=1;for(int j=1;j<=m-i;j++) if(b[j]^b[i+j]) ok[i]=0;}for(int i=1;i<=n;i++) xs[i]=(i<m?ok[i]:pw[i-m]);f[0]=1;for(int i=1;i<n;i++) {for(int j=0;j<i;j++)f[i]=(f[i]+f[j]*xs[i-j])%P;f[i]=(-f[i]+P)%P;}for(int i=1;i<n;i++) f[i]=(f[i]*xs[n-i])%P;int ans=n*pw[n-m]%P;for(int i=1;i<n;i++) ans=(ans+f[i]*(n-i))%P;cout<<ans;return 0;
}

---

10.13 夏增锐

T1 简单计数

之前貌似有个类似的题，只能说掌握的及其不牢固。

考虑尽可能靠后的匹配子序列S，枚举起点，起点前面当然随便填，后面相当于我们要选出n-1个位置，为了保证这个匹配是最靠后的，s中相邻两个字符在T中的间隔中不能出现靠前的那一个字符

即

\[ Ans=\sum_{i=1}^{k+1} { n+k-i \choose n-1 } \times 26^{i-1} \times 25^{k-i+1}\]

T2 线段树 容斥原理

首先如果k=1，那么变成了一个区间加减，统计全局不为0的位置就行。这个具体来讲就是维护最小值和最小值个数，如果最小值为0就减去最小值个数，否则就是区间长度。扫描线一下。

k多了的情况，就考虑容斥，因为我们相当于求交集，就用一堆并集容斥就行，具体的，若并集大小为奇数，就加上，不然就减去。

T3 贪心 动态规划

随便贪一下就行，注意考场切莫急躁，注意细节，选择合适的方法

T4 Ad-hoc 构造

观察原始式子发现一定大于d。设 \(a \oplus b \oplus c \oplus d=d+x\) ,为了方便我们令d的后几位为0，x为1

\[a \oplus b \oplus c=1 \]

\[d= \frac {a^2+b^2+c^2-1} {2} \]

\[d \equiv 0 \pmod 2 \]

开始构造，以下构造正确性显然不证:

设p为a二进制下最高位

\(a \equiv 0 \pmod 2\) : \(b=a+2^p,c=2^{p+1}+2^p+1\)

\(a \equiv 1 \pmod 2\) : \(b=a+2^p-1,c=2^{p+1}+2^p\)

---