首页 > 其他分享 >2022 省队二轮集训培训日记-Day5

2022 省队二轮集训培训日记-Day5

时间：2023-07-13 21:11:59浏览次数：33  
标签：int Day5 long 2022 Print x0 Check 省队 define

模拟赛

T1

非常简单的构造，但是我忘了判断 $m=2$ 和对只有一个点特判的输出错误，导致挂成 $20$。

具体思路，考虑欧拉路径只能有两个奇点，但是每条边上中间的都是奇点，所以我们需要删掉边缘的一些边，直到剩下两个奇点，然后对于 $n,m$ 都是偶数，或者一个偶数一个奇数，或者两个都是奇数来分别构造。

代码：

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define P pair<int,int>
#define mp make_pair
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define fi first
#define se second
#define N number
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x){
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f*=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	x*=f;
}

int n,m,x0,Y0,x1,Y1,all;
bool op;

inline void Print(){
	if(op) printf("%d %d\n",x0,Y0);
	else printf("%d %d\n",Y0,x0);
}
inline bool Check(){
	if(x0==x1&&Y0==Y1) return 1;return 0;
}

namespace Subtask1{
	inline void Solve(){
		if(n==2&&m==2) printf("4\n");
		else printf("%d\n",all-(n+m-5));
		op=1;
		if(n>m)op=0,swap(n,m); 
		x0=n-1;Y0=1;Print();
		while(x0){
			Y0--;Print();x0--;Print();Y0++;Print();if(!x0) break; x0--;Print();
		}
		assert(x0==0&&Y0==1);
		for(int i=1;i<=n-1;i++){
			if(i&1) x1=i,Y1=m-1;
			else x1=i,Y1=1;
			if(i&1){
				while(!Check()){
					x0++;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
					x0--;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
				}
			}
			else{
				while(!Check()){
					Y0--;Print();if(Check()) break;
					x0++;Print();if(Check()) break;
					Y0--;Print();if(Check()) break;
					x0--;Print();if(Check()) break;
				}
			}
		}
		if(n!=2||m!=2) Y0--,Print();
	}
}

namespace Subtask2{
	inline void Solve(){
		printf("%d\n",all-(n+m-5));
		if(n&1) swap(n,m),op=0;
		else op=1;
		x0=n-1;Y0=1;Print();Y0--;Print();
		for(int i=n-2;i>=0;i--){
			if(i&1) x1=i,Y1=0;
			else x1=i,Y1=m-1;
//			printf("x1=%d Y1=%d\n",x1,Y1);
			if(i&1){
				while(!Check()){
					Y0--;Print();if(Check()) break;
					x0--;Print();if(Check()) break;
					Y0--;Print();if(Check()) break;
					x0++;Print();if(Check()) break; 
				}
			}
			else{
				while(!Check()){
					x0--;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
					x0++;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
				}
			}
		}
		Y0--;Print();
	}
}

namespace Subtask3{
	inline void Solve(){
		op=1;
		printf("%d\n",all-(m+n-4));
		x0=n-1;Y0=1;Print();
		x1=0;Y1=1;
		while(!Check()){
			x0--;Print();if(Check()) break;
			Y0--;Print();if(Check()) break;
			x0--;Print();if(Check()) break;
			Y0++;Print();if(Check()) break;
		}
		for(int i=1;i<=n-1;i++){
			if(i&1) x1=i,Y1=m-1;
			else x1=i,Y1=1;
			if(i&1){
				while(!Check()){
					x0++;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
					x0--;Print();if(Check()) break;
					Y0++;Print();if(Check()) break;
				}
			}
			else{
				while(!Check()){
					x0++;Print();if(Check()) break;
					Y0--;Print();if(Check()) break;
					x0--;Print();if(Check()) break;
					Y0--;Print();if(Check()) break;
				}
			}
		}
		Y0--;Print();x0--;Print();
	}
}

int main(){
//	freopen("grid.in","r",stdin);
//	freopen("grid.out","w",stdout);
	read(n);read(m);all=m*(n-1)+n*(m-1);
	if(n==1&&m==1){
		puts("0\n0 0");return 0;
	}
	if(n==1||m==1){
		printf("%d\n",max(n-1,m-1));
		op=1;
		if(m==1) swap(n,m),op=0;
		x0=0;Y0=0;Print();rep(i,1,m-1) Y0=i,Print();return 0;
	}
	if(n%2==0&&m%2==0) Subtask1::Solve();
	else if((n&1)^(m&1)==1) Subtask2::Solve();
	else if((n&1)^(m&1)==0) Subtask3::Solve();
	return 0;
}

T2


