231112洛谷模拟赛

发布时间 2023-11-12 19:56:45作者: cztq

T1 种树

P9836 种树

只需要运用一些小学奥数即可解决

首先需要知道的一点是将 \(p_i\) 质因数分解后得到 \(p_i = \prod\limits_{j = 1}^m a_j^{k_j}\) ,则有 \(\prod\limits_{i = 1}^{m} (k_i+1)\) 个因数

则最终就是把所有的都再乘起来

考虑 \(w\) 分解后能造成什么影响,依据乘法分配律发现我们要把 \(w\) 的质因数都分给最小的 \(k_i\) (包括 \(k_i\)\(0\) 的情况)便可以做到答案最大

那么只需要开质因数种类数个堆维护最小值就可以了,代码也很好写

#include<bits/stdc++.h>
#define mod 998244353 
#define N 10010
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,k,w,cnt[N],mx[N],prime[N],tot,a[N],id[N];
priority_queue<int,vector<int>,greater<int> >q[N];
inline void init(){
	mx[0] = mx[1] = 1;
	for(int i = 2;i<=N-10;i++){
		if(!mx[i]) prime[++tot] = i,id[i] = tot,mx[i] = i;
		for(int j = 1;j<=tot&&i*prime[j]<=N-10;j++){
			mx[i*prime[j]] = prime[j];
			if(i%prime[j]==0) break;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	init();
	cin>>n>>k;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		while(a[i]!=1){
			cnt[id[mx[a[i]]]]++;
			a[i]/=mx[a[i]];
		}
		for(int j = 1;j<=tot;j++)
			if(cnt[j]){
				q[j].emplace(cnt[j]);
				cnt[j] = 0;
			}
	}
	while(k!=1){
		if(q[id[mx[k]]].size()<n){
			q[id[mx[k]]].emplace(1);
			k/=mx[k];
			continue;
		}
		int u = q[id[mx[k]]].top();q[id[mx[k]]].pop();
		u++;
		q[id[mx[k]]].emplace(u);
		k/=mx[k];
	}
	int ans = 1;
	for(int i = 1;i<=tot;i++){
		while(q[i].size()){
			ans = 1ll*ans*(q[i].top()+1)%mod;
			q[i].pop();
		}
	}
	cout<<ans;
	return 0;
}

T2 汪了个汪

P9837 汪了个汪

题解区第一篇的人类智慧太强了,我就不献丑了,正解是图论,不过不好写

反正我也只会那个人类智慧

#include<bits/stdc++.h>
#define N 4010
using namespace std;
int n,t,a[N][N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>t;
	for(int i = 1;i<=n;i++){
		int len = 1,st = (i&1)?(2*n-i+1)/2:(i>>1);
		for(int j = 1;j<=i;j++){
			cout<<st<<" ";
			if(j&1) st+=len;
			else st-=len;
			len++;
		}
		cout<<"\n";
	}
	return 0;
}

T3 挑战 NPC IV

P9838 挑战 NPC IV

这道题其实并不是很难想前面 \(52\) 分的,只需要考虑到对于 \(k = 2\) 时一定是与 \(k=1\) 的答案一样的就能拿到 \(32\)

对于 \(52\) 分来说,你只需要发现 \(n\ge 29\)\(k\le 10^{18}\) 的答案都一样就行

要拿到这几分,首先需要知道一个位置会被计算 \(i\times (n-i+1)\) 次,那么最小的排列就是大的放两端小的放中间

然后你可以发现对于对称的两个位置来说的贡献是一样的,那么就可以交换而使答案不变,所以第一个结论成立

又因为对于位置的排列交换之后会有非常多种,那么在计算一通后就可以发现第二个性质

计算过程去翻题解应该有

其实第二个并不需要花费 \(\mathcal O(n\log n)\) 的时间来模拟排列,只需要大力推导一个式子就可以 \(\mathcal O(\log n)\) 求出答案

那我们剩下的只有 \(n \le 28\) 时的情况了

然后就是一个极为炸裂的 \(dp\) ,对于这个逆天玩意,大家还是看题解吧 我不太懂

所以我写这么多有啥用

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,k,dp[15][8][5][3][2][6000],inv2 = (mod+1)>>1,inv6 = (mod+1)/6,cnt[70],fac[20];
int dfs(int x,int t1,int t2,int t3,int t4,int t5,int y){
	if(y<0||t1<0||t2<0||t3<0||t4<0||t5<0) return 0;
	if(!y) return t1||t2||t3||t4||t5?0:1;
	int &ans = dp[t1][t2][t3][t4][t5][y];
	if(~ans) return ans;
	ans = 0;
	int p = t1+t2+t3+t4+t5;
	p = p*(x-p+1);
	ans+=dfs(x,t1-1,t2,t3,t4,t5,y-p);
	ans+=dfs(x,t1,t2-1,t3,t4,t5,y-2*p);
	ans+=dfs(x,t1,t2,t3-1,t4,t5,y-3*p);
	ans+=dfs(x,t1,t2,t3,t4-1,t5,y-4*p);
	ans+=dfs(x,t1,t2,t3,t4,t5-1,y-5*p);
	return ans;
}
inline int calc(int x,int y){
	x%=mod;y%=mod;
	int ans = (x+1)*y%mod*(y+1)%mod*inv2%mod;
	ans-=y*(y+1)%mod*(2*y+1)%mod*inv6%mod;
	return (ans+mod)%mod;
}
inline int getans(int x){
	int y = (x>>1),ans = 0;
	for(int i = 0;i<60;i++)
		cnt[i+1] = x>>i;
	for(int i = 1;i<60;i++)
		cnt[i]-=cnt[i+1];
	if(x&1){
		ans = (y+1)%mod*((x-y+mod)%mod)%mod;
		cnt[1]--;
	}
	for(int i = 1;i<=60;i++){
		int t = cnt[i]>>1;y-=t;
		ans = (ans+2*(calc(x,y+t)-calc(x,y)+mod)%mod*i%mod)%mod;
		if(cnt[i]&1){
			ans = (ans+y%mod*((x-y+1+mod)%mod)%mod*i%mod)%mod;
			ans = (ans+y%mod*((x-y+1+mod)%mod)%mod*(i+1)%mod)%mod;
			cnt[i+1]--;y--;
		}
	}
	for(int i = 0;i<60;i++)
		cnt[i+1] = x>>i;
	for(int i = 1;i<60;i++)
		cnt[i]-=cnt[i+1];
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	fac[0] = 1;
	for(int i = 1;i<=15;i++)
		fac[i] = fac[i-1]*i;
	int T;cin>>T;
	while(T--){
		cin>>n>>k;
		int x = getans(n);
		if(n>28){
			cout<<x<<"\n";
			continue;
		}
		for(int i = 1;i<=5;i++)
			k = (k-1)/fac[cnt[i]]+1;
		memset(dp,0xff,sizeof(dp));
		while(1){
			int y = dfs(n,cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],x);
			if(y>=k){
				cout<<x<<"\n";
				break;
			}
			k-=y;x++;
		}
	}
	return 0;
}

T4 四暗刻单骑

不懂麻将

好吧这题咋都不好拿分,不说了