noip模拟42

A. 卷

发现乘积足以爆 \(long\) \(long\),但是数据随机,可以略忽略精度问题
一个快速降低数的级别的方法是取对数,由于有性质 \(log(x * y)=logx+logy\),合并时运算会很方便,于是转化成加和型最大独立集问题


B. 简单题

观察发现对于每个奇数,其 \(2\) 倍放在另一个集合,\(4\) 倍放在当前集合,以此类推
那么对于一条偶数长度的链,一定一半放在第一个集合,另一半放在第二个集合,对答案贡献乘 \(2\)
对于奇数长度的链,一定分成 \(len\) 和 \(len+1\) 两部分,那么这样最终答案一定有可行区间 \([l,r]\),那么多出 \(l\) 的部分一定是若干个奇数链造成的,而奇数链又是*组合,设总数为 \(tot\),答案为 \(\binom{tot}{m-l}\)
发现组合数数过大,模数很小,可以用 \(lucas\) 定理计算
对于计算奇偶链的个数,考虑枚举链长,这是 \(log\) 级别的,那么长度的 \(k\) 的链的起点范围为 \(\displaystyle[\frac{n}{2^{k-1}}+1,\frac{n}{2^k}]\),因为这个不分奇数,得除以 \(2\)

代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5005;
const int maxm=11000025;
const int mod=10000019;
int n,q,x,tot1,tot2,l,r,frac[maxm],inv[maxm],ans,ans1,len;
int po(int a,int b=mod-2){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
void pre(){
	frac[0]=1;
	for(int i=1;i<=mod-1;i++)frac[i]=frac[i-1]*i%mod;//,cout<<frac[i]<<" ";
	inv[mod-1]=po(frac[mod-1]);
//	cout<<frac[mod]<<" "<<inv[mod]<<endl;
	for(int i=mod-2;i>=0;i--)inv[i]=(i+1)*inv[i+1]%mod;//,cout<<inv[i]<<" ";
	return ;
}
int C(int n,int m){
	if(n<m)return 0;
	if(n==m)return 1;
	return frac[n]*inv[m]%mod*inv[n-m]%mod;
}
int lucas(int x,int y){
//	cout<<"hhh "<<x<<" "<<y<<endl;
	if(x==y)return 1;
	if(x<y)return 0;
	if(x<mod&&y<mod)return C(x,y);
	return lucas(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
signed main(){
//	cout<<po(2);
	n=read();
	q=read();
	pre();
//	cout<<C(6,2)<<endl;
	len=log2(n)+1;
//	cout<<len<<endl;
	for(int i=1;i<=len;i++){
//		cout<<i<<endl;
		int po1=pow(2,i-1);
		int po2=pow(2,i);
		int up=n/po1;
		int down=n/po2+1;
		if(down&1)down--;
		if(up&1)up++;
		int num=(up-down)/2;
		if(i&1){
			tot1+=num;
		}
		else tot2+=num;
		l+=num*(i/2);
	}
	
	r=l+tot1;
//	cout<<tot1<<" "<<tot2<<" "<<l<<" "<<r<<endl;
	ans1=po(2,tot2);
//	cout<<"ppp "<<endl;
	for(int i=1;i<=q;i++){
		x=read();
		if(x<l||x>r){
			puts("0");
			continue;
		}
		ans=ans1*lucas(tot1,x-l)%mod;
		printf("%d\n",ans);
	}
	return 0;
}

C. 粉丝

这道题本质是自然数拆分,运用根号分治优化
首先自然数拆分有两种 \(dp\) 方法:
设 \(f[i][j]\) 表示 \(dp\) 到 \(i\) 这个数和为 \(j\) 的方案数,\(f[i][j]=f[i-1][j]+f[i][j-i]\)
\(g[i][j]\) 表示分成了 \(i\) 个数字,和为 \(j\) 的方案数
发现两种 \(dp\) 单独做都是 \(n^2\) 的
但是观察第一种 \(dp\) 的状态是 \(dp\) 到 \(i\) 这个数,值域越小复杂度越低
第二种状态是分成 \(i\) 个数,值域越大复杂度越低
于是在 \(\sqrt n\) 处分治,值域小的部分用第一种,大的部分用第二种,总复杂度为 \(n\sqrt n\)
注意第二种 \(dp\) 其实是每个选了了的数都已经以 \(sq\) 为基准了,那么实际的总和需要加上 \(num*sq\),这个合并时用 \(num\) 记录

代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int x,y,n,mod,f[maxn],g[maxn],sum[maxn],sq,ans;
int dp(int limit){
	memset(f,0,sizeof f);
	memset(g,0,sizeof g);
	memset(sum,0,sizeof sum);
	ans=0;
	f[0]=1;
	sq=max((int)sqrt(n),limit);
	for(int i=limit;i<sq;i++){
		for(int j=i;j<=n;j++){
			f[j]+=f[j-i];
			f[j]%=mod;
		}
	}
	g[0]=1;
	sum[0]=1;
	for(int i=1;i<=n/sq;i++){
		int t=i*sq;
		for(int j=i;j+t<=n;j++){
			g[j]=(g[j]+g[j-i])%mod;
		}
		for(int j=0;j+t<=n;j++){
			sum[j+t]+=g[j];
			sum[j+t]%=mod;
		}
	}
	for(int i=0;i<=n;i++){
		ans=(ans+f[i]*sum[n-i]%mod)%mod;
	}
	return ans;
}
signed main(){
	cin>>x>>y>>n>>mod;
	cout<<(dp(x)-dp(y+1)+mod)%mod;
	return 0;
}

D. 字符串

首先可以把两端本身就对称的部分砍掉,作为 \(A\) 和 \(E\)

上一篇:MySQL使用笔记(1)


下一篇:DVWA-7.4 SQL Injection(SQL注入)-Impossible