over 1 year ago

嘛。。成功的被自己的flag玩残了。。
t1
给出l,r(l,r<=10^9,r-l+1<=10^5),n(<=10^5),m(<=10^9)
询问从l到r可重复选n个数gcd为m的方案数
容斥搞搞就行辣(莫名其妙wa两点)
p.s.暴力分多了10分不开心
t2
n(<=1000)个点,m(<=100000)条边 每个点有流量 每条边有边权
问从1到n只走最短路的最大流
跑一遍最短路拆点最大流就好了。。(有个地方long long打成int掉了6个点TAT)
p.s.出题人不卡spfa不开心
t3
有n个时刻(<=10^6),m(<=10^6)个任务,每个任务有l,r,d表示开始时间结束时间重要程度,其中d<=10^7
强制在线询问某个时刻重要程度前k小任务重要度和
线段树合并搞搞就行了。。
t4


看到这样的题面就觉得很慌 然后就看错题了 以为要解一个x出来 然后就出于人类本能弃疗了。。
后来看看,,不就是个暴力二项式嘛。。
现场做这题码力真是没话说

include

include

include

include

include

define N 8100

define mmod 10000

define LL long long

using namespace std;
struct node{LL len,a[N],zf;}n,m,res,z[10],f[10],c,tt,b[10],g,gt,rest;
char s[N];
LL t,cf,num,len,a[10],k;
void read(node &a)
{
scanf("%s",s+1);
len=strlen(s+1);
cf=1;num=0;
for(LL i=len;i>=1;i--)
{
num+=cf*(s[i]-'0');
cf*=10;
if(cf>=10000)
{
a.a[++a.len]=num;
cf=1;
num=0;
}
}
if(num) a.a[++a.len]=num;
}
void clear(node &a)
{
for(LL i=1;i<=a.len;i++) a.a[i]=0;
a.len=a.zf=0;
}
void mns(node &a,node &b,node &c)
{
clear(c);
c.len=a.len;
for(LL i=1;i<=c.len;i++) c.a[i]=a.a[i]-b.a[i];
for(LL i=1;i<=c.len;i++)
if(c.a[i] LL i=c.len;
while(c.a[i]==0 && i>0) i--;
c.len=i;
}
void dvd(node &a,LL b)
{
for(LL i=a.len;i>=1;i--)
{
a.a[i-1]+=(a.a[i]%b)mmod;
a.a[i]/=b;
}
LL i=a.len;
while(a.a[i]==0 && i>=1) i--;
a.len=i;
}
LL qmod()
{
LL g[3][3],t[3][3],a[3][3];
a[1][1]=1234;a[1][2]=1;
a[2][1]=0;a[2][2]=1;
bool bo=0;
while(m.len>1 || m.a[1])
{
if(m.a[1]%2)
{
if(bo)
{
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
g[i][j]=0;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
for(LL k=1;k<=2;k++)
g[i][j]=(g[i][j]+t[i][k]*a[k][j])%3389;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
t[i][j]=g[i][j];
}
else
{
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
t[i][j]=a[i][j];
bo=1;
}
}
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
g[i][j]=0;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
for(LL k=1;k<=2;k++)
g[i][j]=(g[i][j]+a[i][k]*a[k][j])%3389;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
a[i][j]=g[i][j];
dvd(m,2);
}
return (t[1][1]+5678*t[1][2])%3389;
}
bool cmp(LL x)
{
if(z[x].len>f[x].len) return 1;
if(z[x].len for(LL i=1;i {
if(z[x].a[i]>f[x].a[i]) return 1;
if(z[x].a[i]<f[x].a[i]) return 0;
}
return 0;
}
void get(LL x)
{
f[x].a[1]+=a[x];
if(f[x].len==0) f[x].len=1;
for(LL i=1;i<=f[x].len;i++)
{
f[x].a[i+1]+=f[x].a[i]/mmod;
f[x].a[i]%=mmod;
}
if(f[x].a[f[x].len]) f[x].len++;
if(cmp(x)) {mns(z[x],f[x],b[x]);b[x].zf=-1;}
else {mns(f[x],z[x],b[x]);b[x].zf=1;}
}
void tms(node &a,node &b,node &c)
{
clear(c);
if(b.len==0 || b.len==1 && b.a[1]==0) return;
c.len=a.len+b.len-1;
for(LL i=1;i<=a.len;i++)
for(LL j=1;j<=b.len;j++)
c.a[i+j-1]+=a.a[i]
b.a[j];
for(LL i=1;i<=c.len;i++)
{
c.a[i+1]+=c.a[i]/mmod;
c.a[i]%=mmod;
}
LL i=c.len;
while(c.a[i+1])
{
i++;
c.a[i+1]+=c.a[i]/mmod;
c.a[i]%=mmod;
}
c.len=i;
}
void pls(node &a,node &b)
{
LL l=max(a.len,b.len);
for(LL i=1;i<=l;i++) a.a[i]+=b.a[i];
for(LL i=1;i<=l;i++)
{
a.a[i+1]+=a.a[i]/mmod;
a.a[i]%=mmod;
}
LL i=l;
while(a.a[i+1])
{
i++;
a.a[i+1]+=a.a[i]/mmod;
a.a[i]%=mmod;
}
a.len=i;
}
int main()
{
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
read(n);
scanf("%I64d",&t);
read(m);
mns(n,m,res);
k=res.a[1];
a[k]=qmod();
for(LL i=k-1;i>=0;i--)
a[i]=(a[i+1]*1234+5678)%3389;
for(LL i=0;i<=k;i++)
{
get(i);
c=tt=n;
n.a[1]--;
for(LL j=1;j<=n.len;j++)
if(n.a[j]<0) n.a[j]+=mmod,n.a[j+1]--;
else break;
if(n.a[n.len]==0) n.len--;
clear(g);
g.a[1]=t%mmod;
g.a[2]=t/mmod;
if(g.a[2]) g.len=2;
else g.len=1;
gt=g;
for(LL j=i+1;j<=k;j++)
{
dvd(c,j-i);
tms(c,b[i],res);
LL o=1;
if((j-i)%2) o=-o;
if(b[i].zf==-1) o=-o;
tms(res,g,rest);
if(o==1) pls(z[j],rest);
else pls(f[j],rest);
tt.a[1]--;
for(LL j=1;j<=tt.len;j++)
if(tt.a[j]<0) tt.a[j]+=mmod,tt.a[j+1]--;
else break;
if(tt.a[tt.len]==0) tt.len--;
tms(c,tt,res);
c=res;
tms(g,gt,res);
g=res;
}
}
printf("%I64d",b[k].a[b[k].len]);
for(LL i=b[k].len-1;i;i--) printf("%04d",b[k].a[i]);
return 0;
}
t5
..
p.s.暴力多了20分不开心
3题正解还没2题正解+暴力分高。。看来懒得打暴力真是药丸压。。

← 日常训练之dp/贪心 2016-4-1 YZX ROUND →