4
9
2015
0

CQOI2015

懒得码题解了= =反正都是水题

#include<stdio.h>
#include<iostream>
#include<map>
using namespace std;
const int Mod=1000000007;
typedef long long LL;
LL n,l,r,k,Ans,m,t[105];
LL sqr(LL k){return k*k%Mod;}
LL Pow(LL x,LL y){return y?(sqr(Pow(x,y>>1))*(y&1?x:1)%Mod):1;}
#define F(_) (Pow(r/(_)-(l-1)/(_),n)%Mod)
map<LL,int> H;
void Solve(int i,LL w,LL mu)
{if(i==m+1)
 {if(!H[w]) H[w]=1,Ans=(Ans+mu*F(k*w))%Mod;
  return;
 }
 Solve(i+1,w,mu);
 Solve(i+1,w*t[i],-mu);
}
void Work(LL w)
{if(w==1) return;
 m=0;
 for(LL i=2;i*i<=w;i++)
  if(w%i==0)
  {t[++m]=i;
   while(w%i==0) w/=i;
  }
 if(w>1) t[++m]=w;
 Solve(1,1,1);
}
int main()
{cin>>n>>k>>l>>r;H[1]=1;Ans=F(k);
 for(int i=(l-1)/k+1;i<=r/k;i++) Work(i);
 cout<<(Ans+Mod)%Mod;
 return 0;
}
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
namespace INPUT
{const int L=1<<15;
 char buf[L],*S,*T,ch;
 int f;
 char Gc()
 {if(S==T)
  {T=(S=buf)+fread(buf,1,L,stdin);
   if(S==T) return EOF;
  }
  return *S++;
 }
 void get(int& x)
 {for(ch=Gc();(ch<'0'||ch>'9')&&ch!='-';ch=Gc());
  if(ch=='-') f=-1,x=0;
  else f=1,x=ch^48;
  for(ch=Gc();ch>='0'&&ch<='9';ch=Gc()) x=x*10+(ch^48);
  x*=f;
 }
}
#define get(_) INPUT::get(_)
const int N=1105,M=500005;
typedef long long LL;
int n,m,w[N];
namespace Dinic
{int e[M],next[M],tot,G[N],Le[N],Q[N],A,B,f[M];
 void adde(int u,int v,LL c)
 {e[++tot]=v;f[tot]=c;next[tot]=G[u];G[u]=tot;
  e[++tot]=u;f[tot]=0;next[tot]=G[v];G[v]=tot;
 }
 bool bfs()
 {Q[A=B=1]=n+1;memset(Le,-1,n+n+1<<2);Le[n+1]=1;
  while(A<=B&&Le[n]==-1)
  {int u=Q[A++];
   for(int v,i=G[u];i;i=next[i]) if(Le[v=e[i]]==-1&&f[i]>0) Le[v]=Le[u]+1,Q[++B]=v;
  }
  return Le[n]!=-1;
 }
 int dfs(int u,int d)
 {if(u==n) return d;
  int w=0;
  for(int t,v,i=G[u];i&&w<d;i=next[i]) if(Le[v=e[i]]==Le[u]+1&&f[i]>0) t=dfs(v,min(d-w,f[i])),f[i]-=t,f[i^1]+=t,w+=t;
  if(!w) Le[u]=-1;
  return w;
 }
 LL Get_flow()
 {LL maxf=0;
  while(bfs()) maxf+=dfs(n+1,(1<<30)-1);
  return maxf;
 }
}
namespace Dij
{int G[N],e[M],next[M],L[M],tot;
 LL d[M];
 struct Lzz
 {LL Len;int x;
  Lzz(LL _,int __):Len(_),x(__){}
 };
 bool operator<(const Lzz& x,const Lzz& y){return x.Len>y.Len;}
 priority_queue<Lzz> Q;
 void adde(int u,int v,int l){e[++tot]=v;next[tot]=G[u];L[tot]=l;G[u]=tot;}
 void main()
 {for(int i=1;i<=n;i++) d[i]=10000000000000ll;
  Q.push(Lzz(0,1));d[1]=0;
  while(!Q.empty())
  {LL d2,dis=Q.top().Len;int u=Q.top().x;Q.pop();
   if(dis!=d[u]) continue;
   for(int i=G[u],v;i;i=next[i]) if((d2=L[i]+dis)<d[v=e[i]]) Q.push(Lzz(d[v]=d2,v));
  }
  Dinic::tot=1;
  for(int i=1;i<n;i++) Dinic::adde(i,i+n,w[i]);
  for(int i=1;i<=n;i++) for(int j=G[i];j;j=next[j]) if(L[j]+d[i]==d[e[j]]) Dinic::adde(i+n,e[j],(1<<30)-1);
 }
}
int main()
{get(n);get(m);
 for(int u,v,l,i=1;i<=m;i++) get(u),get(v),get(l),Dij::adde(u,v,l),Dij::adde(v,u,l);
 for(int i=1;i<=n;i++) get(w[i]);
 Dij::main();
 cout<<Dinic::Get_flow()<<endl;
 return 0;
}
#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int M=8000005,N=200005;
map<int,int> W;
vector<int> A[N],B[N];
int n,tot,Lc[M],Rc[M],sz[M],rt[N],m,Nc,T[N];
LL s[M],Ans=1;
#define Mid (l+r>>1)
void Add(int &x,int l,int r,int p,int Wb)
{int y=x;x=++tot;
 Lc[x]=Lc[y];Rc[x]=Rc[y];sz[x]=sz[y]+(Wb>0?1:-1);s[x]=s[y]+Wb;
 if(l!=r)
  if(p<=Mid) Add(Lc[x],l,Mid,p,Wb);
  else Add(Rc[x],Mid+1,r,p,Wb);
}
LL Ask(int x,int l,int r,int k){return k>=sz[x]?s[x]:l==r?k*(LL)T[l]:Ask(Lc[x],l,Mid,k)+(k>sz[Lc[x]]?Ask(Rc[x],Mid+1,r,k-sz[Lc[x]]):0);}
int main()
{scanf("%d%d",&n,&m);
 for(int i=1,l,r,k;i<=n;i++) scanf("%d%d%d",&l,&r,&k),A[l].push_back(k),B[r+1].push_back(k),W[k]=1;
 for(map<int,int>::iterator it=W.begin();it!=W.end();it++) T[it->second=++Nc]=it->first;
 for(int i=1;i<=m;i++)
 {rt[i]=rt[i-1];
  for(int j=0;j<A[i].size();j++) Add(rt[i],1,Nc,W[A[i][j]],A[i][j]);
  for(int j=0;j<B[i].size();j++) Add(rt[i],1,Nc,W[B[i][j]],-B[i][j]);
 }
 while(m--)
 {int x,k,a,b,c;scanf("%d%d%d%d",&x,&a,&b,&c);
  k=(Ans%c*a+b)%c+1;
  printf("%lld\n",Ans=Ask(rt[x],1,Nc,k));
 }
 return 0;
}
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef long long LL;
int a[3389];
struct BigNum
{LL t[5005],Len;
 BigNum(){Len=0;memset(t,0,sizeof t);}
 void INPUT()
 {static char s[5005];scanf("%s",s);
  int L=strlen(s);Len=(L-1)/4+1;
  for(int i=L-1,j=1,w=1;~i;i--)
  {t[j]+=w*(s[i]^48);w*=10;
   if(w==10000) w=1,j++;
  }
 }
 void OUTPUT()
 {if(Len==0) puts("0");
  else
  {printf("%lld",t[Len]);
   for(int i=Len-1;i;i--) printf("%04lld",t[i]);
   puts("");
  }
 }
}K1,K2,N,M;
int t;
BigNum operator*(const BigNum& k,int w)
{if(w==0) return BigNum();
 BigNum X=k;
 for(int i=1;i<=X.Len;i++) X.t[i]*=w;
 int i;
 for(i=1;i<=X.Len||X.t[i];i++) X.t[i+1]+=X.t[i]/10000,X.t[i]%=10000;
 X.Len=i-1;
 return X;
}
BigNum operator*(const BigNum& a,const BigNum& b)
{if(a.Len==0||b.Len==0) return BigNum();
 BigNum X;X.Len=a.Len+b.Len-1;
 for(int i=1;i<=a.Len;i++)
  for(int j=1;j<=b.Len;j++)
   X.t[i+j-1]+=a.t[i]*b.t[j];
 int i;
 for(i=1;i<=X.Len||X.t[i];i++) X.t[i+1]+=X.t[i]/10000,X.t[i]%=10000;
 X.Len=i-1;
 return X;
}
BigNum operator/(const BigNum& k,int w)
{BigNum X=k;
 int i,d=0;
 for(i=X.Len;i;i--) X.t[i]+=d*10000,d=X.t[i]%w,X.t[i]/=w;
 while(X.t[X.Len]==0&&X.Len>0) X.Len--;
 return X;
}
BigNum operator+(const BigNum& a,const BigNum& b)
{BigNum X;X.Len=max(a.Len,b.Len);
 for(int i=1;i<=X.Len;i++) X.t[i]=a.t[i]+b.t[i];
 int i;
 for(i=1;i<=X.Len||X.t[i];i++) X.t[i+1]+=X.t[i]/10000,X.t[i]%=10000;
 X.Len=i-1;
 return X;
}
BigNum operator+(const BigNum& a,const int b)
{BigNum X=a;X.t[1]+=b;
 int i;
 for(i=1;i<=X.Len||X.t[i];i++) X.t[i+1]+=X.t[i]/10000,X.t[i]%=10000;
 X.Len=i-1;
 return X;
}
int main()
{a[0]=1;
 for(int i=1;i<=3388;i++) a[i]=(1234*a[i-1]+5678)%3389;
 N.INPUT();cin>>t;M.INPUT();
 BigNum OrzLzz=M/3388*3388,Ans,X,Y;X.Len=X.t[1]=1;
 int k=(N.t[1]+10000-M.t[1])%10000,l=(M.t[1]+10000-OrzLzz.t[1])%10000;
 for(int i=0;i<=k;i++,l=(l+1)%3388)
 {Y=X*a[l];
  for(int j=1;j<=i;j++) Y=Y*t;
  Ans=Ans+Y;
  X=X*(M+i+1)/(i+1);
 }
 Ans.OUTPUT();
 return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=35;
map<int,int> H;
LL f[N][N][4][5005][2],n,m,Len[N][N],tot,K[N*N*N];
char s[N][N];
#define Add(_) H[_]=tot,K[tot++]=_
LL dfs(int x,int y,int k,int w,int flag)
{LL &S=f[x][y][k][w][flag];
 if(S!=-1) return S;
 if(x==n+1) S=w==0&&k==0;
 else if(y==m+1) S=flag?0:dfs(x+1,1,k,w,0);
 else if((1<<y)&K[w])
  if(flag==1||!s[x][y]) S=0;
  else S=dfs(x,y+1,k,H[K[w]^(1<<y)],1)+dfs(x,y+1,k,w,0);
 else if(flag==1)
  if(!s[x][y]) S=0;
  else S=dfs(x,y+1,k,w,1)+dfs(x,y+1,k,w,0);
 else
 {S=dfs(x,y+1,k,w,0);
  if(s[x][y]&&k&&y!=m) S+=dfs(x,y+1,k-1,H[K[w]|(1<<y)],0);
 }
 return S;
}
int main()
{cin>>n>>m;memset(f,-1,sizeof(f));
 for(int i=1;i<=n;i++)
 {scanf("%s",s[i]+1);
  for(int j=m;j>=1;j--) s[i][j]=s[i][j]=='.';
 }
 Add(0);
 for(int i=1;i<m;Add(1<<i),i++) for(int j=i+1;j<m;Add((1<<i)|(1<<j)),j++) for(int k=j+1;k<m;Add((1<<i)|(1<<j)|(1<<k)),k++);
 cout<<dfs(1,1,3,0,0)<<endl;
 return 0;
}
Category: My Oi,My Life | Tags: CQOI 逗比 求保佑 OrzLzz OrzCjy | Read Count: 589

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com