Wannafly挑战赛18

Wannafly挑战赛18

比赛地址：​​ BLOG：​​​ A.序列 发现0.5和-2是一对 共同出现偶数次即可抵消影响 1是凑数的

于是暴力dp dp[i][j][k]前i个位置选了j个0.5 k个-2的方案

#include#define ll long longusing namespace std;const int N=1e3+10;const int mod=1e9+7;int dp[2][N][N],n;inline int inc(int x,int v){ return x+v>=mod?x+v-mod:x+v;}int main(){ scanf("%d",&n); dp[0][0][0]=1;int pre=0,now=1; for (int i=0;i

实际上组合数学也可以搞 就枚举一下这个偶数到底是多少然后分别钦定一下-2和0.5的位置即可 参照大爷代码

#include using namespace std;#define ll long long#define inf 0x3f3f3f3f#define N 1010#define mod 1000000007inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}int n,C[N][N],ans=0;inline void inc(int &x,int y){x+=y;x%=mod;}int main(){// freopen("a.in","r",stdin); n=read()-1; for(int i=0;i<=n;++i) C[i][0]=1; for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; for(int i=0;i*4<=n;++i) inc(ans,(ll)C[n][2*i]*C[n-2*i][2*i]%mod); printf("%d\n",ans); return 0;}

B.随机数

设f[i]表示前i个数有奇数个1的概率，则

f[i+1]=f[i]∗(1−p)+(1−f[i])∗pf[i+1]=f[i]∗(1−p)+(1−f[i])∗p f[i+1]=(1−2p)f[i]+pf[i+1]=(1−2p)f[i]+p

然后十进制矩阵快速幂搞掉即可 每次倍增十次

就从比如10^10变成10^100

#include#define ll long longusing namespace std;const int mod=1e9+7;const int N=1e6+10;inline int ksm(ll b,int t){ static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}int a;char s[N];struct matrix{ int f[3][3];}tr,ans;inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline matrix multiply(const matrix &a,const matrix &b){ matrix c;memset(c.f,0,sizeof(c.f)); for (int i=1;i<=2;++i){ for (int j=1;j<=2;++j){ for (int k=1;k<=2;++k){ c.f[i][j]=inc(c.f[i][j],(ll)a.f[i][k]*b.f[k][j]%mod); } } }return c;}inline matrix ksm(matrix b,int t){ matrix res;memset(res.f,0,sizeof(res.f));res.f[1][1]=res.f[2][2]=1; for (;t;b=multiply(b,b),t>>=1) if (t&1) res=multiply(res,b);return res;}int main(){ freopen("b.in","r",stdin); scanf("%d",&a); scanf("%s",s+1); int inva=1ll*a*ksm(10000,mod-2)%mod; int invb=1-inva+mod;invb%=mod; tr.f[1][1]=invb;tr.f[1][2]=inva; tr.f[2][1]=inva;tr.f[2][2]=invb; int n=strlen(s+1);ans.f[1][1]=ans.f[2][2]=1; for (int i=n;i;--i){ int p=s[i]-'0';matrix tmp=tr; tmp=ksm(tmp,p); tr=ksm(tr,10);ans=multiply(ans,tmp); }printf("%d\n",ans.f[1][2]); return 0;}

c求全局到某个点距离即可 曼哈顿距离其实可以针对每个维度分开维护

菜鸡elijahqi代码写复杂了

#include#define ll long longusing namespace std;const int N=2200;const int mod=1e9+7;char s[N][N];int tot,n,m;int prex[N],prey[N],sufx[N],sufy[N];int nprex[N],nprey[N],nsufx[N],nsufy[N],inv;struct node{ int x,y;}pt[N*N];inline int ksm(ll b,int t){ static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}inline bool cmpx(const node &a,const node &b){ return a.x=mod?x+v-mod:x+v;}inline int dec(int x,int v){ return x-v<0?x-v+mod:x-v;}inline int calc(int x,int y){ int sum=0; for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j) if(s[i][j]=='1') sum=inc(sum,abs(x-i)+abs(y-j)); }return sum;}inline int gao(int x,int y){ int sum=0;sum=inc(sum,dec(1ll*x*nprex[x]%mod,prex[x])); sum=inc(sum,dec(1ll*(n-x)*nsufx[x]%mod,sufx[x])); sum=inc(sum,dec(1ll*y*nprey[y]%mod,prey[y])); sum=inc(sum,dec(1ll*(m-y)*nsufy[y]%mod,sufy[y])); //printf("%d\n",sum);printf("%d\n",calc(x,y)); //sum=calc(x,y); sum=(ll)sum*inv%mod;return sum;}int main(){ freopen("c.in","r",stdin); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%s",s[i]+1); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (s[i][j]=='1') pt[++tot].x=i,pt[tot].y=j; sort(pt+1,pt+tot+1,cmpx);int now=1;inv=ksm(tot,mod-2); for (int i=1;i<=n;++i){ prex[i]=prex[i-1];nprex[i]=nprex[i-1]; while(now<=tot&&pt[now].x<=i){ prex[i]+=pt[now].x;prex[i]%=mod; ++nprex[i];++now; } }now=tot;//printf("%lld\n",1ll*16*ksm(7,mod-2)%mod); for (int i=n;i;--i){ sufx[i]=sufx[i+1];nsufx[i]=nsufx[i+1]; while(now&&pt[now].x>=i){ sufx[i]+=n-pt[now].x;sufx[i]%=mod; ++nsufx[i];--now; } }sort(pt+1,pt+tot+1,cmpy); now=1; for (int i=1;i<=m;++i){ prey[i]=prey[i-1];nprey[i]=nprey[i-1]; while(now<=tot&&pt[now].y<=i){ prey[i]+=pt[now].y;prey[i]%=mod; ++nprey[i];++now; } }now=tot; for (int i=m;i;--i){ sufy[i]=sufy[i+1];nsufy[i]=nsufy[i+1]; while(now&&pt[now].y>=i){ sufy[i]+=m-pt[now].y;sufy[i]%=mod; ++nsufy[i];--now; } }int ans=0; for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j){ //printf("%d\n",gao(i,j)); ans^=gao(i,j); } }printf("%d\n",ans); return 0;}

