格雷码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef unsigned long long ull;
ull n,k;
int main(void){
scanf("%llu%llu",&n,&k);
k^=(k>>1);
for(reg ull i=n;i>=1;--i)
if(k&(1ull<<(i-1)))
putchar('1');
else
putchar('0');
putchar('\n');
return 0;
}
括号树
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
const int MAXN=500000+5;
int n;
char val[MAXN];
int fa[MAXN];
int cnt,head[MAXN],to[MAXN],Next[MAXN];
ll f[MAXN];
ll sum[MAXN];
int top;
int S[MAXN];
inline void Add_Edge(reg int,reg int);
inline void DFS(reg int);
int main(void){
scanf("%d\n%s",&n,val+1);
for(reg int i=2;i<=n;++i){
scanf("%d",&fa[i]);
Add_Edge(fa[i],i);
}
DFS(1);
reg ll ans=0;
for(reg int i=1;i<=n;++i)
ans^=(ll)i*sum[i];
printf("%lld\n",ans);
return 0;
}
inline void Add_Edge(reg int u,reg int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
inline void DFS(reg int ID){
int flag=0;
if(val[ID]=='(')
S[++top]=ID;
else
if(top){
flag=S[top];
f[ID]=f[fa[flag]]+1;
--top;
}
sum[ID]=sum[fa[ID]]+f[ID];
for(reg int i=head[ID];i;i=Next[i])
DFS(to[i]);
if(flag)
S[++top]=flag;
else if(top)
--top;
return;
}
Emiya 家今天的饭
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 998244353ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
reg bool f=false;
reg char ch=getchar();
reg ll res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=100+5;
const int MAXM=2000+5;
int n,m;
ll a[MAXN][MAXM];
ll sum[MAXN];
ll dp[MAXN][MAXN<<1];
int main(void){
reg ll ans=1;
n=read(),m=read();
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=m;++j)
a[i][j]=read(),sum[i]=(sum[i]+a[i][j])%MOD;
for(reg int i=1;i<=n;++i)
ans=ans*((sum[i]+1)%MOD)%MOD;
--ans;
for(reg int i=1;i<=m;++i){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(reg int j=1;j<=n;++j)
for(reg int k=0;k<=(n<<1);++k){
dp[j][k]=(dp[j][k]+dp[j-1][k]*((sum[j]-a[j][i]+MOD)%MOD)%MOD)%MOD;
dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])%MOD;
dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i]%MOD)%MOD;
}
for(reg int j=n+1;j<=(n<<1);++j)
ans=(ans+MOD-dp[n][j])%MOD;
}
printf("%lld\n",ans);
return 0;
}
划分
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=40000000+5;
const int MAXM=100000+5;
const int MAXSIZE=11;
const int BASE=10000;
const int LGBASE=4;
struct BigNumber{
int len;
int unit[MAXSIZE];
inline BigNumber(void){
len=1;
memset(unit,0,sizeof(unit));
return;
}
inline BigNumber(reg ll a){
reg int i;
for(i=0;a!=0&&i<MAXSIZE;++i){
unit[i]=a%BASE;
a/=BASE;
}
len=i-1;
return;
}
inline void Fresh(void){
reg int i;
for(i=0;i<MAXSIZE-1;++i)
if(unit[i]>=BASE){
unit[i+1]+=unit[i]/BASE;
unit[i]%=BASE;
}
for(i=MAXSIZE-1;i>=0;--i)
if(unit[i]){
len=i;
break;
}
if(i==-1)
len=1;
return;
}
inline void Add(const BigNumber& a){
for(reg int i=0,l=max(len,a.len);i<=l;++i)
unit[i]+=a.unit[i];
Fresh();
return;
}
inline void Mul(const BigNumber& a){
BigNumber res;
for(reg int i=0;i<=len;++i)
for(reg int j=0;j<=a.len;++j)
res.unit[i+j]+=unit[i]*a.unit[j];
*this=res;
Fresh();
return;
}
inline void Opt(reg ll a){
BigNumber temp(a);
temp.Mul(temp);
this->Add(temp);
return;
}
inline void Print(void){
printf("%d",unit[len]);
for(reg int i=len-1;i>=0;--i)
printf("%0*d",LGBASE,unit[i]);
putchar('\n');
return;
}
};
int n,type;
int x,y,z,m;
int a[MAXN],b[MAXN];
int p[MAXM],l[MAXM],r[MAXM];
ll sum[MAXN];
BigNumber ans;
int pre[MAXN];
int head,tail,Q[MAXN];
inline ll Calc(reg int);
int main(void){
n=read(),type=read();
if(type==0)
for(reg int i=1;i<=n;++i)
a[i]=read();
else{
x=read(),y=read(),z=read(),b[1]=read(),b[2]=read(),m=read();
for(reg int i=1;i<=m;++i)
p[i]=read(),l[i]=read(),r[i]=read();
for(reg int i=1;i<=m;++i){
for(reg int j=p[i-1]+1;j<=p[i];++j){
if(j>=3)
b[j]=((ll)x*b[j-1]+(ll)y*b[j-2]+z)%(1<<30);
a[j]=b[j]%(r[i]-l[i]+1)+l[i];
}
}
}
for(reg int i=1;i<=n;++i)
sum[i]=sum[i-1]+a[i];
head=tail=1;
for(reg int i=1;i<=n;++i){
while(head<tail&&Calc(Q[head+1])<=sum[i])
++head;
pre[i]=Q[head];
while(head<tail&&Calc(Q[tail])>=Calc(i))
--tail;
Q[++tail]=i;
}
reg int now=n;
while(now){
ans.Opt(sum[now]-sum[pre[now]]);
now=pre[now];
}
ans.Print();
return 0;
}
inline ll Calc(reg int x){
return (sum[x]<<1)-sum[pre[x]];
}
近期评论