NOI Online R2 题解

由于错误的比赛策略、过度的水群和我早上不知道有这个比赛的残酷事实，我最多就拿200分了，惨败……比赛结束15分钟之后才写完C。无论如何，我似乎还是可以放一下代码，水一篇博客的？

所有代码未经证实。

第一题

#include <iostream>

using namespace std;
typedef long long ll;
int gcd(int a,int b){
	return b != 0?gcd(b,a%b):a;
}
int T,p1,p2,k;
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>p1>>p2>>k;
		int d = gcd(p1,p2);
		p1/=d;
		p2/=d;
		if(p1>p2)swap(p1,p2);
		int lim = (p2+p1-2)/p1;
		if(lim>=k){
			cout<<"No\n";
		}else{
			cout<<"Yes\n";
		}
	}
	return 0;
}

第二题

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
char buf[1000000],*p1,*p2;
inline bool isdigit(const char &ch){
	return ch>=48&&ch<=57;
}
inline char nextchar(){
	return p1==p2&&(p2=buf+fread(p1=buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline void getint(int &des){
	char ch=des=0;
	while(!isdigit(ch)&&ch!=EOF)ch=nextchar();
	while(isdigit(ch))des=des*10+ch-48,ch=nextchar();
}
using namespace std;
typedef long long ll;
const int mod = 1000000007;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b/2))) : sq(pow(a,b/2)));}

int n,A[1000010],V[1000010];
vector<int> po[1000010];
int d1[1000010],d2[1000010];
inline void update(const int &left,const int &right,const int &w){
	register int i;
	for(i=left;i<=1000005;i+=i&-i){
		d1[i]=add(d1[i],w);
		d2[i]=add(d2[i],mul(left,w));
	}
	for(i=right;i<=1000005;i+=i&-i){
		d1[i]=sub(d1[i],w);
		d2[i]=sub(d2[i],mul(right,w));
	}
}
inline int query(const int &left,const int &right){							//×ó±ÕÓÒ¿ª
	register int i;register int ans=0;
	for(i=left-1;i>=1;i-=i&-i){
		ans=sub(ans,(1ll*d1[i]*left-d2[i]+mod)%mod);
	}
	for(i=right-1;i>=1;i-=i&-i){
		ans=(1ll*d1[i]*right-d2[i]+ans+mod)%mod;
	}
	return ans;
}

int main() {
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	getint(n);
	for(int i=0;i<n;i++){
		getint(A[i]);V[i] = A[i];
	}
	sort(V,V+n);
	int m = unique(V,V+n)-V;
	for(int i=0;i<n;i++){
		A[i] = lower_bound(V,V+m,A[i])-V;
		po[A[i]].push_back(i);
	}
	for(int i=0;i<n;i++)reverse(po[i].begin(),po[i].end());
	int ans = 0,cu = 0;
	int cv = 0;
	for(int i=0;i<n;i++){
		if(i == po[A[i]].back()){
			cv+=1;
			update(i+1,n-1+2,1);
		}
		cu = add(cu,sq(cv));
	}
	for(int i=0;i<n;i++){
		ans = add(ans,cu);
		po[A[i]].pop_back();
		int r = po[A[i]].size()?po[A[i]].back():n;
		cu = sub(cu,mul(2,query(i+1,r-1+2)));
		cu = add(cu,r-i);
		update(i+1,r-1+2,mod-1);
	}
	cout<<ans<<endl;
	return 0;
}

第三题

设dp[i][j]为第i号点的子树中选取j对配对节点的选择方案数。

取，答案序列为，那么我们有：

   

于是使用二项式反演就可以求出答案了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}
const int N = 1000000;
int fac[N+10],invfac[N+10];


int C(int n,int m){
	if(n<0 || m<0 || m>n)return 0;
	return mul(fac[n],mul(invfac[m],invfac[n-m]));
}
int n,u,v;
vector<int> G[5050];
char ch[5050];
int dp[5050][5050],sz[5050],sc[5050][2];

void dfs(int num,int cf = -1){
	dp[num][0] = 1;
	for(auto ct:G[num]){
		if(ct == cf)continue;
		dfs(ct,num);
		vector<int> ndp(sz[num]+sz[ct]+2,0);
		for(int i=0;i<=sz[num];i++){
			for(int j=0;j<=sz[ct];j++){
				ndp[i+j] = add(ndp[i+j],mul(dp[num][i],dp[ct][j]));
			}
		}
		for(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];
		sz[num]+=sz[ct];
		sc[num][0]+=sc[ct][0];
		sc[num][1]+=sc[ct][1];
	}
	vector<int> ndp(sz[num]+2,0);
	for(int i=0;i<=sz[num];i++){
		if(!dp[num][i])continue;
		ndp[i] = add(ndp[i],dp[num][i]);
		int ca = sc[num][(ch[num]-'0')^1]-i;
		if(ca<0)break;
		ndp[i+1] = add(ndp[i+1],mul(dp[num][i],ca));
	}
	for(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];
	sz[num] +=1;
	sc[num][ch[num]-'0']+=1;
}
int main() {
	//freopen("match.in","r",stdin);
	//freopen("match.out","w",stdout);
	fac[0] = 1;
	for(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);
	invfac[N] = mpow(fac[N],mod-2);
	for(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);
	cin>>n;
	cin>>(ch+1);
	for(int i=1;i<n;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	for(int i=0;i<=n/2;i++){
		dp[1][i] = mul(dp[1][i],fac[n/2-i]);
	}
	for(int i=0;i<=n/2;i++){
		int cans = 0;
		for(int j=i;j<=n/2;j++){
			if((j-i)%2 == 1){
				cans = sub(cans,mul(C(j,i),dp[1][j]));
			}else{
				cans = add(cans,mul(C(j,i),dp[1][j]));
			}
		}
		cout<<cans<<" \n"[i == n/2];
	}
	return 0;
}