icefox大爷的代码(icefox天下第一！

#include using namespace std;#define ll long long#define inf 0x3f3f3f3f#define N 2010#define mod 1000000007inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}int n,m,s1[N],s2[N],tot,f1[N],f2[N],ans=0;char s[N];inline void inc(int &x,int y){x+=y;x%=mod;}inline int ksm(int x,int k){ int res=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) res=(ll)res*x%mod;return res;}int main(){// freopen("a.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i){ scanf("%s",s+1); for(int j=1;j<=m;++j){ if(s[j]=='0') continue; s1[i]++;s2[j]++;++tot; } }for(int i=2;i<=n;++i) inc(f1[1],(i-1)*s1[i]); int tmp=s1[1]; for(int i=2;i<=n;++i){ f1[i]=f1[i-1]-(tot-tmp)+tmp;f1[i]=(f1[i]%mod+mod)%mod; tmp+=s1[i]; }for(int i=2;i<=m;++i) inc(f2[1],(i-1)*s2[i]); tmp=s2[1]; for(int i=2;i<=m;++i){ f2[i]=f2[i-1]-(tot-tmp)+tmp;f2[i]=(f2[i]%mod+mod)%mod; tmp+=s2[i]; }tot=ksm(tot,mod-2); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ ans^=(ll)(f1[i]+f2[j])*tot%mod; }printf("%d\n",ans); return 0;}

d题

设dp[t][i][j]表示t时间在i,j的方案且上一次没有移动

dp1[t][i][j][k]表示ti时间在i,j的方案且上一次移动方向i是k

#includeusing namespace std;int dp[2][202][202],dp1[2][202][202][4];int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};int n,m,T,X1,Y1,D,x2,y2;const int mod=1e9+7;inline int inc(int x,int v){ return x+v>=mod?x+v-mod:x+v;}inline int gao(int x,int y){ return max(abs(x-X1),abs(y-Y1));}int main(){ freopen("d.in","r",stdin); scanf("%d%d%d%d%d%d%d%d",&n,&m,&T,&X1,&Y1,&D,&x2,&y2); //X1=123321,Y1=123321; dp[0][1][1]=1;int pre=0,now=1; for (int t=0;tn||y<1||y>m) continue; dp1[now][x][y][k]=inc(dp1[now][x][y][k],dp[pre][i][j]); }dp[now][i][j]=inc(dp[now][i][j],dp[pre][i][j]); if (gao(i,j)>D){ int sum=0; for (int k=0;k<4;++k){ sum=inc(sum,dp1[pre][i][j][k]); } for (int k=0;k<4;++k){ int x=i+dx[k],y=j+dy[k]; if(x<1||x>n||y<1||y>m) continue; dp1[now][x][y][k]=inc(dp1[now][x][y][k],sum); }dp[now][i][j]=inc(dp[now][i][j],sum); }else{ //dp[now][i][j]=inc(dp[now][i][j],dp[pre][i][j]); for (int k=0;k<4;++k){ int x=i+dx[k],y=j+dy[k]; dp[now][i][j]=inc(dp[now][i][j],dp1[pre][i][j][k]); if(x<1||x>n||y<1||y>m) continue; dp1[now][x][y][k]=inc(dp1[now][x][y][k],dp1[pre][i][j][k]); } } } }pre^=1;now^=1; }int ans=0; for (int i=0;i<4;++i) ans=inc(ans,dp1[pre][x2][y2][i]); ans=inc(ans,dp[pre][x2][y2]);printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。