【比赛报告】2018.10.31牛客网线上赛[牛客网NOIP赛前集训营-提高组(第五场)] NOIP练习赛卷二十八
A.同余方程 位运算
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll m,l1,l2,r1,r2;
ll get(ll l,ll r){return r/m-(l==0?-1:(l-1)/m);}
ll cal(ll l,ll r)
{
ll ans=0;
for(ll i=l;i;i=i&(i-1))
for(ll j=r;j;j=j&(j-1))//枚举子集操作
{
ll x=i&-i,y=j&-j;//取出二进制下最低位的1
ll mx=max(x,y),mn=min(x,y),L=((i&(i-1)^(j&j-1))&(~(mx-1))),R=L+mx-1;//取出前半截
ans=(ans+get(L,L+mx-1)%mod*(mn%mod)%mod)%mod;
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&m);r1++;r2++;
printf("%lld\n",(cal(r1,r2)-cal(l1,r2)-cal(r1,l2)+cal(l1,l2)+2*mod)%mod);
return 0;
}
总结
各种位运算操作
B.旅游 最小生成树
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+10,mod=998244353;
inline int read()
{
int s=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
if(f)s=-s;return s;
}
int n,m,hd[N],tot,fa[N],val[N],deg[N];
ll Pow[N],ans;
struct Edge{
int v,nx;
ll w;
}e[N<<1];
inline int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline void add(int u,int v,ll w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].nx=hd[u];
hd[u]=tot;
}
void dfs(int u,int f,ll len)
{
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;ll w=e[i].w;
if(v!=f)dfs(v,u,w);
}
if(deg[u]%2)deg[u]++,deg[f]++,ans=(ans+len)%mod;
}
int main()
{
//freopen("in.txt","r",stdin);
n=read();m=read();
for(int i=1;i<=n;i++)
fa[i]=i;
Pow[0]=1;
for(int i=1;i<=m+1;i++)
Pow[i]=Pow[i-1]*2%mod;
ans=(Pow[m+1]-2)%mod;
for(int i=1,u,v,fu,fv;i<=m;i++)
{
u=read();v=read();deg[u]++;deg[v]++;fu=Find(u);fv=Find(v);
if(fu!=fv)
{
add(u,v,Pow[i]);add(v,u,Pow[i]);fa[fv]=fu;
}
}
dfs(1,0,0);printf("%lld\n",ans);
return 0;
}
总结
无
C.串串 组合数
#include<cstdio>
const int N=4e3+10,mod=1e9+7;
int a,b,c,d,fac[N],inv[N],ans;
int C(int n,int m)
{
if(n<0||m<0)return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
//freopen("in.txt","r",stdin);
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<N;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
for(int i=2;i<N;i++)inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
for(int i=2;i<N;i++)inv[i]=(1ll*inv[i-1]*inv[i])%mod;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(!c||!d)
{
printf("%d\n",C(a+b,a));return 0;
}
a-=c;b-=d;
for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
ans=(ans+1ll*C(i+j,i)*C(a-i+d-1,d-1)%mod*C(b-j+c-1,c-1)%mod)%mod;
printf("%d\n",1ll*ans*C(c+d,c)%mod);
return 0;
}
总结
避免重复很关键,以前也有一道类似的