Codeforces 1097
咕咕了一个月...终于闲的没事想起补了...
ABC代码没在本地（而且懒），就不放了...
（然而当时C题FST了真是想...= =）
D.Makoto and a Blackboard(DP 期望)
\(Description\)
给定\(n,k\)。每次\(n\)会等概率地变成自己的一个约数（包括\(1,n\)），求变化\(k\)次后\(n\)期望是多少。
\(n\leq10^{15},\ k\leq10^4\)。
\(Solution\)
将\(n\)质因数分解，\(n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)，每次变化后每个质因子的次数\(a_i\)会随机变成\(0\sim a_i\)中的一个数，且每个\(a_i\)的变化是独立的。
所以可以对每个质因子分别计算期望，最后乘起来。
令\(f[i][j]\)表示\(i\)次变化后，\(a\)变成\(j\)的概率，\(f[0][a]=1\)。
转移就是\(f[i][j]=\sum_{k=j}^a\frac{f[i-1][k]}{k+1}\)。
把所有质因数都算一遍，乘起来就好了。
质因子个数、次数都是\(\log\)级别的（其实乘起来也就\(\log\)级别？），所以复杂度是\(O(k\log^2n)\)（其实也就是\(O(k\log n)\)？）。
我竟然把逆元求成阶乘逆元了然后调二十分钟= =我也是醉了。
//217ms 0KB
#include <cstdio>
#include <algorithm>
#define mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=52;
int inv[N];
int Solve(int x,int K,int a)
{
static int sum[N];
for(int i=0; i<a;++i) sum[i]=0;
sum[a]=1, sum[a+1]=0;
for(int i=1; i<=K; ++i)
for(int j=a; ~j; --j)
sum[j]=sum[j+1]+1ll*sum[j]*inv[j+1]%mod, Mod(sum[j]);
LL ans=0;
for(int i=0,t=1; i<=a; ++i) ans+=1ll*t*sum[i]%mod, t=1ll*t*x%mod;
return ans%mod;
}
int main()
{
inv[1]=1;
for(int i=2; i<N; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
LL n,ans=1; int K; scanf("%I64d%d",&n,&K);
for(int i=2; 1ll*i*i<=n; ++i)//这个枚举貌似可以优化（每次+=6？）
if(!(n%i))
{
int a=1; n/=i;
while(!(n%i)) ++a, n/=i;
ans=ans*Solve(i,K,a)%mod;
}
if(n!=1) ans=ans*Solve(n%mod,K,1)%mod;//n可能很大 别忘取模！
printf("%I64d\n",ans);
return 0;
}
E.Egor and an RPG game(思路 LIS Dilworth定理)
\(Description\)
设\(k\)表示将一个排列\(A_i\)划分成若干个递增或递减子序列，所需子序列个数的最小值。令\(f(n)\)表示所有\(1...n\)的排列中，\(k\)的最大值。（有点绕...就是用最少的序列划分排列，\(f(n)\)是所有\(1\)到\(n\)的排列中所需序列最多的那个个数）
\(T\)次询问，每次给定一个\(1...n\)的排列\(A_i\)，你需要将其分成\(k\leq f(n)\)段递增或递减的序列并输出方案（不要求\(k\)最小，只需\(\leq f(n)\)）。
\(T,\sum n\leq10^5\)。
\(Solution\)
首先考虑\(f(n)\)是多少。
随便找一些排列比如题解中的这个：\(\{1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11\}\)，\(k=5\)，能发现\(k\)是最大的满足\(\frac{i(i+1)}{2}\leq n\)的正整数\(i\)。
所以我们猜\(f(n)=k\)，其中\(k\)是最大的满足\(\frac{k(k+1)}{2}\leq n\)的正整数。
事实上确实可以证明。也就是对于任意\(n<\frac{k'(k'+1)}{2}\)，总能将序列分成不超过\(k'-1\)个单调子序列。
设\(LIS\)为此时的最长上升子序列，若\(|LIS|\geq k'\)，删掉\(LIS\)，则此时\(n-|LIS|<\frac{k'(k'+1)}{2}-k'=\frac{(k'-1)k'}{2}\)，显然是一个同样的规模更小的问题。
否则\(|LIS|\leq k'-1\)，由\(Dilworth\)定理，\(最小链覆盖=最长反链\)，本题中就是\(下降子序列个数=最长上升子序列长度\leq k'-1\)。（对于\(i<j,A_i>A_j\)，连单向边\(i\to j\)，则最长反链即\(LIS\)，任意一条路径即下降子序列）
所以此时可以将序列分成不超过\(k'-1\)个下降子序列。
证完了。。也是够神。。不知道别的可能的做法，懒得看了。。
输出\(|LIS|\)个下降子序列时，令\(f[i]\)表示以\(i\)结尾的\(LIS\)长度，把\(f[i]\)相同的位置划分到同一个子序列中就可以了。（显然这些数是递减的）
复杂度\(O(n\sqrt{n}\log n)\)（需要\(O(\sqrt{n})\)次\(LIS\)）。
//358ms 3600KB
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5;
int tot,A[N],f[N];
std::vector<int> ans[N];
struct BIT
{
int n,t[N];
#define lb(x) (x&-x)
inline int Query(int p)
{
int res=0;
for(; p; p^=lb(p)) res=std::max(res,t[p]);
return res;
}
inline void Modify(int p,int v)
{
for(; p<=n; p+=lb(p)) t[p]=std::max(t[p],v);
}
inline void Clear(int p)
{
for(; p<=n; p+=lb(p))
if(!t[p]) break;
else t[p]=0;
}
}T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now;
}
void Solve(int n)
{
static bool vis[N];
int mx=0;
for(int i=1; i<=n; ++i) mx=std::max(mx,f[i]=T.Query(A[i]-1)+1), T.Modify(A[i],f[i]);
for(int i=1; i<=n; ++i) T.Clear(A[i]);
int l=1,r=sqrt(n*2),mid;
while(l<r)//k(k+1)/2<=n (k+1)(k+2)/2>n
if(mid=l+r>>1,mid*(mid+1)>n*2) r=mid;//可能会爆int。。但k的上界是sqrt(2n)。
else l=mid+1;
int k=l;
if(mx>=k)
{
++tot;
for(int i=n,now=mx,v=N; i; --i)
if(f[i]==now && A[i]<v)
--now, v=A[i], vis[i]=1, ans[tot].push_back(A[i]);
std::reverse(ans[tot].begin(),ans[tot].end());
int cnt=0;
for(int i=1; i<=n; ++i)
if(!vis[i]) A[++cnt]=A[i];
else vis[i]=0;
if(cnt) Solve(cnt);
}
else
{
for(int i=1; i<=n; ++i) ans[tot+f[i]].push_back(A[i]);
tot+=mx;
}
}
int main()
{
for(int Tot=read(); Tot--; )
{
const int n=read(); T.n=n;
for(int i=1; i<=n; ++i) A[i]=read();
tot=0, Solve(n);
printf("%d\n",tot);
for(int i=1; i<=tot; ++i,putchar('\n'))
{
printf("%d",ans[i].size());
for(int j=0,l=ans[i].size(); j<l; ++j) printf(" %d",ans[i][j]);
ans[i].clear();
}
}
return 0;
}
F.Alex and a TV Show(bitset)
\(Description\)
有\(n\)个多重集合，初始都为空。有\(q\)次操作，操作共四种：
\(1\ x\ v\)：将第\(x\)个集合赋值为\(\{v\}\)。
\(2\ x\ y\ z\)：把第\(x\)个集合设为第\(y\)个集合与第\(z\)个集合的并。
\(3\ x\ y\ z\)：把第\(x\)个集合设为\(\{\gcd(a,b)|a\in y,b\in z\}\)。
\(4\ x\ v\)：询问第\(x\)个集合中，数字\(v\)出现次数模\(2\)后的值。
\(n\leq10^5,\ q\leq10^6\)，出现的所有数字均为正整数且\(\leq7000\)。
\(Solution\)
先考虑第三个类似卷积的操作如何处理。题解用到了类似\(FFT\)的方法，将“卷积”转化成对应位置的“点值”分别进行运算。
在\(x\)位置处，不去维护数字\(x\)的出现次数，而是维护\(x\)所有倍数的出现次数。这样就可以对不同位置的点值分别维护“\(\gcd\)卷积”啦。
比如\(y\)集合中\(x\)的倍数有\(a\)个，\(z\)集合中\(x\)的倍数有\(b\)个，那么“卷积”之后\(x\)的倍数就有\(a*b\)个（而且这个\(a,b\)与其它位置的值互不影响）。
具体实现，因为只需要判断奇偶性，拿一个大小为\(7000\)的\(bitset\ A_i\)。操作二就是\(A_y\ ^{\wedge}A_z\)（加），操作三就是\(A_y\&A_z\)（乘）。
但是查询的时候需要容斥：\(Ans=A_x-A_{2x}-A_{3x}+A_{6x}\)...注意到容斥系数只有\(\mu=1\)或\(-1\)，而\(1\equiv-1(mod\ 2)\)，所以直接把\(\mu(i*x)\neq0\)的这些位置上的值加起来就好，也就是全与起来再模\(2\)。
这样每次操作的复杂度都是\(O(\frac{7000}{w})\)。
//764ms 97900KB
#include <cstdio>
#include <cctype>
#include <bitset>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5,M=7001;
int mu[N];
std::bitset<M> A[N],ori[M],Mu[M];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now;
}
void Init()
{
static int P[M>>3];
static bool notP[M];
mu[1]=1;
for(int i=2,cnt=0; i<M; ++i)
{
if(!notP[i]) P[++cnt]=i, mu[i]=-1;
for(int j=1,v; j<=cnt&&(v=P[j]*i)<M; ++j)
{
notP[v]=1;
if(!(i%P[j])) break;
mu[v]=-mu[i];
}
}
}
int main()
{
Init();
for(int i=1; i<M; ++i)
for(int j=i; j<M; j+=i)
ori[j][i]=1, Mu[i][j]=(mu[j/i]!=0);
for(int n=read(),q=read(),x,y,z,v; q--; )
switch(read())
{
case 1: x=read(),v=read(),A[x]=ori[v]; break;
case 2: x=read(),y=read(),z=read(),A[x]=A[y]^A[z]; break;
case 3: x=read(),y=read(),z=read(),A[x]=A[y]&A[z]; break;
case 4: x=read(),v=read(),putchar(48+((A[x]&Mu[v]).count()&1)); break;
}
return 0;
}
G.Vladislav and a Great Legend(斯特林数 树形DP)
\(Description\)
给定一棵\(n\)个点的树和正整数\(k\)，定义\(f(s)\)表示使点集\(s\)中的点连通所需的最少边数。求\(\sum_{s\neq\varnothing}f(s)^k\)。
\(n\leq10^5,\ k\leq200\)。
\(Solution\)
依旧套路，把\(f(s)^k\)用第二类斯特林数（\(m^n=\sum_{k=0}^mC_m^kS(n,k)k!\)）展开：
\]
后面的\(\sum_{s\neq\varnothing}C_{f(s)}^i\)实际就是任选\(i\)条边，对应多少个点集。考虑树DP去算。
令\(f[i][j]\)表示选中的所有点的\(LCA\)为\(i\)时，从这些生成树中选了\(j\)条边对应的点集有多少个（生成树包括\(i\to fa[i]\)这条边，因为不在这个时候计算这条边好像不好做...表示不会）。
每个点初始化\(f[x][0]=2\)（可以在也可以不在点集中）。合并子树的时候就是树形背包，\(f'[x][i+j]=\sum_{v=son[x]}f[x][i]*f[v][j]\)。
合并完子树的贡献后，再算上\(x\to fa[x]\)这条边的贡献（可能出现在边集中），即\(f[x][i]\)+=\(f[x][i-1]\)。
此时会有不合法的情况：\(x\)子树外没有选点，但选了\(x\to fa[x]\)这条边。
减去合并完子树后时的\(f\)的贡献就行了，即\(Ans_i\)-=\(f[x][i-1]\)。
还有要注意\(f[x][0]\)是包括空集这一种情况的（不选任何点），但是又不能直接去掉（直接--\(f[x][0]\)），组合的时候可能用到。
所以在用\(f[x][0]\)更新其它值时注意把这种情况去掉：\(Ans_1\)再加上这个\(1\)，用\(x\to fa[x]\)的边更新后的\(f[x][1]\)要减掉这个\(1\)。
还可以把\(i!\)乘进去，就成了维护下降幂。。不想看了。。
//467ms 90200KB
#include <cstdio>
#include <cctype>
#include <algorithm>
#define mod 1000000007
#define gc() getchar()
#define Mod(x) x>=mod&&(x-=mod)
#define Add(x,v) (x+=v)>=mod&&(x-=mod)
typedef long long LL;
const int N=1e5+5;
int K,Enum,H[N],nxt[N<<1],to[N<<1],f[N][203],Ans[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now;
}
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int fa)
{
static int sz[N],g[N];
f[x][0]=2, sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa)
{
DFS(v,x);
for(int a=0,l=std::min(sz[x]-1,K); a<=l; ++a)
for(int b=0; b<=sz[v]&&a+b<=K; ++b)//注意这里不是到sz[v]-1（还有v->fa[v]这条边）
Add(g[a+b],1ll*f[x][a]*f[v][b]%mod);
sz[x]+=sz[v];
for(int j=0,l=std::min(sz[x]-1,K); j<=l; ++j) f[x][j]=g[j], g[j]=0;
}
if(x!=1)
{
for(int i=1,l=std::min(sz[x],K); i<=l; ++i) Add(Ans[i],mod-f[x][i-1]);//注意这里也不是sz[x]-1。。（不写这个取min更保险一些）
++Ans[1];
}
else for(int i=0,l=std::min(sz[1]-1,K); i<=K; ++i) Add(Ans[i],f[1][i]);
for(int i=std::min(sz[x],K); i; --i) Add(f[x][i],f[x][i-1]);
Add(f[x][1],mod-1);
}
int main()
{
static int S[203][203];
const int n=read(),K=read(); ::K=K;
for(int i=1; i<n; ++i) AE(read(),read());
DFS(1,1);
S[0][0]=1;
for(int i=1; i<=K; ++i)
for(int j=1; j<=i; ++j) S[i][j]=S[i-1][j-1]+1ll*S[i-1][j]*j%mod, Mod(S[i][j]);
LL ans=0;
for(int i=0,fac=1; i<=K; ++i) ans+=1ll*S[K][i]*fac%mod*Ans[i]%mod, fac=1ll*fac*(i+1)%mod;
printf("%I64d\n",ans%mod);
return 0;
}
H.
不想做了。。
咕咕