NOI Online 2020 Round2 爆零记_综合

这一切的一切，还是要从一只蝙蝠说起…
想不到CCF还要出NOI Online Round2…既然现在还算是公益活动就去凑个热闹~~顺便卡卡评测机~~呗…

day -2

2020.4.23 补题+写博客
~~为什么年级会选择这么奇怪的时间开会啊…~~
补了一下LSK聚佬出的模拟题，仔细想了T3发现是个水题…所以我为什么要用这么多时间来想T1啊qwq…
然后开始写博客…写到一半就不想写了qwq，感觉最近的题目应该以总结策略为主，博客可以少写点。

day -1

2020.4.23 试机+奇怪的知识总结
试机打了一下之前没写的T2-冒泡排序，感觉非常好写…但是听很多人说很容易挂掉，怕交上去WA了坏了心态测了半天数据…~~结果1A了~~。感觉其实上场的题目算是最不容易写挂的一类题了，以后还是要有点自信qwq。
然后总结了一些OL赛的奇怪的知识，~~感觉奇怪的知识又增加了好多~~。
there

day 1

迟到5分钟开始比赛。
先看T1，感觉很水，随便写了个做法过了样例。
后来的后来…突然发现有k=1的情况…~~差点签到失败~~
然后看T2，莫名感觉100pt很难，于是先看T3。
~~这是谁写的题面这么难理解。~~
于是又回去做T2…
T2想了半天会了没有平方的做法。然后根据平方的组合意义用树状数组瞎算贡献?不知道是不是对的???写着写着突然发现是区间更新=_=，于是换成了线段树。
写完了果然没过样例。于是去某~~用户群~~里打探情报…发现T1T2是个原题，全世界都A了T2…wzbl…
听大佬的~~AK感言~~感觉我的做法应该是错的…然后继续想T2正解，什么都没想出来。
大概离考试结束40min的时候突然发现我线段树写挂了 !! 改了之后就过了样例…
做完T2发现T3题目改了，感觉变简单了。~~但是我还是不会做~~。
显然考虑 $d p [x] [k]$ 表示在子树 $x$ 内选择 $k$ 对非平局的方案数。感觉很好dp，但是会发现对于平局的情况很难强制安排。
于是我们定义 $d p [x] [k]$ 表示在子树 $x$ 内选择 $\geq k$ 对非平局的方案数，然后容斥?
好像直接 $d p [x] [k] ? d p [x] [k + 1]$ 就可以了qwq。
想玩这些感觉时间不够了…得骗点分才行kk:)但是发现无论是 $O(2^m·m)$ 的状压dp还是 $O(n^3)$ 的暴力背包dp都比正解(?)难写，还是算了…
于是开始写正解(?)…考试结束前五分钟才写完，果然没过样例…
然后就是~~激动人心~~的交题时刻了。不愧是CCF，考试要结束的时候果然会崩溃。
期望得分: $0 + 0 + 0 = 0$
噫，我爆零了。
~~所以这场考试我到底在干些什么~~

总结

~~这个故事告诉我们:在线考试水群必死。~~
将近半年没写过容斥题…结果连最基本的容斥技巧都不会了。但是有关二项式反演的容斥系数我还真没学过，太菜了太菜了…~~感谢CCF又给了我一个被educated的机会。~~
由于这场考试频繁的改题还不给大样例，导致这一轮完全成为了FST大赛。虽说正式的考试pretest不会这么水，但是如果FST，代价将会是巨大的。所以以后还是要多检查代码，防止频繁的FST的情况。

题解

T1-涂色游戏(color)

~~相信大家都会做，我就不说了。~~

T2-子序列问题(sequence)

考场上我是用的组合意义做的…其实并不需要。
考虑当前从 $r ? 1$ 结束变为 $r$ 结束的变化，显然只会有 $A_r$ 对 $lst_{A_r},r]$ 产生为1的贡献。
如果你会线段树维护平方的话，这题就做完了。

线段树维护平方:
$∑i=lr(Ai+d)2=∑i=lrAi2+2Aid+d2=∑i=lrAi2+2d∑i=lrAi+(r?l+1)d\sum^{r}_{i=l}(A_i+d)^2=\sum^{r}_{i=l}A_i^2+2A_id+d^2=\sum^{r}_{i=l}A_i^2+2d\sum^{r}_{i=l}A_i+(r-l+1)d$
于是维护 $∑i=lrAi2,∑i=lrAi\sum^{r}_{i=l}A_i^2,\sum^{r}_{i=l}A_i$ 即可。

如果你~~像我一样~~把这东西给忘了，也不要紧。将平方拆成在一个区间中能选出的数的集合大小加上一个区间中能选出的数对大小乘2。同样可以推出来。

T3-游戏(match)

其实上面我已经口胡的差不多了。
定义 $f [x] [k]$ 表示子树内强制选 $k$ 对平局的方案数, $g [x] [k]$ 表示表示子树内恰好选 $k$ 对平局的方案数。其余的对我们随便安排。
~~dp是一个经典的背包问题，相信大家都会。~~
这是一个经典的容斥，接下来考虑容斥系数。
注意到
$f(i)=∑j=in(ji)g(j)f(i)=\sum^{n}_{j=i} \binom{j}{i}g(j)$
根据套路，我们用二项式反演就能得到容斥系数:
$g(i)=∑j=in(?1)j?i(ji)f(j)g(i)=\sum^{n}_{j=i} (-1)^{j-i}\binom{j}{i}f(j)$
这题就做完了。~~其实我觉得比T2还简单。~~
复杂度: $O(n^2)$

代码

T1-color

