Codeforces 1129D Isolation
一个长度为(n)的序列，上面每个位置有一种颜色，求把这个序列分割成若干段，使得每一段的只出现一次的颜色个数不超过(k)个，求方案数。
(n le 10^5)
设(dp[i])表示(1...i)的合法划分方案数
显然 (dp[i]=sum_{j=1}^{i-1}dp[j][cnt(j,i) le k])
对于(cnt(j,i))的计算：
定义数组(b)，如果([i,j])中(a_j)的颜色第一次出现，那么(b_j=1)，如果是第二次出现，那么(b_j=-1)，否则(b_j=0)
那么(cnt(j,i)=sum_{k=j}^ib_k)
考虑(i)转移到(i+1)的过程，我们发现只有一个(b_p)从(1)变成(-1) ，有一个(b_q)从(-1)变成(0)
考虑(cnt(j,i+1))相对于(cnt(j,i))的变化本质就是([p+1,i])区间(+1)，区间([q+1,p]-1)，其余不变
那么我们需要支持两种操作：
- 区间加减(1)
- 求所有满足(cnt(j,i)le k) 的所有(dp[j])之和
使用分块维护
时间复杂度(O(nsqrt n))
ARC060E Representation
题意：
把一个长度为 (len) 的串切成 (k) 段，使得其每一段都不是循环的(由一个子串出现 (ge 2) 次构成)，求最小的 (k) ，以及在最小的 (k) 之下的方案数，对 (10^9+7) 取模。
(len le 5 imes 10^5)
题解：
(并不)容易发现， (k) 只有3种取值，(1,2,len) 考虑原串如果不是循环的，那么答案为 (1) ，如果是循环的且循环节长度 (>1) ，那么随便找一个循环节中间断开即可，如果全是同一种字母，显然没有办法，只能切成 (len) 段
求出 (k) 之后就可以很容易的统计方案数了， (k=1,len) 答案显然，对于 (k=2) 求出正串和反串的 (next) 数组，枚举断点即可
#include <cstdio>
#include <cstring>
const int N=500005;
int nxt1[N],nxt2[N];
char s1[N],s2[N];
inline void getnxt(char *s,int *t){
int n=strlen(s+1);
for (int i=2,k=0;i<=n;i++){
while (k&&s[k+1]!=s[i]) k=t[k];
if (s[k+1]==s[i]) k++;t[i]=k;
}
}
int main (){
scanf ("%s",s1+1);
int n=strlen(s1+1),cnt=0,f=1;
for (int i=2;i<=n;i++) if (s1[i]!=s1[i-1]) f=0;
if (f){
printf ("%d
1",n,1);
return 0;
}
getnxt(s1,nxt1);
for (int i=1;i<=n;i++) s2[i]=s1[n-i+1];
getnxt(s2,nxt2);
if ((!nxt1[n])||(n%(n-nxt1[n])!=0)) {
puts("1
1");
return 0;
}
for (int i=1;i<n;i++)
if (((!nxt1[i])||(i%(i-nxt1[i])!=0))&&((!nxt2[n-i])||((n-i)%(n-i-nxt2[n-i])!=0))) cnt++;
printf ("2
%d",cnt);
return 0;
}
ARC064D Rotated Palindromes
题意：
给定数字 (n,k) ，求有多少长度为 (n) 的序列 (a)，同时满足以下两个条件：
- 对于任意 (1le ile n) ，(a_iin[1,k])
- 序列 (a) 可以通过循环位移变成回文串
答案对 (10^9+7) 取模 (n,kle 10^9)
题解：
如果没有循环节的限制，答案就是 (k^{lceilfrac{n}{2} ceil}) 次方
容斥，设 (dp[x]) 为最小循环节长度为 (v[x]) 时有多少个回文序列，转移时要减去它的约数的答案
考虑对答案的贡献：如果 (v[x]) 是奇数，贡献是 (v[x] imes dp[x]) ，否则贡献是 (frac{v[x]}{2} imes dp[x]) ，因为这一段必定是回文的，重复个数为一半
#include <bits/stdc++.h>
using namespace std;
const int N=2005,Mod=1e9+7;
int v[N],f[N];
inline int qpow(int a,int b){
int ans=1;
while (b){
if (b&1) ans=1ll*ans*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return ans;
}
int main(){
int n,k,tot=0,ans=0;
scanf ("%d%d",&n,&k);
for (int i=1; i*i<=n; i++)
if (n%i==0) {
v[++tot]=i;
if (i*i!=n) v[++tot]=n/i;
}
sort(v+1,v+tot+1);
for (int i=1; i<=tot; i++){
f[i]=qpow(k,(v[i]+1)/2);
for (int j=1; j<i; j++) if (v[i]%v[j]==0) f[i]=(f[i]-f[j]+Mod)%Mod;
if (v[i]&1) ans=(1ll*ans+1ll*v[i]*f[i]%Mod)%Mod;
else ans=(1ll*ans+1ll*(v[i]/2)*f[i]%Mod)%Mod;
}
printf ("%d",ans);
return 0;
}
ARC063C Integers on a Tree
题意和题解就直接放 zld 的集训队作业了......orz zld!!!
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int Head[N],Next[N<<1],Adj[N<<1],tot=0;
inline void addedge(int u,int v){
Next[++tot]=Head[u],Head[u]=tot,Adj[tot]=v;
Next[++tot]=Head[v],Head[v]=tot,Adj[tot]=u;
}
int L[N],R[N];
bool flag,p[N];
inline void check(int x,int f,bool t){
p[x]=t;
if (L[x]==R[x]) {
if ((L[x]&1)!=t) {
flag=false;
return;
}
}
for (int e=Head[x];e;e=Next[e])
if (Adj[e]!=f) check(Adj[e],x,t^1);
}
inline int Min(int a,int b){
return a<b?a:b;
}
inline int Max(int a,int b){
return a>b?a:b;
}
inline void dfs(int x,int f){
for (int e=Head[x];e;e=Next[e])
if (Adj[e]!=f){
dfs(Adj[e],x);
L[x]=Max(L[Adj[e]]-1,L[x]);
R[x]=Min(R[Adj[e]]+1,R[x]);
}
}
inline void dfs2(int x,int f){
if (f){
L[x]=Max(L[f]-1,L[x]);
R[x]=Min(R[f]+1,R[x]);
if (L[x]>R[x]){
puts("No");
exit(0);
}
}
for (int e=Head[x];e;e=Next[e])
if (Adj[e]!=f)
dfs2(Adj[e],x);
}
int a[N];
inline void getans(int x,int f,int lst){
if (L[x]<=lst-1) a[x]=--lst;
else a[x]=++lst;
for (int e=Head[x];e;e=Next[e])
if (Adj[e]!=f) getans(Adj[e],x,lst);
}
int main (){
memset (L,-0x3f,sizeof(L));
memset (R,0x3f,sizeof(R));
int n;scanf ("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf ("%d%d",&u,&v);
addedge(u,v);
}
int m;scanf ("%d",&m);
int rt=1;
for (int i=1,x,v;i<=m;i++){
scanf ("%d%d",&x,&v);
rt=x;
L[x]=R[x]=v;
}
flag=true,check(rt,0,L[rt]&1);
if (!flag) {
puts("No");
return 0;
}
dfs(rt,0);
dfs2(rt,0);
puts("Yes");
getans(rt,0,L[rt]-1);
for (int i=1;i<=n;i++) printf ("%d
",a[i]);
return 0;
}
ARC061D Card Game for Three
题意：
A,B,C三个人玩游戏，最初每个人分别有 (n,m,k) 张牌，每张牌上有字母 (a,b,c) 之一，但是不知道每张牌具体是什么。由A先操作，每轮操作者翻出自己牌堆顶的一张牌并弃置，下一轮的操作者是该牌上字母对应的人。不能操作的人赢。问有多少种初始牌的情况能使A胜利。答案模 (10^9+7)
(n,m,kle 3 imes 10^5)
题解：
原理：枚举抽到了多少张非 (A) 的卡牌，然后 (A) 可以放置的位置是 (inom{n+i-1}{n-1})
剩余没有选择的 (m+k-1) 张卡牌显然随便取
之后我们发现没有计数的是 (B,C) 的相对位置
我们枚举一个 (B) 的个数，计算 (B) 的位置安排方法，然后剩下的地方放 (C)
最后加起来就是 (B,C) 的相对位置
优化：
直接计算显然是 (O(n^2)) 级别的 ((n,m,k) 同阶 ())
我们观察最后那个 (sum) 如何拆开
- 当 (i< k) 的时候即为 (sum_{x=0}^{x<k}inom{i}{x})
- 当 (i<m) 的时候即为 (sum_{x=0}^{x<m}inom{i}{x})
- 当 (mle ile m+k) 的时候即为 (sum_{x=m+1}^{x<k}inom{i}{x})
这三种情况显然可以递推了，类似杨辉三角那样
#include <cstdio>
const int N=1000005,Mod=1e9+7;
inline int qpow(int a,int b){
int ans=1;
while (b){
if (b&1) ans=1ll*ans*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return ans;
}
int fac[N],inv[N],pow3[N];
inline void init_binom(){
fac[0]=1;for (int i=1;i<=1000000;i++) fac[i]=1ll*fac[i-1]*i%Mod;
inv[1000000]=qpow(fac[1000000],Mod-2);
for (int i=999999;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
pow3[0]=1;for (int i=1;i<=1000000;i++) pow3[i]=1ll*pow3[i-1]*3ll%Mod;
}
inline int C(int n,int m){
return 1ll*fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int n,m,k;
int main (){
init_binom();
scanf ("%d%d%d",&n,&m,&k);
int ans=0,x=1;
if (m<k) m^=k^=m^=k;
for (int i=0;i<=m+k;i++) {
ans=(ans+1ll*C(n-1+i,n-1)*pow3[m+k-i]%Mod*x%Mod)%Mod;
if (i<k) x=x*2ll%Mod;
else if(i>=m) x=((x*2ll%Mod-C(i,k)-C(i,i-m))%Mod+Mod)%Mod;
else x=(x*2ll%Mod-C(i,k)+Mod)%Mod;
}
printf ("%d",(ans+Mod)%Mod);
return 0;
}
ARC068 Solitaire
题意：把 (1...n) 顺次加入双端队列（可以从前后加），再删除 (k) 个（可以从前后删），问删到的第 (k) 个是 (1) 的删除序列的个数，答案对 (10^9+7) 取模
(kle nle 2 imes 10^3)
我们考虑合法的删除序列的性质
- 第 (k) 个数字是 (1) （废话）
- 前 (k-1) 个数字可以拆分成一个或两个（非连续）下降序列
考虑原因？如果双端队列为 (a_1,a_2,a_3...,1,a_{n-2},a_{n-1},a_n) 那么显然有 (a_1>a_2>a_3) 以及 (a_{n-2}<a_{n-1}<a_n)，把从前面删的提取成一个序列，从后面删的提取成一个序列 - 由性质 (2) 拆出来的序列中，其中一个的最小值大于没删除的所有数字的最大值
接下来考虑构造：
先考虑剩下来的 (n-k) 个数字，可以随便 pop ，所以
已经弹出的序列，考虑dp，设 (f[i][j]) 表示前 (k-1) 个数字中，已经确定了 (i) 个数字，它们的最小值为 (j)
设删除后两个序列为 (AB) 且 (A) 一直删到 (1) ，(B) 满足性质 3
那么可以选择下一个数字放在 (A) 后或者 (B) 后
如果放在 (A) 后，那么新加入的数字一定小于 (j) ，如果放在 (B) 后，那么新加入的数字一定是没加入的数字中最大的（性质3），所以它不会比 (j) 小，转移时使用后缀和优化即可
代码非常简单
#include <cstdio>
const int Mod=1e9+7,N=2005;
int f[N][N],n,k;
int main (){
scanf ("%d%d",&n,&k);
for (int i=2;i<=n;i++) f[1][i]=1;
for (int i=1;i<k-1;i++){
int sum=f[i][n-i+1];
for(int j=n-i;j>=2;j--){
sum=(sum+f[i][j])%Mod;
f[i+1][j]=(f[i+1][j]+sum)%Mod;
}
}
int ans=0;
for (int j=2;j<=n-k+2;j++) ans=(ans+f[k-1][j])%Mod;
if (k==1) ans=1;
for (int i=1;i<=n-1-k;i++) ans=ans*2%Mod;
printf ("%d",ans);
return 0;
}
CF1139D Steps to One
题意：
给定一个数字 (m) ，每次等概率随机一个 ([1,m]) 区间内的数字加到序列中，问序列的 (gcd=1) 的期望步数
(mle 10^5)
题解：
Orz CYJian
设 (f[i]) 表示 (gcd) 从 (i) 变成 (1) 的期望步数
显然 (f[1]=0) 那么：
考虑转移，显然有：
对式子进行莫比乌斯反演：
设 (T=td) ，继续推：
故原式为：
设 (g[T]=sum_{d|T}f[d]mu(frac{T}{d}))
对于每一个新递推出的 (f[x]) ，可以以调和级数的复杂度更新所有的 (g)
但是当 (T=d=i) 的时候会出现未知的 (f[i]) ，考虑把它拿到等式左边：
这样就可以转移了......时间复杂度 (O(mlogm))
#include <bits/stdc++.h>
using namespace std;
const int N=100005,Mod=1e9+7;
bool notp[N];int p[N],tot=0,mu[N];
vector <int > d[N];
int f[N],g[N];
int m;
inline void getmu(){
mu[1]=1;
for (int i=2;i<=m;i++){
if (!notp[i]) p[++tot]=i,mu[i]=-1;
for (int j=1;j<=tot&&i*p[j]<=m;j++){
notp[i*p[j]]=true;
if (i%p[j]==0) break;
mu[i*p[j]]=-mu[i];
}
}
for (int i=1;i<=m;i++)
for (int j=i;j<=m;j+=i)
d[j].push_back(i);
}
inline void insert(int x){
for (int i=1;i*x<=m;i++)
g[i*x]=((g[i*x]+f[x]*mu[i])%Mod+Mod)%Mod;
}
inline int qpow(int a,int b){
int ans=1;
while (b){
if (b&1) ans=1ll*ans*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return ans;
}
int main (){
scanf ("%d",&m);
getmu();
f[1]=0;
int ans=0;
for (int i=2;i<=m;i++){
f[i]=m;int s=d[i].size();
for (int j=0;j<s;j++){
int T=d[i][j];
f[i]=(f[i]+1ll*(m/T)*g[T]%Mod)%Mod;
}
f[i]=1ll*f[i]*qpow(m-(m/i),Mod-2)%Mod;
ans=(ans+f[i])%Mod;insert(i);
}
ans=1ll*ans*qpow(m,Mod-2)%Mod,ans=(ans+1)%Mod;
printf ("%d",ans);
return 0;
}