牛客NOIP暑期七天营-提高组3
-----------今天是被打爆的一天,T3就是用正解做的,但是好像zz了,只得了30分。-----------------
---------------- T1由于没判不合法的情况,也只有15分---------------------
---------------------果然是一个拿不到noip一等奖的人----------------------------
----------------------------毕竟noip都准备改名了?-------------------------
A:破碎的矩阵。
题意:给出N,M,表示有N*M的矩阵,然后给定每一行的异或和,每一列的异或和,求方案数。
思路:如果合法,方案数是pow(2,(N-1)*(M-1)),这个很好想,因为你确定了一个N*M的左上方(N-1)*(M-1)的矩阵后,最后一行一列可以反推,是唯一的。 不合法的情况是,异或和不为0;
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=2000010; int ans,N,M,Mod; ll x,a[maxn],b[maxn]; int qpow(int base,int num) { int res=1; while(num){ if(num&1) res=1LL*res*base%Mod; num>>=1; base=1LL*base*base%Mod; }return res; } void solve(int t) { int res=qpow(qpow(qpow(2,N-1),M-1),t); ans=1LL*res%Mod%Mod; } int main() { int T; scanf("%d",&T); while(T--){ ll xxx=0; scanf("%d%d%lld%d",&N,&M,&x,&Mod); rep(i,1,N) scanf("%lld",&a[i]),xxx^=a[i]; rep(i,1,M) scanf("%lld",&b[i]),xxx^=b[i]; if(xxx) puts("0"); else { int t=0; rep(i,0,60) if(x&(1LL<<i)) t++; solve(t); printf("%d ",ans); } } return 0; }
B:点与面。
题意:求W的个数。
思路:裸题,三次BIT即可。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=500010; const int Mod=998244353; int a[maxn],b[maxn],tot; ll L[maxn],R[maxn],ans,sum[maxn],res[maxn]; ll query(int x){ int res=0;while(x){ (res+=sum[x])%=Mod; x-=(-x)&x;} return res;} void add(int x,ll y){ while(x<=tot){ sum[x]+=y; if(sum[x]>=Mod) sum[x]-=Mod; x+=(-x)&x;} } int main() { int N; scanf("%d",&N); rep(i,1,N) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+N+1); tot=unique(b+1,b+N+1)-(b+1); rep(i,1,N) a[i]=lower_bound(b+1,b+tot+1,a[i])-b; rep(i,1,N) L[i]=i-1-query(a[i]),add(a[i],1); rep(i,1,tot) sum[i]=0; for(int i=N;i>=1;i--) R[i]=N-i-query(a[i]),add(a[i],1); rep(i,1,tot) sum[i]=0; rep(i,1,N) res[i]=1; rep(i,1,N) (res[i]*=query(a[i]-1))%=Mod,add(a[i],L[i]); rep(i,1,tot) sum[i]=0; for(int i=N;i>=1;i--) (res[i]*=query(a[i]-1))%=Mod,add(a[i],R[i]); rep(i,1,N) ans+=res[i]; printf("%lld ",ans%Mod); return 0; }