/*Lower_Rating*/
/*NOI Online 2*/
/*Long Long!! Long Long !!*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 800000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int T;
LL p1,p2,k;
LL gcd(LL a,LL b){
    if(!b)return a;return gcd(b,a%b);
}
int main(){
    //freopen("color.in","r",stdin);//freopen("color.out","w",stdout);T=read();while(T--){
    p1=read(),p2=read(),k=read();if(k==1){
    puts("No");continue;}if(p1>p2)swap(p1,p2);LL b=(p1+p2-gcd(p1,p2)-1)/p1;if(b>=k)puts("No");else puts("Yes");}
}

T2-sequence

/*Lower_Rating*/
/*NOI Online 2*/
/*Long Long!! Long Long !!*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 1000000007
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 2000000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,a[MAXN+5],pn,pos[MAXN+5],ans,tmp;
int p[MAXN+5];
struct Seg_tree{
    #define lc (x<<1)#define rc (x<<1|1)#define mid (l+r>>1)int sum[(MAXN<<2)+5],tag[(MAXN<<2)+5];void pushdown(int x,int l,int r){
    if(tag[x]){
    sum[lc]=add(sum[lc],mul(tag[x],mid-l+1)),tag[lc]=add(tag[lc],tag[x]);sum[rc]=add(sum[rc],mul(tag[x],r-mid)),tag[rc]=add(tag[rc],tag[x]);tag[x]=0;}}void pushup(int x){
    sum[x]=add(sum[lc],sum[rc]);}void Insert(int x,int l,int r,int L,int R,int c){
    if(r<L||R<l)return ;if(L<=l&&r<=R){
    sum[x]=add(sum[x],mul(r-l+1,c));tag[x]=add(tag[x],c);return ;}pushdown(x,l,r);Insert(lc,l,mid,L,R,c),Insert(rc,mid+1,r,L,R,c);pushup(x);}int Query(int x,int l,int r,int L,int R){
    if(r<L||R<l)return 0;if(L<=l&&r<=R)return sum[x];pushdown(x,l,r);return add(Query(lc,l,mid,L,R),Query(rc,mid+1,r,L,R));}
}T;int main(){
    //freopen("sequence.in","r",stdin);//freopen("sequence.out","w",stdout);n=read();for(int i=1;i<=n;i++)p[i]=a[i]=read();sort(p+1,p+n+1);pn=unique(p+1,p+n+1)-p-1;for(int i=1;i<=n;i++)a[i]=lower_bound(p+1,p+pn+1,a[i])-p;for(int i=1;i<=n;i++){
    ans=add(ans,mul(n-i+1,T.Query(1,1,n,pos[a[i]]+1,i)));tmp=add(tmp,mul(n-i+1,i-pos[a[i]]));T.Insert(1,1,n,pos[a[i]]+1,i,1);pos[a[i]]=i;}printf("%d",add(mul(ans,2),tmp));
}

T3-match

/*Lower_Rating*/
/*NOI Online 2*/
/*Long Long!! Long Long !!*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
using namespace std;#define LL long long
#define DB double
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
#define MAXN 5000
#define eps 1e-10
#define INF 1000000000
#define inf 100000000000000000LL
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int a,int b){
    return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){
    return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){
    return 1LL*a*b%MOD;}
int fst_pow(int a,int b){
    int res=1;while(b){
    if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;
}
int inv(int a){
    return fst_pow(a,MOD-2);}int n,m,siz[MAXN+5],cnt[MAXN+5],a[MAXN+5];
int fac[MAXN+5],ifac[MAXN+5],tmp[MAXN+5];
int dp[MAXN+5][MAXN+5];
char s[MAXN+5];
vector<int> G[MAXN+5];void prepare(){
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);ifac[n]=inv(fac[n]);for(int i=n-1;i>=0;i--)ifac[i]=mul(ifac[i+1],i+1);
}
int Comb(int a,int b){
    return mul(fac[a],mul(ifac[b],ifac[a-b]));
}
void link(int u,int v){
    G[u].push_back(v);G[v].push_back(u);
}
int dfs(int x,int fa){
    siz[x]=1,dp[x][0]=1,cnt[x]=a[x];for(int i=0;i<G[x].size();i++){
    int v=G[x][i];if(v==fa)continue;dfs(v,x);for(int j=0;j<=siz[x]+siz[v];j++)tmp[j]=0;for(int j=siz[x];~j;j--)for(int k=0;k<=siz[v];k++)tmp[j+k]=add(tmp[j+k],mul(dp[x][j],dp[v][k]));for(int j=0;j<=siz[x]+siz[v];j++)dp[x][j]=tmp[j];siz[x]+=siz[v],cnt[x]+=cnt[v];}for(int i=siz[x];i>=1;i--)if(a[x]){
    if(siz[x]-cnt[x]-i>=0)dp[x][i]=add(dp[x][i],mul(dp[x][i-1],siz[x]-cnt[x]-i+1));}else{
    if(cnt[x]-i>=0)dp[x][i]=add(dp[x][i],mul(dp[x][i-1],cnt[x]-i+1));}
}int main(){
    //freopen("match.in","r",stdin);//freopen("match.out","w",stdout);n=read(),m=n/2;prepare();for(int i=1;i<=n;i++)scanf("%1d",&a[i]);for(int i=1;i<n;i++){
    int u=read(),v=read();link(u,v);}dfs(1,0);for(int j=0;j<=m;j++)dp[1][j]=mul(fac[m-j],dp[1][j]);for(int i=0;i<=m;i++){
    int res=0;for(int j=i,p=0;j<=m;j++,p^=1)if(p)res=dec(res,mul(Comb(j,i),dp[1][j]));else res=add(res,mul(Comb(j,i),dp[1][j]));printf("%d\n",res);}
}