wym 的做法非常巧妙。首先信息是非常多的，我们考虑一个信息对应一个结果，我们直接枚举毒药位置，然后暴力枚举哪只老鼠是在哪一轮死的，我们只需要保证，毒药位置不同，老鼠的死亡轮数序列也不同，然后对于每一轮，我们按照这个序列去给老鼠喂药。

正确性：设 $x$ 是毒药，那么 $x$ 对应的老鼠死亡序列一定是符合的，而一个老鼠只能在一局内死亡，或者不死亡，而任意两个不同位置的毒药序列不同，所以其它毒药序列一定是不符合的。

#include<bits/stdc++.h>
#include "poison.h"
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 10010
#define M 21
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int lim,nn,nm,nk,nt,tot;
int a[M],b[N][M];
int di[M];

inline void dfs(int k,int num){
    if(num>lim) return;
    if(k==nm){
        rep(i,0,nm-1) b[tot][i]=a[i];tot++;
        return;
    }
    if(tot==nn) return;
    rep(i,0,nt){
        a[k]=i;dfs(k+1,num+(i!=0));
        if(tot==nn) return;
    }
}

int solve(int n,int m,int k,int t){
    nn=n;nm=m;nk=k;nt=t;lim=m-k;
    dfs(0,0);
    // rep(i,0,n-1){
    //     rep(j,0,m-1) printf("%d ",b[i][j]);puts("");
    // }
    rep(i,1,t){
        rep(j,0,n-1)rep(o,0,m-1)if(b[j][o]==i&&!di[o]){
            feed(j,o);
        }
        int ans=done();
        rep(j,0,m-1){
            if(di[j]) continue;
            if(!((ans>>j)&1)){
                di[j]=i;
            }
        }
    }
    // rep(i,0,m-1) printf("di[%d]=%d\n",i,di[i]);
    rep(i,0,n-1){
        bool op=1;
        rep(j,0,m-1) if(di[j]!=b[i][j]) op=0;
        if(op){
            // printf("MyAns=%d\n",i);
            return i; 
        }
    }
    assert(0);
}

T3

推式子题，除掉 $p$ 的倍数的情况，我们根据费马小定理，原问题等价为有多少个 $a,b,c,d$ 满足 $a^b\equiv c^d$，其中 $1\le a,b,c,d\le p-1$，指数显然是这个取值范围，而底数不取 $0$ 是因为我们去掉整除的情况。指数难以处理，利用原根，我们可以得到 $ab\equiv cd \bmod p-1$，设 $f(m)$ 表示为 有多少 $a,b,c,d$ 满足 $ab\equiv cd\mod m$，同时利用中国剩余定理的唯一性，我们也可以证明 $f(x)$ 是积性的。所以我们现在需要考虑如何求出 $f(p^e)$ 即可。设 $c(t)$ 表示有多少个 $a,b$ 满足 $ab\equiv t \bmod m$，所以我们可以得到 $f(pe)=\sum\limits_{i=0} c^2(t)$。设 $a=Ap\alpha,b=Bp\beta,t=Tp^\theta$，由 $ab\equiv t$ 我们可以得到 $\alpha+\beta=\theta,AB=T \bmod p^{e-\theta}$，前者答案是 $\theta +1$，后者当 $A,B,T$ 都取在 $[1,p^{e-theta})$ 时解得数量为 $\phi2(p)$，但是 $A$ 的取值范围应该是 $[1,p^{e-\alpha})$，所以还需要乘上 $p^{\theta-\alpha}$，$B$ 同理。把这些都乘起来，待会和式，化简，可以得到一个非常简单的式子：

$$
f(pe)=p(p^e(p+1)-1)
$$

分解质因数即可。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N number
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int t;
ll p;

inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int Calc(int p,int e){
    // printf("p=%d e=%d\n",p,e);
    return 1ll*ksm(p,2*e-1,mod)*((1ll*ksm(p,e,mod)*(p+1)%mod-1+mod)%mod)%mod;
}
inline int Solve(ll x){
    ll i=2;int ans=1;
    for(;i*i<=x;i++){
        if(x%i) continue;
        int cnt=0;while(x%i==0) cnt++,x/=i;
        ans=1ll*ans*Calc(i,cnt)%mod;
    }
    if(x!=1) ans=1ll*ans*Calc(x%mod,1)%mod;
    return ans;
}
// ll Solve(ll n)
// {
// 	ll ans=1;
// 	for(ll i=2;i*i<=n;i++)
// 	{
// 		int num=0;
// 		while(n%i==0)
// 		{
// 			num++;
// 			n/=i;
// 		}
// 		if(num)ans=ans*Calc(i,num)%mod;
// 	}
// 	if(n!=1)ans=ans*Calc(n%mod,1)%mod;
// 	return ans;
// }
signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);
    while(t--){
        read(p);p--;
        int ans=Solve(p);
        p%=mod;ans=(ans+1ll*p*p%mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

标签：int,Day5,long,2022,Print,x0,Check,省队,define
From： https://www.cnblogs.com/HeNuclearReactor/p/17552178.html

相关文章

  • 2022 省队二轮集训培训日记-Day4
    模拟赛T1首先是曼哈顿距离到切比雪夫距离的转化，到原点曼哈顿距离为定值$a$的点组成的图形为一个斜正方形，且原点到顶点的距离为$a$，正方形边长为$\sqrt{2}a$，而到原点切比雪夫距离为$a$的点组成的图形为正正方形，且边长为$2a$，那么我们可以通过把平面坐标系旋转$45$度，并把......
  • 2022 省队二轮集训培训日记 Day1
    模拟赛这里的题解在出题人的基础上进行补充。T1原题链接首先忽略所有全开的子树（在这样的子树内我们不应该选择任何路径），选一个关的点作为根设$f_{u,0/1,0/1/2}$表示满足条件$u$最后是关/开的，子树内其它点最后都是开的子树内有0/1/2个路径端点，其它端点为$u$的最小......
  • 神策数据荣获亚马逊云科技“2022 年度独立软件开发（ISV）合作伙伴”称号
    近日，以“共见·价值成就”为主题的亚马逊云科技中国合作伙伴峰会成功举办。神策数据荣获亚马逊云科技“2022年度独立软件开发（ISV）合作伙伴”称号！“2022年度独立软件开发（ISV）合作伙伴”是亚马逊云科技与神策数据合作共赢的标志，它见证了双方依托亚马逊云科技ISV全成长路径，从能力构......
  • 2022ICPC杭州站 A （裴蜀 + 扩欧）
    题目链接：A题意：给定一个序列\(a\)，让序列加上一个等差序列，求出总和%$m$的最小值以及等差序列的\(s\)和公差\(d\)。思路：定义\(a\)序列总和为sum。则求解的答案为\((sum+n∗s+n∗(n+1)2∗d)\)%m的最小值。根据裴蜀定理得到原式等于\(sum+x∗gcd(n,n∗(n+1)/2)+y......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享（附原数据表）
    报告链接：http://tecdat.cn/?p=32044近年来，我国的跨境电子商务发展迅速，在过去五年中，其贸易额增长率达到了16.2%，已经成为稳定对外贸易的一支重要力量（查看文末了解报告PDF版本免费获取方式）。一方面，随着跨境电子商务的发展，跨境电子商务的监管政策得到了进一步的改善，跨境电子商务的规......
  • P8339 [AHOI2022] 钥匙 思考--zhengjun
    很容易考虑到计算贡献。该问题的关键在于——如何使得钥匙和宝箱的对应关系不算重Warning：有这样的二元对应关系，可以考虑一下转化为括号序列！转化为括号序列之后，发现路径上括号串的对应关系能够预处理出来。套个虚树和扫描线，就做完了。代码#include<bits/stdc++.h>using......
  • 助教工作总结（2022下路由交换技术上）
    一、助教工作的具体职责和任务1.线上线下给同学解答问题2.给老师布置的作业做一份尽可能标准且好理解的答案文档给同学们参考由于我大一提前学完了这门课程，所以作为刚学完且同班的同学，我更能体会到入门路由交换技术的疑难点。由于这门课的实验作业比较多，为了让......
  • 你省（福建）省队集训 Day5 T3 乱搞分析
    简要题意有\(1\leT\le10^6\)次询问，每次询问正整数\(x,p\)，\(p\)为素数，令\(n=xp^2\)，问是否存在三个正整数\(a,b,c\)，满足\(ab+bc+ca=n\)。有的话给出构造，否则输出\(-1\)。solution打表注意到只有\(n=4,18\)是无解的。打表namespaceDB{ constintN=1e5; struc......
  • 2022-2023 XCPC生涯总结
    参加比赛总结ICPC2022网络预选第一场2022.9.17队名沿用了去年yezi他们队的队名，这场因为有六级所以只有我们队和james_zhou队打.Caed开场过了CDH，开始写A，我一直在想L，240分钟左右我们分别把A和L过了，一起想G，Caed神中神最后把G想出来了。赛后知道是校排75，大概稳前100了，考虑到应......
  • CSP&NOIP2022游记
    今年是最后一年了，真的是来划水的了已经无欲无求了，只是最好能有个七级吧，要是没有也无所谓，反正我自始至终都是个OI废物已经完全回归whk咯谢幕之战，你会变好，还是更烂？冷知识：从去年CSP结束至今，Bosun在LG上只做了9题初赛前一天住了旅馆，周边玩了一下，感觉苏州古城区真的是一点意思也......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99