BC上粉记
打了24场，大号小号总计拿了四次68，做了无数次死，曾经上橙又掉回紫，也有全部题目都FST最后unrated的大起大落，一波7连涨冲上了首页~
BestCoder Round #47
这天大概是由于刮台风所以回家了，回家没啥事干就发现了有BC这东西，于是叫上黈力一起来打
开场开始摞T1傻逼题，但调了挺久，大概在快20分钟的时候A了
#include<cstdio>
#include<iostream>
using namespace std;
long long T,n,i,j,p,ans,now,a[2222];
int main(){
scanf("%I64d",&T);
while(T--){
scanf("%I64d%I64d",&n,&p);
ans=-1e16;
for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
for(i=1;i<=n;i++){
swap(a[i],p);
now=0;
for(j=1;j<=n;j++){
now=now+a[j];
ans=max(ans,now);
if(now<0)now=0;
}
swap(a[i],p);
}
printf("%I64d\n",ans);
}
}
然后发现T2更傻逼，40分钟的时候交了一发，没想到WA了，看了好久没看出错，黈力也觉得没错，结果最后数据错了，重测后就A了
#include<cstdio>
#include<algorithm>
#define N 111111
using namespace std;
long long T,n,m,i,j,ans,l1,l2,a[N],b[N];
bool cmp(long long x,long long y){return x>y;}
int main(){
scanf("%I64d",&T);
while(T--){
ans=0;
scanf("%I64d%I64d",&n,&m);
for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
for(i=1;i<=m;i++)scanf("%I64d",&b[i]);
sort(a+1,a+n+1,cmp);sort(b+1,b+m+1);
if(m>n)m=n;
if(n>m)n=m;
for(i=1;i<=n&&a[i]>b[i];i++){
ans+=a[i]-b[i];
}
printf("%I64d\n",ans);
}
}
然后黈力把T3也A了，就开始看T4，看了好久也不太会，黈力的方法我也没听懂，就弃疗了
最后开始准备HACK，开始HACK的时候发现怎么点也点不开别人的程序，后来换成IE浏览器点还死机了，重启后就差不多结束了。。【死于没有Chrome浏览器】
最后没×人竟然排到了RANK8，并拿到了ROOM1，没想到还有68元的奖励，不过没有支付宝只能累计了。。
不过令人气愤的是竟然只涨了170分，我看别人拿RANK30都涨200+，看来RP实在是不好
后来听黈力说要用Chorme，就下了个Chorme，果然可以点别人的程序啦。。
看了题解后发现1004也是SB题，线段树乱搞搞就行了，比赛后就写了下
#include<cstdio>
#include<cstring>
#define inf 1e15
#define N 222222
int T,n,m,i,w,l[N],r[N],lx[N],c[N],ans[N];
long long x1,y1,x2,y2,x[N],y[N],nx[N],ny[N],p[N];
struct T{int l,r;long long x,y,lx,ly;}t[N<<2];
long long max(long long x,long long y){if(x>y)return x;return y;}
void update(int x,int z){for(;x<=n;x+=x&-x)c[x]+=z;}
int query(int x){int tmp=0;for(;x;x-=x&-x)tmp+=c[x];return tmp;}
void pushdown(int k){
if(t[k].lx){
t[k<<1].x+=t[k].lx;
t[k<<1].lx+=t[k].lx;
t[k<<1|1].x+=t[k].lx;
t[k<<1|1].lx+=t[k].lx;
t[k].lx=0;
}
if(t[k].ly){
t[k<<1].y+=t[k].ly;
t[k<<1].ly+=t[k].ly;
t[k<<1|1].y+=t[k].ly;
t[k<<1|1].ly+=t[k].ly;
t[k].ly=0;
}
}
void pushup(int k){
t[k].x=max(t[k<<1].x,t[k<<1|1].x);
t[k].y=max(t[k<<1].y,t[k<<1|1].y);
}
void buildtree(int l,int r,int k){
t[k].l=l;t[k].r=r;
if(l==r){t[k].x=nx[l];t[k].y=ny[l];t[k].lx=t[k].ly=0;return;}
int mid=(l+r)>>1;
buildtree(l,mid,k<<1);
buildtree(mid+1,r,k<<1|1);
pushup(k);
}
void ins(int k,int x,int y,long long key,int fx){
pushdown(k);
if(x<=t[k].l&&t[k].r<=y){
if(fx)t[k].x+=key,t[k].lx+=key;
else t[k].y+=key,t[k].ly+=key;
return;
}
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(x>mid)ins(k<<1|1,x,y,key,fx);
else if(y<=mid)ins(k<<1,x,y,key,fx);
else ins(k<<1,x,mid,key,fx),ins(k<<1|1,mid+1,y,key,fx);
pushup(k);
}
void del(int k,int fx){
pushdown(k);
int l=t[k].l,r=t[k].r,mid=(k+r)>>1;
if(l==r){t[k].x=t[k].y=-inf;w=l;return;}
if(fx){if(t[k<<1].x>t[k<<1|1].x)del(k<<1,fx);else del(k<<1|1,fx);
}else{if(t[k<<1].y>t[k<<1|1].y)del(k<<1,fx);else del(k<<1|1,fx);}
pushup(k);
}
void go(int xx,int yy,int u){
memset(c,0,sizeof(c));
for(i=1;i<=4*n;i++)t[i].x=t[i].y=-inf,t[i].lx=t[i].ly=0;
for(i=1;i<=n;i++)if(x[i]<=xx&&y[i]<=yy)update(i,1),nx[i]=x[i],ny[i]=y[i];else nx[i]=ny[i]=-inf;
buildtree(1,n,1);
for(i=1;i<=m;i++){
if(lx[i]==1){
ins(1,l[i],r[i],p[i],1);
while(t[1].x>xx)del(1,1),update(w,-1);
}else if(lx[i]==2){
ins(1,l[i],r[i],p[i],0);
while(t[1].y>yy)del(1,0),update(w,-1);
}else ans[i]+=u*(query(r[i])-query(l[i]-1));
}
}
int main(){
scanf("%d",&T);
while(T--){
memset(ans,0,sizeof(ans));
scanf("%d%I64d%I64d%I64d%I64d",&n,&x1,&y1,&x2,&y2);
for(i=1;i<=n;i++)scanf("%I64d%I64d",&x[i],&y[i]);
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d",&lx[i]);
if(lx[i]<=2)scanf("%d%d%I64d",&l[i],&r[i],&p[i]);
else scanf("%d%d",&l[i],&r[i]);
}
go(x2,y2,1);go(x1-1,y1-1,1);go(x2,y1-1,-1);go(x1-1,y2,-1);
for(i=1;i<=m;i++)if(lx[i]==3)printf("%d\n",ans[i]);
}
}
BestCoder Round #48
这场觉得很多大牛都在打NOI，就想来虐虐大学狗，没想到被大学狗虐了
首先3分钟秒了T1，非常爽
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,now,T;
char s[3333333];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);
n=strlen(s);now=0;
for(i=0;i<n;i++){
if(now==0&&s[i]=='v'&&s[i-1]=='v')now++;
if(now==0&&s[i]=='w')now++;
if(now==1&&s[i]=='y')now++;
if(now==2&&s[i]=='h')now++;
}
if(now==3)puts("Yes");else puts("No");
}
}
然后开始摞T2，觉得挺像关押罪犯的，但摞了好久还是写挫了。。然后就一直颓，怎么想也想不出怎么做
大概最后20分钟的时候黈力随便看了一下题，说这不是二分图染色傻逼题吗。。
真是太有道理了，就开始写，可是到最后还是没写出来、
最后HACK的时候还HACK错了一次，名次直接从101调到288。。结果掉了27分，要是不手贱的话涨个几十分还是没有问题的、【死于HACK】
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,now,T;
char s[3333333];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);
n=strlen(s);now=0;
for(i=0;i<n;i++){
if(now==0&&s[i]=='v'&&s[i-1]=='v')now++;
if(now==0&&s[i]=='w')now++;
if(now==1&&s[i]=='y')now++;
if(now==2&&s[i]=='h')now++;
}
if(now==3)puts("Yes");else puts("No");
}
}
BestCoder 1st Anniversary
开场4分钟A了T1傻逼题
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 222222
using namespace std;
typedef long long LL;
int T,n,i,a[N],m,p,q,ans,now;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&n,&m,&p,&q);
ans=inf;now=0;
while(n>0){
ans=min(ans,now+n*p);
n-=m;now+=q;
}
ans=min(ans,now);
printf("%d\n",ans);
}
}
然后开始摞T2，虽然一看就是傻逼题，但由于姿势不太对摞了好久也没有摞出来，还爆了几发OJ，最后就弃疗了。。
然后发现T3A的人挺多，就直接摞了个贪心上去竟然A了，爽~
然后黈力就跟我说贪心是错的。。马上弄了组数据把我×了，我想了一会也没啥好的办法，就先弄T4了
发现T4可以二分图染色一下背包弄，但这题n=20000感到浓浓的卡常恶意，黈力跟我说要bitset，但我不会，就直接摞了个暴力上去，然后T2也乱摞了个交上去
回来继续摞T3，发现可以判断这个数除6的余数，如果是1和2再特判一下解个方程，就重新写了一下，在比赛最后时刻交上去拿了底分。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 1e9
#define N 22222
using namespace std;
typedef long long LL;
LL T,n,i,p,l,r,ans,mid,now,w,step,f[N];
bool ff;
int main(){
scanf("%I64d",&T);
for(i=1;i<=19000;i++)f[i]=f[i-1]+i;
while(T--){
scanf("%I64d",&p);
now=p%6;if(!now)now=6;ff=0;step=p/6;
if(now>=3)printf("%I64d\n",now);else
if(now==1){
w=floor(-0.5+sqrt(0.25+2*step));
if((w*(w+1))==step*2)ff=1;
if(ff)puts("1");else puts("7");
}else if(now==2){
for(i=0;i<=19000;i++)if(f[i]<=step){
w=floor(-0.5+sqrt(0.5+2*(step-f[i])));
if((w*(w+1))==2*(step-f[i]))ff=1;
if(ff)break;
}
if(ff)puts("2");else puts("8");
}
}
}
HACK开始就狂×T3贪心做法，×对5个×错2个；然后开始×T4傻逼判定做法，×对两个×错一个
最后T2和T4都FST了，T2写错了一个小小的地方，T4死于不会bitset，排名127，不过涨了180分，比上次RANK8还多。。
把T2和T4重写了下。。【死于不会bitset】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 222
using namespace std;
typedef long long LL;
int T,n,i,j;bool ff;
char s[N],b[N]={"anniversary"};
int search(int st,int L,int R){
int i,j,len=R-L+1;
for(i=st;i<=n-len;i++){
for(j=0;j<len;j++)if(s[i+j]!=b[L+j])break;
if(j>=len)return i+len;
}
return -1;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);n=strlen(s);ff=0;
for(i=0;i<9;i++)
for(j=i+1;j<10;j++)if(!ff){//1-i i+1-j j-11
int x=search(0,0,i);
if(x==-1)continue;
int y=search(x,i+1,j);
if(y==-1)continue;
int z=search(y,j+1,10);
if(z!=-1)ff=1;
}
if(ff)puts("YES");else puts("NO");
}
}
#include<cstdio>
#include<cstring>
#include<bitset>
#define N 11111
using namespace std;
int T,n,m,i,j,tot,ans,top,r1,r2,x,y,now,tmp,last[222222],ne[222222],first[N],a1[N],a2[N];
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
bool v[N];char ch;
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void insert(int x,int y){last[++tot]=y;ne[tot]=first[x];first[x]=tot;}
void dfs(int x,int col){
if(col)r1++;else r2++;v[x]=1;
for(int i=first[x];i;i=ne[i])if(!v[last[i]])dfs(last[i],1-col);
}
int main(){
read(T);
while(T--){
bitset<11111>dp;
read(n);read(m);
memset(v,0,sizeof(v));
memset(first,0,sizeof(first));
ans=0;tot=0;now=0;top=0;
for(i=1;i<=m;i++){
read(x);read(y);
insert(x,y);insert(y,x);
}
for(i=1;i<=n;i++)if(!v[i]){r1=0;r2=0;dfs(i,0);a1[++top]=r1;a2[top]=r2;}
dp[0]=1;for(i=1;i<=top;i++)dp=(dp<<a1[i])|(dp<<a2[i]);
tmp=0;
for(i=0;i<=n;i++)if(dp[i])tmp=max(tmp,min(i,n-i));
printf("%d\n",tmp*(n-tmp)-m);
}
}
BestCoder Round #49
这场比赛前做了个15KB的板子，秒题更轻松啦！
开场T1直接摞暴力，5分钟A了
void find(int x,int w,int step){
if(!w){MIN(ans,step);return;}
if(!x)return;
find(x-1,w,step);
find(x-1,w%a[x],step+1);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&w);ans=inf;
rep(i,1,n)scanf("%d",&a[i]);
sort(a+1,a+n+1);
find(n,w,0);
if(ans==inf)puts("-1");else pi(ans);
}
}
然后摞T2，马上摞了个Manacher，然后优化了一下发现是n^2的，但n=20000又感到了浓浓的卡时恶意，问了下黈力也没有什么办法，就只能一直颓。。颓到最后也不会做，最后就被HACK了，题解说T2要bitset优化【再次死于bitset】
然后开始HACK，1002成功1个失败3个，1001成功1个，通过HACK涨了50分和一堆人拉开差距排名54，涨了125分好开心啊上橙啦
第二天中午再来看发现又掉回紫了。。原来BC改版了，要分div1和div2了，橙的分数变成了2100分。。我曰
BestCoder Round #50 (div.1)
开场开T1写暴力判，但写到一半发现这也太码了，看T2有挺多人A的就先看了T2
傻逼爆了一发，在mzl的帮助下14分钟才A了T2。。
long long T,n,m,x,y,i,j,tot,ans,dp[N];
int main(){
dp[0]=1;dp[1]=1;dp[2]=1;for(i=3;i<=60;i++)for(j=0;j<=i-3;j++)dp[i]+=dp[j];
while(scanf("%I64d",&n)!=EOF){
ans=0;
for(i=1;i<=n;i++)ans+=dp[i];
printf("%I64d\n",ans);
}
}
然后发现T1是不是只有正方形才有可能，就写了发结果WA了，和没学过小学数学的黈力交流了下发现把菱形也判进去了，这pretest还真强啊。。于是改了下就A了
int T,n,m,i,j,ans,k,l,u,v,tot,ans1,ans2,ans3,ans4,x[N],y[N];
int dis(int a,int b){
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}
int mul(int a,int b){
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}
int main(){
while(scanf("%d",&n)!=EOF){
ans=ans1=ans2=ans3=ans4=0;
for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
for(k=1;k<=n;k++)
if(i!=k&&j!=k)
for(l=1;l<=n;l++)if(i!=l&&j!=l&&k!=l){
if((dis(i,j)==dis(j,k)&&dis(j,k)==dis(k,l)&&dis(k,l)==dis(l,i))&&(dis(i,k)==dis(j,l)))ans2++;
}
printf("%d\n",ans2/8);
}
}
然后看T3觉得也不会，就弃疗了。。
HACK前觉得没什么HACK点，HACK的时候随便点开了一个数组开小的，原来想×结果被抢走了，后来发现这是全场唯一一个成功的HACK【死于HACK被抢】
这场拿了RANK33，涨了76分，感觉再打一场就能上橙啦
BestCoder Round #51 (div.1)
开场T1根本看不懂，问了下黈力才搞懂是怎么一回事，然后就直接写了发A了就没管
然后开始摞T3所谓的回文自动机，虽然过了样例但就是A不了，于是就弃疗了，觉得这场肯定跌分了。。
HACK的时候发现我T1没取模，然后整个人都是崩溃的，全部FST那肯定要大跌一笔了。。
大约10点的时候回来看T1竟然还坚挺着？我不太敢相信，最后发现是由于HACK的问题还没有评测
最后测完就全部FST了，不会有一大堆人全部FST，A了T1的人只有30多个，BCD无人A，剩下的全FST。。
黈力在div2轻松RANK1虐场，%%%，大约到了23点分数还是没有变化，我想大概还要再测，因为A题有1e8的读入量却只有3s时限，大多数人都死于卡时，而我只是个错上加错的傻逼
第二天再来看的时候RATING还是没变，后来这场就unrated了，逃过一劫233
BestCoder Round #52 (div.1)
开场T1发现挺搞基的，然后xmc过来说这是wiki上天梯的一道题，直接复过来结果WA了，然后改了很多个地方，把初值都手动改了才A，大概已经是20多分钟，已经有50+人A了。。
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 17
#define S 1<<N
const int INF=0x7f7f7f7f;
int T,m,x,y,z,in,all,far[N][N]={0},dp[N][S],ans;
int main(){
scanf("%d",&T);
while(T--){
all=0;ans=0;in=0;x=0;y=0;z=0;m=0;
scanf("%d",&in);
for(int i=0;i<=in;i++)for(int j=0;j<=in;j++)far[i][j]=1e9;
for(int i=0;i<=in;i++)far[i][i]=0;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);x--;y--;
far[x][y]=min(far[x][y],z);
far[y][x]=min(far[y][x],z);
}
for(int k=0;k<in;k++)
for(int i=0;i<in;i++)
for(int j=0;j<in;j++)if(i!=k&&i!=j&&k!=j)
far[i][j]=min(far[i][j],far[i][k]+far[k][j]);
all=1<<in;
for(int i=0;i<in;i++)for(int j=0;j<=all;j++)dp[i][j]=1e9;
for(int i=0;i<in;i++)dp[i][0]=far[0][i];
for(int s=1;s<all;s++)
for(int i=0;i<in;i++)if(!(s&(1<<i)))
for(int j=0;j<in;j++)if(s&(1<<j))
dp[i][s]=min(dp[i][s],dp[j][s^(1<<j)]+far[j][i]);
printf("%d\n",dp[0][(all-1)^1]);
}
}
这时T2也已经有挺多人A了，我想这一定是傻逼题，就往傻逼的地方想，没一会就想出来了，我很自信第一发大号直接交了，结果WA了，然后发现没有特判m<=2的情况，改了以后就A了。。
int T,n,m,x,y,i,j,tot,now,pp,w[N],c[N];LL ans,fm,gy,cnt[N];
struct EG{int x,y;}eg[N];bool cmp(EG a,EG b){return (a.x<b.x)||(a.x==b.x&&a.y<b.y);}
void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
int query(int x){int tmp=0;for(;x;x-=x&-x)tmp+=c[x];return tmp;}
int main(){
for(i=3;i<=50000;i++)cnt[i]=(LL)i*(LL)(i-1)*(LL)(i-2)/(LL)6;
scanf("%d",&T);
while(T--){
CL(c);
scanf("%d%d",&n,&m);ans=0;
for(i=1;i<=n;i++)scanf("%d",&w[i]);
for(i=1;i<=m;i++)scanf("%d%d",&eg[i].x,&eg[i].y);
if(m<=2){puts("0");continue;}
sort(eg+1,eg+m+1,cmp);pp=1;
for(i=1;i<=n;i++){
for(;eg[pp].x<=i&&pp<=m;pp++)add(eg[pp].y,1);
now=query(n)-query(i-1);
ans+=(LL)w[i]*cnt[now];
}
fm=cnt[m];
gy=gcd(ans,fm);
ans/=gy;fm/=gy;
if(fm==1)printf("%I64d\n",ans);else printf("%I64d/%I64d\n",ans,fm);
}
}
然后造了些数据，HACK前的排名大概是ROOM9
然后点开几个，发现有些没开longlong的，就×成功了两个，一跃成为ROOM1,爽~，虽然后面×错了一个，但还是ROOM1
最后评完还是ROOM1，我想真是金钱与RATING的双丰收啊，看来肯定可以上橙啦
可拿了RANK7的我却涨了更少的分，只涨了68分，离上橙还差区区6分。。唉，只能下次再努力了
BestCoder Round #53 (div.1)
这场是吉利的场，据说很难呢~
开局摞T1，乱写了一个过了pretest但被黈力怒斥，就重交了一发。。
int T,n,m,x,y,i,j,tot,cnt[N],now,flag;
int la[M],ne[M],fir[N];void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int hi){
cnt[hi]++;now=max(hi,now);
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(y!=fa){
dfs(y,x,hi+1);
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
flag=0;CL(fir);CL(cnt);now=0;tot=0;
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(1,0,0);
for(i=1;i<now;i++)if(cnt[i]>1)flag=1;
if(n<=2||!flag)puts("YES");else puts("NO");
}
}
然后摞T2，发现是在基环树上判曼哈顿回路，就拉了个基环树板，想了想有这么几种情况是合法的，一是一个环，二试一个环+一条链，三是一个环+两条相邻的链，但还是爆了3发OJ才过。。不过这些都是在小号上爆的，也没有什么关系
然后T3、T4也没怎么去看就开始造大数据，造完后随手试试T2，发现自环的情况出了些问题，原来我自环加了两次边就爆炸了，于是只好重交，分数少了400分。。【死于自环】
int T,n,m,x,y,fff,i,j,tot,num,p,q,sz,l2,tt,flag,pp,cir[N],a[N],c[N],dad[N],to[N],pre[N],v[N],qq[N];
int la[M],ne[M],fir[N];void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);}
void fcur(int x){
v[x]=++sz;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(y==pre[x])continue;
if(v[y]){
if(v[y]<v[x])continue;
cir[++num]=x;c[x]=1;
for(;x!=y;y=pre[y])c[y]=1,cir[++num]=y;
}else pre[y]=x,fcur(y);
}
}
bool dfs(int x,int f){
int nn=0;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(y!=f){
nn++;
if(!dfs(y,x))return 0;
if(nn>=2)return 0;
}
}
return 1;
}
int main(){
while(scanf("%d",&n)!=EOF){
CL(fir);num=0;tot=0;fff=0;sz=0;pp=0;tt=0;flag=0;l2=0;CL(dad);CL(c);CL(v);CL(pre);//zh=0;*/
for(i=1;i<=n;i++)dad[i]=i;
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(x!=y)ins(x,y),ins(y,x);else ins(x,y);p=find(x),q=find(y),dad[p]=q;
}
for(i=1;i<n;i++)if(find(i)!=find(i+1))fff=1;
if(fff)puts("NO");else{
fcur(1);
for(x=1;x<=num;x++){
flag=0;
for(i=fir[cir[x]];i;i=ne[i])if(!c[la[i]]){
if(!dfs(la[i],cir[x]))fff=1;else qq[++tt]=x;
}
}
if(tt>2)fff=1;
if(tt==2&&((qq[1]+1!=qq[2]&&(!(qq[1]==1&&qq[2]==num)))))fff=1;
if(!fff)puts("YES");else puts("NO");
}
}
}
然后HACK的时候还手贱HACK错了一发，不过还好对排名的影响不是很大
比完后发现我为啥要这么傻逼的去判，直接拉基环树直径模板不就得了。。
最后拿了RANK31，涨了41分，终于成功上橙~
BestCoder Round #54 (div.1)
开场摞T1，大概就是直接分解质因数，14分钟的时候才A~
然后摞T2，大概就是高精度判断等比数列，就麻麻麻，麻了半小时才麻完。。
然后听黄主力说T3是傻逼题，就把T3秒了
回头发现T2似乎不太对，就改了一发
然后发现T3n=1000000的时候萎掉了，就又改了一发
回头发现T2 0 0 0 0 0的判断是错误的，又改了两发，在最后30S才交上，分数只剩下676了、、【死于疯狂重交】
然后HACK的时候又自己作死HACK错了3发。。排名掉到了A3题中的最后一名【再次死于HACK】
最后测完排到了RANK64，又掉回紫了真开心。。
int T,n,m,x,y,i,j,tot,p,now,x1,x2,x3,x4,top,tt,b[5],a[111],cnt[N],prime[N];bool f[N];
int main(){
scanf("%d",&T);
for(i=2;i<=50000;i++){
if(!f[i])prime[++p]=i;
for(j=1;j<=p&&i*prime[j]<=50000;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
while(T--){
scanf("%d",&n);
CL(cnt);top=0;tt=0;CL(b);CL(a);x1=0;x2=0;x3=0;x4=0;
for(i=1;i<=n;i++){
scanf("%d",&x);
for(now=1;now<=p&&prime[now]*prime[now]<=x;now++){
while(x%prime[now]==0)cnt[now]++,x/=prime[now];
}
if(x!=1)a[++top]=x;
}
sort(a+1,a+top+1);
x1=a[1];x2=a[2];
for(i=1;i<=p&&!x4;i++)if(cnt[i]&&!x3){
x3=prime[i];
if(cnt[i]>1)x4=prime[i];
}else if(cnt[i])x4=prime[i];
if(x1!=0)b[++tt]=x1;
if(x2!=0)b[++tt]=x2;
if(x3!=0)b[++tt]=x3;
if(x4!=0)b[++tt]=x4;
if(tt<2)puts("-1");else{
sort(b+1,b+tt+1);
printf("%I64d\n",(long long)b[1]*(long long)b[2]);
}
}
}
struct data{int v[205],l,fh;}l1,l2,l3;
data operator*(data a,data b){//高精度乘法
data c;memset(c.v,0,sizeof c.v);
for(int i=1;i<=a.l+b.l;i++)c.v[i]=0;
for(int i=1;i<=a.l;i++)
for(int j=1;j<=b.l;j++)
c.v[i+j-1]+=a.v[i]*b.v[j];
c.l=a.l+b.l-1;
for(int i=1;i<=c.l;i++){
c.v[i+1]+=c.v[i]/10;
c.v[i]%=10;
}
if(c.v[c.l+1])c.l++;
return c;
}
data operator-(data a,data b){//高精度减高精度
for(int i=1;i<=a.l;i++){
a.v[i]-=b.v[i];
if(a.v[i]<0){
a.v[i]+=10;
a.v[i+1]--;
}
}
while(a.l&&!a.v[a.l])a.l--;
return a;
}
bool operator==(data a,data b){
while(a.l>0&&a.v[a.l]==0)a.l--;
while(b.l>0&&b.v[b.l]==0)b.l--;
if(a.l!=b.l)return 0;
for(int i=1;i<=a.l;i++)if(a.v[i]!=b.v[i])return 0;
return 1;
}
int T,n,m,x,y,i,j,tot;char s[111];
int main(){
//freopen("2.in","r",stdin);
//freopen("2.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d",&n);
if(n<=1){
scanf("%s",s);
puts("Yes");
}else if(n<=2){
scanf("%s",s);
int ff=0;
l1.l=strlen(s);
for(i=1;i<l1.l;i++)l1.v[i]=s[strlen(s)-i]-'0';
if(s[0]=='-')l1.l--,l1.fh=1;else l1.v[l1.l]=s[0]-'0',l1.fh=0;
while(l1.l>0&&l1.v[l1.l]==0)l1.l--;
if(l1.l==0)ff++;
scanf("%s",s);
l1.l=strlen(s);
for(i=1;i<l1.l;i++)l1.v[i]=s[strlen(s)-i]-'0';
if(s[0]=='-')l1.l--,l1.fh=1;else l1.v[l1.l]=s[0]-'0',l1.fh=0;
while(l1.l>0&&l1.v[l1.l]==0)l1.l--;
if(l1.l==0)ff++;
if(ff==1)puts("No");else puts("Yes");
}else{
int ff=0;
scanf("%s",s);l1.l=strlen(s);
for(i=1;i<l1.l;i++)l1.v[i]=s[strlen(s)-i]-'0';
if(s[0]=='-')l1.l--,l1.fh=1;else l1.v[l1.l]=s[0]-'0',l1.fh=0;
while(l1.l>0&&l1.v[l1.l]==0)l1.l--;
scanf("%s",s);l2.l=strlen(s);
for(i=1;i<l2.l;i++)l2.v[i]=s[strlen(s)-i]-'0';
if(s[0]=='-')l2.l--,l2.fh=1;else l2.v[l2.l]=s[0]-'0',l2.fh=0;
while(l2.l>0&&l2.v[l2.l]==0)l2.l--;
for(j=3;j<=n;j++){
scanf("%s",s);l3.l=strlen(s);
for(i=1;i<l3.l;i++)l3.v[i]=s[strlen(s)-i]-'0';
if(s[0]=='-')l3.l--,l3.fh=1;else l3.v[l3.l]=s[0]-'0',l3.fh=0;
while(l3.l>0&&l3.v[l3.l]==0)l3.l--;
/*for(i=l1.l;i;i--)printf("%d",l1.v[i]);puts("");
for(i=l2.l;i;i--)printf("%d",l2.v[i]);puts("");
for(i=l3.l;i;i--)printf("%d",l3.v[i]);puts("");*/
//printf("%d %d\n",l1.fh,l3.fh);
if(!(l2*l2==l1*l3)||((l1.fh^l3.fh)==1))ff=1;
l1.l=l2.l;l1.fh=l2.fh;
for(i=1;i<=l2.l;i++)l1.v[i]=l2.v[i];
l2.l=l3.l;l2.fh=l3.fh;
for(i=1;i<=l3.l;i++)l2.v[i]=l3.v[i];
}
if(ff)puts("No");else puts("Yes");
}
}
}
#include<cstdio>
#define N 1111111
using namespace std;
int i,j,n,p,ans,R,T,prime[N],phi[N];
bool f[N];
int main(){
n=1000001;
for(i=2;i<=n;i++){
if(!f[i]){
prime[++p]=i;
phi[i]=i-1;
}
for(j=1;j<=p&&i*prime[j]<=n;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("%d\n",phi[n+1]);
}
}
BestCoder Round #55
这场由于吃饭吃太久了，晚了2分钟才开始打
开场看了下T1觉得挺难得，然后发现只有500分就果断先看T2了，如果不会大不了不交
然后发现T2是个傻逼题，直接记忆化水过了。。似乎还没多少人过呢、
int T,n,m,x,y,i,j,k,w,tot,x1,x2,Y1,y2,a[N];
double ans,dp[N][N][N],h[N][N];char s[N];
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
double find(int x,int y,int k){
if(k==0)return inf;
if(x==x2&&y==y2)return 0;
if(dp[x][y][k]!=-1)return dp[x][y][k];
double ans=inf;
if(x>1&&h[x-1][y]!=inf)ans=min(ans,((double)abs(h[x-1][y]-h[x][y])/k)+find(x-1,y,k-1));
if(x<n&&h[x+1][y]!=inf)ans=min(ans,((double)abs(h[x+1][y]-h[x][y])/k)+find(x+1,y,k-1));
if(y>1&&h[x][y-1]!=inf)ans=min(ans,((double)abs(h[x][y-1]-h[x][y])/k)+find(x,y-1,k-1));
if(y<m&&h[x][y+1]!=inf)ans=min(ans,((double)abs(h[x][y+1]-h[x][y])/k)+find(x,y+1,k-1));
return dp[x][y][k]=ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)for(w=0;w<=k;w++)dp[i][j][w]=-1.0;
for(i=1;i<=n;i++){
scanf("%s",s+1);
for(j=1;j<=m;j++)if(s[j]=='#')h[i][j]=inf;else h[i][j]=double(s[j]-'0');
}
scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
ans=find(x1,Y1,k);
if(ans==inf)puts("No Answer");else printf("%.2lf\n",ans);
}
}
然后看了下T1并没有看懂，看T3觉得还是一个挺麻烦的矩乘。。
然后群里问了一下T1的题意就开始弄T1，弄了会没过样例，多谢xmc大爷的提醒，相似棱锥的体积是要乘以3次方而不是2次方的，我怎么这么蠢，像黈力一样连小学数学都不会咯~
然后T1一开始因为没清零WA了一发，在30多分钟的时候才A
int T,n,i;
double tot,u,l,r,mid,h[N],a[N];
double get(double x){
double ans=0;
for(i=1;i<=n;i++){
if(x<=h[i]){
ans+=(h[i]*a[i])*(h[i]-x)/h[i]*(h[i]-x)/h[i]*(h[i]-x)/h[i];
}
}
return ans;
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);tot=0;
for(i=1;i<=n;i++)scanf("%lf",&h[i]);
for(i=1;i<=n;i++)scanf("%lf",&a[i]),a[i]=a[i]*a[i];
for(i=1;i<=n;i++)tot+=h[i]*a[i];
l=0;r=1000;
while(r-l>eps){
mid=(l+r)/2;
u=get(mid);
if(2*u>tot)l=mid;else r=mid;
}
printf("%d\n",(int)l);
}
}
然后开始摞T3，直接上暴力矩乘，没多久就写完了，可发现初始状态比较难弄，搞了好久没搞过样例
然后想了想可以建一个超级源点连所有的初始状态，这样就对啦，然后就A了，暂时是ROOM1爽~
int T,m,x,y,i,j,k,S,sum;bool u[9],u2[9],flag;
struct JZ{int x,y,m[N][N];}ans,def;
JZ cheng(JZ a,JZ b){
JZ c;memset(c.m,0,sizeof c.m);
c.x=a.x;c.y=b.y;
for(int i=0;i<=a.x;i++)
for(int j=0;j<=b.y;j++)
for(int k=0;k<=a.y;k++)c.m[i][j]=(int)((LL)((LL)c.m[i][j]+(LL)(a.m[i][k]%MOD)*(LL)(b.m[k][j]%MOD))%MOD);
return c;
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
while(scanf("%d%d",&T,&m)!=EOF){
S=1<<m;
memset(def.m,0,sizeof def.m);
def.x=def.y=S;
for(i=0;i<S;i++){
memset(u,0,sizeof(u));
memset(u2,0,sizeof(u2));
for(j=0;j<m;j++)if((1<<j)&i)u[j]=1;
for(j=0;j<S;j++){
flag=1;
for(k=0;k<m;k++)if((1<<k)&j)u2[k]=1;else u2[k]=0;
for(k=0;k<m;k++){
if(k)if(u[k]&&!u[k-1]&&!u2[k]&&u2[k-1])flag=0;
if(u[k]&&!u[k+1]&&!u2[k]&&u2[k+1])flag=0;
if(!flag)break;
}
if(flag)def.m[i][j]=1;
}
}
for(i=0;i<S;i++)def.m[S][i]=1;
for(ans=def,T--;T;T>>=1){
if(T&1)ans=cheng(ans,def);
def=cheng(def,def);
}
sum=0;
for(i=0;i<S;i++)
sum=(sum+ans.m[0][i])%MOD;
printf("%d\n",sum);
}
}
然后看T4，觉得就是数位DP乱搞，可我数位DP掌握的不是很熟练，就搞了半小时才把基本的DP写对
然后就开始乱个案的转移，在最后15分钟的时候才弄完，可发现最后一个样例没过
最后加了个特判在最后五分钟过了PRETEST，可惜最后还是被×了
int T,n,m,x,y,l,i,j,k,u,tot,now,cas,pp,dp[N][16],cnt[16];char s[N];LL sum,sum2,ans;
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
dp[0][0]=1;
for(i=0;i<=9;i++)dp[1][i]=1;
for(i=2;i<=100002;i++)
for(j=0;j<16;j++)
for(k=0;k<=9;k++)dp[i][j]=(dp[i][j]+dp[i-1][j^k]);
/*for(k=0;k<16;k++){
for(l=0;l<=9;l++)if((k^l)==j)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
}*/
scanf("%d",&T);
while(T--){
memset(cnt,0,sizeof(cnt));sum=0;sum2=0;
scanf("%s",s+1);n=strlen(s+1);now=0;
for(i=n;i;i--){
u=s[n-i+1]-'0';
for(j=0;j<u;j++)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][j^k^now])%MOD;
if(i==1)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][u^k^now]);
now^=s[n-i+1]-'0';
}
pp=0;
for(i=1;i<=n;i++)pp=pp^(s[i]-'0');
for(i=1;i<16;i++)sum=(sum+(LL)cnt[i]*(LL)i)%MOD;
scanf("%s",s+1);n=strlen(s+1);
memset(cnt,0,sizeof(cnt));now=0;
for(i=n;i;i--){
u=s[n-i+1]-'0';
for(j=0;j<u;j++)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][j^k^now])%MOD;
if(i==1)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][u^k^now]);
now^=s[n-i+1]-'0';
}
//for(i=0;i<16;i++)printf("%d ",cnt[i]);puts("");
for(i=1;i<16;i++)sum2=(sum2+(LL)cnt[i]*(LL)i)%MOD;
ans=(sum2-sum+pp+MOD)%MOD;
printf("Case #%d: %I64d\n",++cas,ans);
}
}
然后开始HACK，原来以为T2挺好HACK的，但发现大家都能过k=0的情况，10分钟后一无所获
然后点开几个T1的，发现有一个数组开小了，就造了组数据，可造完后发现已经被×了
然后又发现一个数组开小的，就×掉了。。
可是由于1004被×了，掉到了ROOM2，看来奖励拿不到了呢~
最后REJUDGE的时候原来的ROOM1的T1和T2全部作死WA了，我才侥幸拿了ROOM1，而且小号也拿了ROOM1。。
这场排到了第10名，又涨回橙啦~
T4忘了取膜真是曰了狗。。还是太急了，最后时刻直接交了。。和第一次登上领奖台擦肩而过【死于忘了取膜】
/*****************************************************************
Author:lbn187, a konjac TwT
Date:2015-07-31
Contest:2015 Multi-University Training Contest
Algorithm:QAQ
^_^ Orz hzh, NOI gold members, IOI 2016 world champion
^=^ Orz hhw, you are our blue moon, with you will live
^~^ Orz mxh, you are our red sun, without you we'll die
^-^ Orz yizhou, I wish you a successful marriage
^w^ Orz xianyangyu, you can sleep all the time in the game
*****************************************************************/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#define fo(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=1;i<=n;i++)
#define dr(i,n) for(int i=n;i;i--)
#define do(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mjj(i,x) for(int i=fir[x];i;i=ne[i])
#define X first
#define Y second
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define mp make_pair
#define rlr son[son[root][1]][0]
#define gi(a) scanf("%d",&a);
#define gi2(a,b) scanf("%d%d",&a,&b);
#define gi3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define gl(a) scanf("%I64d",&a);
#define gs(s) scanf("%s",s);
#define pi(a) printf("%d\n",a);
#define pi2(a,b) printf("%d %d\n",a,b);
#define pl(a) printf("%I64d\n",a);
#define spr(x) (x*x)
#define pie acos(-1)
#define CP(a,b) memcpy(a,b,sizeof(a))
#define CL(a) memset(a,0,sizeof(a))
#define N 222222
#define M 222222
#define MOD 1000000007
#define inf 1e9
#define eps 1e-8
using namespace std;
typedef long long LL;typedef unsigned long long ULL;typedef double LF;typedef long double LD;
typedef pair<int,int>pii;typedef pair<int,LL>pil;typedef pair<LL,int>pli;typedef pair<LL,LL>pll;typedef pair<LF,LF>pff;
const int xx[]={1,-1,0,0},yy[]={0,0,1,-1};
int T,n,m,x,y,l,i,j,k,u,tot,now,cas,pp,dp[N][16],cnt[16];char s[N];LL sum,sum2,ans;
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
dp[0][0]=1;
for(i=0;i<=9;i++)dp[1][i]=1;
for(i=2;i<=100002;i++)
for(j=0;j<16;j++)
for(k=0;k<=9;k++)dp[i][j]=(dp[i][j]+dp[i-1][j^k])%MOD;
scanf("%d",&T);
while(T--){
memset(cnt,0,sizeof(cnt));sum=0;sum2=0;
scanf("%s",s+1);n=strlen(s+1);now=0;
for(i=n;i;i--){
u=s[n-i+1]-'0';
for(j=0;j<u;j++)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][j^k^now])%MOD;
if(i==1)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][u^k^now])%MOD;
now^=s[n-i+1]-'0';
}
pp=0;
for(i=1;i<=n;i++)pp=pp^(s[i]-'0');
for(i=1;i<16;i++)sum=(sum+(LL)cnt[i]*(LL)i)%MOD;
scanf("%s",s+1);n=strlen(s+1);
memset(cnt,0,sizeof(cnt));now=0;
for(i=n;i;i--){
u=s[n-i+1]-'0';
for(j=0;j<u;j++)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][j^k^now])%MOD;
if(i==1)for(k=1;k<16;k++)cnt[k]=(cnt[k]+dp[i-1][u^k^now])%MOD;
now^=s[n-i+1]-'0';
}
for(i=1;i<16;i++)sum2=(sum2+(LL)cnt[i]*(LL)i)%MOD;
ans=(sum2-sum+pp+MOD)%MOD;
printf("Case #%d: %I64d\n",++cas,ans);
}
}
BestCoder Round #56 (div.1)
这场由于在学校里8:30要回寝室，大号就没打，小号随便打了下
T1傻逼题，傻逼地爆了一发，5分钟A了
int main(){
scanf("%d",&T); int p,f[N],g[N];
while(T--){
scanf("%d%d",&n,&p);
memset(f,0,sizeof(f));f[0]=1;
for(;n--;){
for(i=0;i<p;i++)g[i]=f[i];
scanf("%d",&x);x%=p;
for(i=0;i<p;i++)f[i]=(g[i]+g[(i-x+p)%p])%MOD;
}
printf("%d\n",f[0]);
}
}
T2二维树状数组裸题，但一开始题看错多想了会，然后写了一发WA了，调了5分多钟才发现树状数组写炸了。。
int T,n,m,q,i,j,x,opt,x1,Y1,x2,y2,p,w,y,z,c[N][N];
void ins(int x,int y,int z){
for(;x<=n;x+=x&-x){
int a=y;
for(;a<=m;a+=a&-a)
c[x][a]^=z;
}
}
int get(int x,int y){
int ans=0;
for(;x;x-=x&-x){
int a=y;
for(;a;a-=a&-a)
ans^=c[x][a];
}
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&q);CL(c);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&x),ins(i,j,x);
for(;q--;){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
p=get(x2,y2)^get(x1-1,Y1-1)^get(x2,Y1-1)^get(x1-1,y2);
puts(p?"Yes":"No");
}else{
scanf("%d%d%d",&x,&y,&z);
w=get(x,y)^get(x-1,y-1)^get(x,y-1)^get(x-1,y);
ins(x,y,w^z);
}
}
}
}
最后RANK51，小号也涨了一些分。。
BestCoder Round #58 (div.1)
这场在国庆，总算能打了。。
开场看T1好难好难啊，然后看T2好难好难啊，然后看T3似乎还能做
就开始做T3，但摞了30min才摞完。。。
int T,n,m,x,y,i,j,tot,cnt,a[N],v[N];
LL c[N],d[N],ans,now,pp;
void ins(int x,int z){for(;x<=n;x+=x&-x)c[x]+=z;}
void ins2(int x,int z){for(;x<=n;x+=x&-x)d[x]+=z;}
LL get(int x){for(pp=0;x;x-=x&-x)pp+=c[x];return pp;}
LL get2(int x){for(pp=0;x;x-=x&-x)pp+=d[x];return pp;}
int main(){
scanf("%d",&T);
while(T--){
CL(c);CL(d);
scanf("%d%d",&n,&m);now=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n-m;i++){
ins(a[i],1);
now+=get(n)-get(a[i]);
}
ans=now;
for(i=n-m;i;i--){
ins(a[i],-1);
now+=get(n)-get(a[i+m]);
now-=get2(a[i]-1);
ins2(a[i+m],1);
now+=get2(a[i+m]-1);
now-=get(n)-get(a[i]);
ans=min(ans,now);
}
printf("%I64d\n",ans);
}
}
然后YY大爷马上把T1秒了%%%似乎就是把置换弄出来就可以了。。
然后摞T2，虽然被黄主力一眼秒了，但蒟蒻还是不会做。。想了好久越想越复杂
就又问了一下黄主力，马上就顿悟了，%%%
int T,n,i,top;LL x,sum,to[N],ans;
map<long long,int>mp;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);mp.clear();sum=ans=0;
for(i=1;i<=n;i++){
scanf("%I64d",&x);sum=(sum+x)%MOD;
if(mp[x])ans=(ans+(pow(2,n-i,MOD)*(to[mp[x]])%MOD)*x%MOD+MOD)%MOD;else mp[x]=++top;
to[mp[x]]=(to[mp[x]]+pow(2,i-1,MOD))%MOD;
}
sum=(sum*pow(2,n-1,MOD))%MOD;
printf("%I64d\n",(sum-ans+MOD)%MOD);
}
}
但是测得时候T3竟然FST了。。原来是多开了long long 导致TLE了【死于开long long】
真是曰了狗，原来+40分的现在-40分了。。。
BestCoder Round #60
这场由于在学校，还是8:30寝室关门，所以用小号打。。
4min交了T1，WA了，改了以下就A了。。
然后T2YY了以下，然后就A了。。
然后T3看了一会，发现直接搜索就行了，然后就A了。。然后就暂时排到了RANK1
然后看T4，觉得暴力似乎可做？复杂度似乎是N^1.5的。。。
然后就码码码，发现判断子串除了SAM没有什么特别好的方法。。
只好写了个SAM，然后交上去WA了，可是这时已经8:25了，只好回去了。。
第二天来发现所有题目都FST了，真是太爽了。。不过反正小号，也无所谓了
然后来订正一下：
1001 有0的时候稍微有点问题。。
int T,n,m,x,y,i,j,tot,tp,ff,ww;LL a[N],b[N],ans;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);ans=1;ff=0;tp=0;ww=0;
for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
sort(a+1,a+n+1);
for(i=1;i<=n;i++)if(a[i]>0)ans*=a[i],ff=1;else if(a[i]<0)b[++tp]=a[i];else ww=1;
if(ff){
for(i=1;i+1<=tp;i+=2)ans*=b[i]*b[i+1];
}else{
if(ww&&tp<=1)ans=0;else
if(tp==1)ans=a[tp];else{
for(i=1;i+1<=tp;i+=2)ans*=a[i]*a[i+1];
}
}
printf("%I64d\n",ans);
}
}
1002 大力分解质因数作大死
int T,i,j,tot,t,ans,ff,aa,bb,pp,p[1001];
LL x,y,n,m,w;
bool f[1001];
int main(){
for(i=2;i<=1000;i++){
if(!f[i])p[++t]=i;
for(j=1;j<=t&&i*p[j]<=1000;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d",&n,&m);
if(n==m){
puts("0");
continue;
}
x=n;y=m;pp=0;ans=0;ff=1;
for(i=1;i<=t;i++){
aa=0;bb=0;
for(;x%p[i]==0;x/=p[i])aa++;
for(;y%p[i]==0;y/=p[i])bb++;
if(aa>bb||(bb>0&&!aa)){
ff=0;
break;
}else if(aa)if((bb-1)/aa+1>pp)pp=(bb-1)/aa+1;//pp=max(pp,(bb-1)/aa+1);
}
//printf("%I64d %I64d\n",x,y);
bb=0;
for(;y%x==0&&x!=1;y/=x)bb++;
pp=max(bb,pp);
if((!ff)||y>1){
puts("-1");
continue;
}
for(w=1;w<pp;w*=2)ans++;
printf("%d\n",ans);
}
}
1003 题目一个细节看错了，原来每个数是<=300，我以为是<=10的了，<=300也一样，直接暴力就可以了。。
int T,n,m,x,y,i,j,L,tot,ff,f[31],a[31][11],v[31][333];
void dfs(int x,int y){
if(x==n+1)ff=1;
if(ff)return;
bool ww=0;
for(int i=1;i<=a[x][0];i++)if(v[x][a[x][i]]<=0){ww=1;break;}
if(ww){dfs(x+1,y);return;}
if(y>L)return;
for(int i=1;i<=a[x][0];i++)if(v[x][a[x][i]]>0){
for(int j=1;j<=n;j++)v[j][a[x][i]]--;
dfs(x+1,y+1);
for(int j=1;j<=n;j++)v[j][a[x][i]]++;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&L);ff=0;CL(a);CL(v);
for(i=1;i<=n;i++){
for(scanf("%d",&a[i][0]),j=1;j<=a[i][0];j++)scanf("%d",&a[i][j]),v[i][a[i][j]]=1;
}
dfs(1,1);
puts(ff?"YES":"NO");
}
}
1004 我也不知道错哪了。。
int T,n,m,x,y,la,i,j,k,l,c,wz,pp,now,p,np,q,nq,cnt,lenx,leny,tmp,len[N],S[N],son[N][27],fa[N],fir[27],ne[N][27],a[N],st[N],ed[N];//ULL pw[N],sum[N];
char s[N];
map<pair<int,int> ,int > pm;
void add(int c){
p=la;len[np=la=++cnt]=len[p]+1;
for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
if(!p)fa[np]=S[i];else{
q=son[p][c];
if(len[p]+1==len[q])fa[np]=q;else{
nq=++cnt;len[nq]=len[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
}
}
}
void print(int x){
if(x>=2)printf("1");else printf("0");
if(x&1)printf("1");else printf("0");
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);pm.clear();
CL(ne);CL(son);CL(fa);CL(len);CL(S);CL(st);CL(ed);CL(a);
la=cnt=p=np=q=nq=0;
for(now=i=1;i<=n;i++){
st[i]=now;
scanf("%s",s);l=strlen(s);
memset(fir,-1,sizeof(fir));S[i]=la=++cnt;
for(j=0;j<l;j++){
c=s[j]-'a';add(s[j]-'a');
a[now+j]=c;fir[c]=now+j;
for(k=0;k<26;k++)ne[now+j][k]=fir[k];//,printf("%d ",ne[now+j][k]);
//puts("");
}
ed[i]=now+l-1;
now+=l;
//printf("---%d\n",st[2]);
//for(j=0;j<l;j++)add(s[j]-'a');
}
//for(i=1;i<=cnt;i++)printf("%d ",len[i]);puts("");
//for(i=1;i<=n;i++)printf("%d ",S[i]);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);lenx=ed[x]-st[x]+1;leny=ed[y]-st[y]+1;
if(lenx>leny){
printf("00");
continue;
}
if(pm[mp(x,y)])print(pm[mp(x,y)]);else{
wz=ed[y];pp=0;
for(j=ed[x];j>=st[x];j--){
wz=ne[wz][a[j]]-1;
if(wz==-1)break;
}
if(wz!=-1)pp+=2;
for(p=S[y],tmp=0,j=st[x];j<=ed[x];j++){
if(son[p][a[j]])p=son[p][a[j]],tmp++;else{
for(;!son[p][a[j]]&&p;p=fa[p]);
if(!p)p=S[y],tmp=0;else tmp=len[p]+1,p=son[p][a[j]];
}
if(tmp>=lenx)break;
}
if(tmp>=lenx)pp++;
pm[mp(x,y)]=pp;
print(pp);
}
}
puts("");
}
}
1005明显裸树上带修莫队，可惜我不会带修的莫队。。
BestCoder Round #61（div.1)
这场由于会考回家了，总算有时间打了。。
T1是一道分类讨论的智商题，我由于智商不够用，试了20分钟才试出来
int T,n,m,x,y,w,S,t,i,j,tot,a[N];
int main(){
while(scanf("%d%d%d",&n,&S,&t)!=EOF){
if(n==1&&S==1&&t==1)puts("0");else
if(S==t)puts("-1");else
if((S==1&&t==n)||(S==n&&t==1))puts("0");else
if(S==1||S==n||S-t==1||t-S==1)puts("1");else puts("2");
}
}
T2是一道语文好题，由于语文水平太差，我没有读懂，就先看了T3
T3觉得就是把一个数的约数个数统计出来，然后求这个数的幂就可以了
怎么统计约数个数呢？用约数和公式，开根怎么办呢？判断约数是奇数和偶数就可以啦
这个幂有点大啊，没事，刚用过费马小定理，套上去就好啦。。
怎么过不了样例？看来还要分解质因数。。没事我有板，马上写好，45分钟交，暂时刷到RANK1
LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
int T,n,m,x,y,i,j,t,tot,p[N],a[N],to[N];LL r,u,v,w,cnt[N];bool ff;bool f[N];
int main(){
for(i=2;i<=100000;i++){
if(!f[i])p[++t]=i,to[i]=t;
for(j=1;j<=t&&i*p[j]<=100000;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
while(scanf("%d",&n)!=EOF){
ff=0;CL(cnt);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i>1){
for(r=i,j=1;p[j]*p[j]<=r;j++)if(r%p[j]==0){
for(;r%p[j]==0;r/=p[j])cnt[j]+=a[i];
}
cnt[to[r]]+=a[i];
}
}
for(v=u=1,i=1;i<=t;i++){
if(cnt[i]&1)ff=1;
u=u*pow(p[i],cnt[i]/2,MOD)%MOD;
v=v*pow(p[i],cnt[i],MOD)%MOD;
}
if(ff){
for(w=1,i=1;i<=t;i++)if((cnt[i]&1)&&ff)w=w*((cnt[i]+1)/2)%(MOD-1),ff=0;else w=w*(cnt[i]+1)%(MOD-1);
printf("%I64d\n",pow(v,w+MOD-1,MOD));
}else{
for(w=1,i=1;i<=n;i++)w=w*(cnt[i]+1)%(MOD-1);
printf("%I64d\n",pow(u,w+MOD-1,MOD));
}
}
}
然后回来看T2，搞了20分钟才理解题意，然后开始找规律，找到一个前20个数对的规律交上去WA了，然后就一直想不出。。
测之前排名16，排在一堆3题的后面，由于和小号分在一个ROOM，就一直HACK小号，可T1总是显示输入不合法，真是曰狗，只好先HACK第三题，回来继续HACK第一题，总是输入不合法，最后放弃了。。
最后测完RANK15，发现我的HACK竟然是+5。。原来几个不合法输入都重测了。。早知道就多HACK几次了，多1次就是好几名啊。。【死于HACK意志不坚定】
后来看了题解发现是一道傻逼题啊。。分治下去就可以啦。。第一次不会做60人A的题啊【死于不会傻逼题】
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
set<LL>st;LL n,x;int w;
void cal(LL n,int hi,LL sum){
st.insert(sum);if(n==1)return;
int x=w-hi+(n&1),i;
for(i=1;i<=x;i++)st.insert((1ll<<i)-1);
cal(n/2,hi-1,sum+(1<<x));
}
int main(){
for(;scanf("%lld",&n)!=EOF;st.clear()){
for(w=0,x=n;x;w++)x/=2;
cal(n,w,1);printf("%d\n",st.size());
}
}
BestCoder Round #62 (div.1)
开场第一个交T1，然后T2想了一会觉得就是数位DP+快速幂，就麻麻麻，然后发现题目看错了，然后重新写，调了好久才过了样例，可是调到最后都没A。HACK的时候发现T1写错了，直接GG，掉了70多分掉下紫了。。
BestCoder Round #64 (div.1)
T1不是傻逼题么。。赶紧写了个，小号排了第一，大号交慢了点滚第五了。。
T2不是傻逼题么。。赶紧写了个，小号第二个交，但是RE了，日狗一个数读成%d了，改好了已经滚到第十了。。
T3好神啊。。完全没思路。。这有毛规律啊。。不会做GG
T4似乎在树上和在数列上没什么区别啊，但是在数列上怎么做呢？大概是莫队+BIT吧。。可是这是O(n^1.5lg^2n)的啊，有什么希望呢。。我想，我想。。想不出GG
HACK的时候，哈哈有个傻逼T1数组开小啦，看我×死他，结果我被×死了，没想到他数组里存的是0~10007膜的答案。。于是排名直接掉了5名【再次死于HACK】
不过由于手速还是比较快，总算涨回橙啦。。
int T,n,m,x,y,i,j,tot,a[N],b[N],c[N];LL now,ans;
int main(){
while(scanf("%d",&n)!=EOF){
for(i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i],b[i]=(1890*a[i]+143)%10007,c[i]=b[i]-a[i];
for(now=ans=0,i=1;i<=n;i++){
now+=c[i];
if(now<0)now=0;
ans=max(ans,now);
}
for(i=1;i<=n;i++)ans+=a[i];
printf("%I64d\n",ans);
}
}
int T,n,m,y,i,j,tot,a[N];LL w,x,pw[66],sum[66];
LL get(LL x){
if(x==0)return 0;
if(x==1)return 1;
for(int i=1;i<=56;i++)if(pw[i+1]>=x)return get(x-pw[i]-1)+sum[i]+x-pw[i];
}
int main(){
scanf("%d",&T);
for(w=2,pw[1]=1,sum[1]=1,i=2;i<=57;i++)sum[i]=sum[i-1]*2+w,w=w*2,pw[i]=w-1;
while(T--){
scanf("%I64d",&x);
printf("%I64d\n",get(x));
}
}
1004看了题解写了下，涨姿势了。。要在字典树上来维护异或，这样的复杂度就变为O(n^1.5lgn)啦233
#include<bits/stdc++.h>
#define N 50050
#define CL(a) memset(a,0,sizeof(a))
using namespace std;
int T,n,m,Q,x,y,z,l,r,i,j,k,zs,tot,sum,S=300,fir[N],ne[N<<1],la[N<<1],va[N<<1],d[N],pos[N],ans[N],c[N*17][2],sz[N*17];
struct P{int l,r,id;}q[N];bool cmp(P a,P b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r;}
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int val){
d[x]=val;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,val^va[i]);
}
void add(int x){
int u=0,i,w;
for(i=15;i>=0;i--){
w=x>>i&1;
if(m>>i&1)u=c[u][w^1];else sum+=sz[c[u][w^1]],u=c[u][w];
if(!u)break;
}
for(u=0,i=15;i>=0;i--){
w=x>>i&1;
if(!c[u][w])c[u][w]=++zs;
sz[u=c[u][w]]++;
}
}
void del(int x){
int u=0,i,w;
for(i=15;i>=0;i--){
w=x>>i&1;
if(m>>i&1)u=c[u][w^1];else sum-=sz[c[u][w^1]],u=c[u][w];
if(!u)break;
}
for(u=0,i=15;i>=0;i--)sz[u=c[u][x>>i&1]]--;
}
int main(){
for(;scanf("%d%d%d",&n,&m,&Q)!=EOF;tot=sum=zs=0,CL(fir),CL(d),CL(c),CL(sz)){
for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(dfs(1,0,0),i=1;i<=Q;i++)pos[i]=(i-1)/S,scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
for(sort(q+1,q+Q+1,cmp),l=i=1,r=0;i<=Q;ans[q[i++].id]=sum){
for(;r<q[i].r;)add(d[++r]);for(;r>q[i].r;)del(d[r--]);
for(;l<q[i].l;)del(d[l++]);for(;l>q[i].l;)add(d[--l]);
}
for(i=1;i<=Q;i++)printf("%d\n",ans[i]);
}
}
BestCoder Round #65
这场在学校，8:30要回寝室，原来不想打的，可是还是打了
开场想先看T2，如果没秒大号就不做了，没想到一眼秒了，2min就A了。。
然后5min时候秒了T1
然后看T3,这不是傻逼题么。。10min的时候把T3也秒了，遥遥领先
然后看T4，好神啊，感觉是个挺难写的DP，先检查一下前几道，看来没什么问题
直接写T4，30min的时候写完了，觉得挺对的，但是一交RE了。。结果还交错号用大号交了。。
然后看了几遍代码，发现有一个j--写成j++了，而且第二遍DP没弄下去
改了下在40min的时候才A，这时候已经掉到第七了，更要命的是小号还排在大号前面
然后看最后一题觉得好神啊，乱写了个双联通GG。。
最后排到第9，大涨一笔，不得不说还是合场比较好涨分。。
int T,n,m,x,y,i,j,tot,a[N];
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);
if(n&1)puts("1");else puts("0");
}
}
int T,n,m,x,y,i,j,tot,a[N];char s1[N],s2[N];bool ff;
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);
scanf("%s",s1);
scanf("%s",s2);ff=1;
for(i=0;i<n;i++){
if((s1[i]=='A'&&s2[i]!='U')||(s1[i]=='T'&&s2[i]!='A')||(s1[i]=='C'&&s2[i]!='G')||(s1[i]=='G'&&s2[i]!='C'))ff=0;
}
puts(ff?"YES":"NO");
}
}
int T,n,m,x,y,i,j,tot,w,sum,a[N],b[N],c[N];
void add(int x,int z){for(;x<=n;x+=x&-x)c[x]+=z;}
int query(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int get(int x){
int l=1,r=n,mid,ans=0;
for(;l<=r;)if(query(mid=l+r>>1)>x)r=mid-1;else l=mid+1,ans=mid;
return ans+1;
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),add(i,1);
for(i=n;i;i--){
w=a[i]-a[i-1];
b[i]=get(i-w-1);
add(b[i],-1);
}
for(i=1;i<=n;i++)printf("%d%c",b[i],i==n?'\n':' ');
}
}
int T,n,m,x,y,i,j,k,A,B,tot,ans,p,a[N],fa[N],f[N][11],la[N],ne[N],fir[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
int i,j;f[x][0]=1;
for(i=fir[x];i;i=ne[i]){
fa[la[i]]=x;
dfs(la[i]);
for(j=0;j<k;j++)f[x][j+1]+=f[la[i]][j];
}
}
void up(int x){
int i,j;
for(i=fir[x];i;i=ne[i]){
for(j=k;j>1;j--)f[la[i]][j]-=f[la[i]][j-2];
for(j=0;j<k;j++)f[la[i]][j+1]+=f[x][j];
up(la[i]);
}
}
int main(){
for(scanf("%d",&T);T--;){
CL(fir);tot=0;CL(f);CL(fa);CL(la);CL(ne);
scanf("%d%d%d%d",&n,&k,&A,&B);
for(i=2;i<=n;i++){
x=(int)(((LL)A*i+B)%(i-1))+1;
ins(x,i);
}
dfs(1);
up(1);ans=0;
for(i=1;i<=n;i++){
p=0;
for(j=0;j<=k;j++)p+=f[i][j];
ans^=p;
}
printf("%d\n",ans);
}
}
BestCoder Round #67 (div.1)
原来以为这场能在家里打的，没想到又是小礼拜，只好少15min去打。。没想到受到了很大的影响QAQ
开场原来想秒T2或T3的，但看上去不可做的样子
回来看看T1，一个看上去不是多项式的题要求一个读入复杂度的算法，一定很傻逼，用小号试一试，一开始用了bits/stdc++.h CE了几发，原来是第一个过的。。然后变成第二了。。
然后看T2，真是暴搜好题啊，一开始查了下21点打法，并没有什么发现，然后乱写了一个DP，写了好久，然后小号改了10多发才过了pretest。。这时只有30min了。。
然后看T3，想了10min会做了，还有15min寝室就关门了，只好赶紧写，但是没来得及写完。。
然后T2就FST了。。我的傻逼DP大概是错的吧。。早知道做T3了。。再写5min就写完了【死于寝室关门】
#include<cstdio>
int T,n,m,x,y,i,j,tot,w;
int main(){
for(scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);w=0;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&x),w+=x;
if(((n+m)%2+(w)%2)==1)puts("YES");else puts("NO");
}
}
int T,n,m,x,y,i,j,k,l,tot,a[N];char s[9];
double o,w,u,f[22][22][22],g[22][22],h[22][22];
int get(char w){
if(w=='A')return 1;
if(w>'A'&&w<='Z')return 10;
return w-'0';
}
double cal(int x,int y){
if(x>21)return 0;
if(x>y)return 1;
if(x==y)return 0.5;
double ans=0;
for(int i=1;i<=9;i++)ans+=o*cal(x+i,y);
ans+=w*cal(x+10,y);
return ans;
}
int main(){
w=(double)4/13;o=(double)1/13;
for(i=2;i<=20;i++){
f[i][i][0]=1;
for(l=2;l<=20;l++)
for(j=1;j<=19;j++){
for(k=1;k<=10;k++){
if(k==10)u=w;else u=o;
if(l+k<=21)f[i][l+k][j]+=f[i][l][j-1]*u;
}
}
}
for(i=2;i<=20;i++){
for(j=2;j<=21;j++){
g[i][j]=cal(i,j);
}
}
for(l=2;l<=20;l++)
for(i=2;i<=20;i++){
for(k=0;k<=19;k++){
u=0;
for(j=2;j<=21;j++){
u+=f[i][j][k]*(1.00-g[l][j]);
}
h[i][l]=max(h[i][l],u);
}
}
for(scanf("%d",&T);T--;){
scanf("%s",s);
x=get(s[0])+get(s[1]);
y=get(s[2])+get(s[3]);
if(h[x][y]>0.5)puts("YES");else puts("NO");
}
}
int T,n,m,w,x,y,i,j,k,tot,cnt,now,a[N],ans[N],c[N];
struct P{int x,y,z;}p[N],q[N];
bool cmp(P a,P b){return a.y<b.y;};
void add(int x,int z){if(x==0)return;for(;x<=1000000;x+=x&-x)c[x]+=z;}
int qu(int x){if(x<=0)return 0;for(now=0;x;x-=x&-x)now+=c[x];return now;}
int main(){
for(;scanf("%d%d",&n,&m)!=EOF;){
w=0;cnt=0;CL(c);CL(ans);
for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(i=1;i<=m;i++){
scanf("%d",&k);
for(y=0,j=1;j<=k;j++){
scanf("%d",&x);
if(y+1<=x-1)q[++w].x=y+1,q[w].y=x-1,q[w].z=i;
y=x;
}
q[++w].x=y+1,q[w].y=1000000,q[w].z=i;
}
sort(p+1,p+n+1,cmp);sort(q+1,q+w+1,cmp);
for(i=j=k=1;i<=1000000;i++){
for(;p[j].y==i&&j<=n;j++)add(p[j].x,1),cnt++;
for(;q[k].y==i&&k<=w;k++)ans[q[k].z]+=cnt-qu(q[k].x-1);
}
for(i=1;i<=m;i++)printf("%d\n",n-ans[i]);
}
}
/*****************************************************************
Author:lbn187, a konjac TwT
Date:2015-12-26
Contest:Bestcoder
Algorithm:QAQ
^_^ Orz hzh, NOI gold members, IOI 2016 world champion
^=^ Orz hhw, you are our blue moon, with you will live
^~^ Orz mxh, you are our red sun, without you we'll die
^-^ Orz yizhou, I wish you a successful marriage
^w^ Orz xianyangyu, you can sleep all the time in the game
*****************************************************************/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#define fon(i,n) for(int i=0;i<n;i++)
#define frn(i,n) for(int i=1;i<=n;i++)
#define drn(i,n) for(int i=n;i;i--)
#define don(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mjj(i,x) for(int i=fir[x];i;i=ne[i])
#define X first
#define Y second
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define mp make_pair
#define rlr son[son[root][1]][0]
#define gi(a) scanf("%d",&a);
#define gi2(a,b) scanf("%d%d",&a,&b);
#define gi3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define gl(a) scanf("%I64d",&a);
#define gs(s) scanf("%s",s);
#define pi(a) printf("%d\n",a);
#define pi2(a,b) printf("%d %d\n",a,b);
#define pl(a) printf("%I64d\n",a);
#define spr(x) (x*x)
#define pie acos(-1)
#define CP(a,b) memcpy(a,b,sizeof(a))
#define CL(a) memset(a,0,sizeof(a))
#define N 222222
#define M 222222
#define P 1000000007
#define inf 1e9
#define eps 1e-8
using namespace std;
typedef long long LL;typedef unsigned long long ULL;typedef double LF;typedef long double LD;
typedef pair<int,int>pii;typedef pair<int,LL>pil;typedef pair<LL,int>pli;typedef pair<LL,LL>pll;typedef pair<LF,LF>pff;
LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
LL phi(LL n){LL i,re=n;for(i=2;i*i<=n;i++)if(n%i==0){re=re/i*(i-1);while(n%i==0)n/=i;}if(n>1)re=re/n*(n-1);return re%P;}
void exgcd(LL a,LL b,LL &x,LL &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
const int xx[]={1,-1,0,0},yy[]={0,0,1,-1};
int T,n,m,x,y,i,j,k,l,tot,a[N];char s[9];
double o,w,u,f[22][22],g[22][22],h[22][22];
int get(char w){
if(w=='A')return 1;
if(w>'A'&&w<='Z')return 10;
return w-'0';
}
double cal(int x,int y){
if(x>21)return 0;
if(x>=y)return 1;
double ans=0;
for(int i=1;i<=9;i++)ans+=o*cal(x+i,y);
ans+=w*cal(x+10,y);
return ans;
}
double dfs(int x,int y){
if(f[x][y]>0)return f[x][y];
if(x>21)return 0;
double x2=0.0;
for(int i=1;i<=9;i++)x2+=o*dfs(x+i,y);
x2+=w*dfs(x+10,y);
if(x<y)return f[x][y]=x2;
return f[x][y]=max(1.0-g[y][x],x2);
}
int main(){
w=(double)4/13;o=(double)1/13;
/*for(i=2;i<=20;i++){
f[i][i][0]=1;
for(l=2;l<=20;l++)
for(j=1;j<=19;j++){
for(k=1;k<=10;k++){
if(k==10)u=w;else u=o;
if(l+k<=21)f[i][l+k][j]+=f[i][l][j-1]*u;
}
}
}*/
for(i=2;i<=20;i++){
for(j=2;j<=21;j++){
g[i][j]=cal(i,j);
}
}
for(i=2;i<=20;i++)
for(j=2;j<=20;j++)
f[i][j]=dfs(i,j);
/*for(l=2;l<=20;l++)
for(i=2;i<=20;i++){
for(k=0;k<=19;k++){
u=0;
for(j=2;j<=21;j++){
u+=f[i][j][k]*(1.00-g[l][j]);
}
h[i][l]=max(h[i][l],u);
}
}*/
for(scanf("%d",&T);T--;){
scanf("%s",s);
x=get(s[0])+get(s[1]);
y=get(s[2])+get(s[3]);
printf("%.3lf\n",f[x][y]);
if(f[x][y]>=0.500000001)puts("YES");else puts("NO");
}
}
BestCoder Round #68 (div.1)
开场看T2 10S后决定看T1，傻逼题，但因为进不了博客没有模板整整写了3min，暂时R2
然后看T2，K这么大大概是矩乘吧。。逆元相乘是对的么，似乎是对的。就赶紧写，由于摞了会20多min才写完。已经有五六个人A了。。
然后发现Claris早就把T3秒了。。可是我看了好久还是没什么头绪。。只好暴力找规律。。但似乎没有什么特别明显的规律
到oeis找一下，也没有发现。这时候数国队走过来说你把数列除以2试试看，果然有了，但似乎没有通式
然后再把前缀和放到oeis上找一找，发现就是1≤i＜j＜k≤n，gcd(i,j,k)=1的个数
就先写了个暴力，但是n好大啊。。似乎BZOJ看到过一道题可以O(n^2/3)求前缀和，觉得很神不会，忘了是那一道了。。
我在BZOJ上乱翻，可是没有翻出来，只有最后10min了。。Claris发了下那道题的题号
把题解的代码复到求前缀和的地方，但发现过不了。。只有2min了。。发现代码里面是前缀和，改了下在最后10S交了。。
最后HACK×一发掉到了R6，不过还不错，小涨一笔
int T,n,m,x,y,z,p,q,i,j,tot,ans,a[N],F[N],sz[N];
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
int main(){
for(scanf("%d",&T);T--;){
for(scanf("%d",&n),i=1;i<=n;i++)F[i]=i,sz[i]=1;
for(i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
if(!z){
p=gf(x);q=gf(y);
sz[q]+=sz[p];
F[p]=q;
}
}
ans=0;
for(i=1;i<=n;i++)ans^=sz[gf(i)];
printf("%d\n",ans);
}
}
int T,n,m,x,y,i,j,Q,u,k,tot,du[N],fir[55],ne[2222],la[2222];
long long w;
struct JZ{int x,y;long long m[55][55];}o,f,g;
JZ cheng(JZ a,JZ b){
JZ c;memset(c.m,0,sizeof c.m);
c.x=a.x;c.y=b.y;int i,j,k;
for(i=1;i<=a.x;i++)
for(j=1;j<=b.y;j++)
for(k=1;k<=a.y;k++)
c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%P)%P;
return c;
}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int main(){
for(;scanf("%d%d",&n,&m)!=EOF;){
CL(fir);tot=0;memset(o.m,0,sizeof o.m);CL(du);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y);
for(x=1;x<=n;x++){
w=pow(du[x],P-2,P);
for(i=fir[x];i;i=ne[i])o.m[x][la[i]]=w;
}
o.x=o.y=n;
for(scanf("%d",&Q);Q--;){
scanf("%d%d",&u,&k);
g=o;
memset(f.m,0,sizeof f.m);
f.x=1;f.y=n;
f.m[1][u]=1;
for(;k;k>>=1){
if(k&1)f=cheng(f,g);
g=cheng(g,g);
}
for(i=1;i<=n;i++)printf("%lld ",f.m[1][i]);
puts("");
}
}
}
int T,n,m,x,y,i,j,p,la,tot,a[N],u[N],sum[N],prime[N];bool f[N];long long ans;
map<int,LL>_mu;
LL MU(LL n){
map<int,LL>::iterator it;
if(n<M)return sum[n];
if((it=_mu.find(n))!=_mu.end())return it->second;
LL i,last,re=1;
for(i=2;i<=n;i=last+1){
last=n/(n/i);
re-=(last-i+1)*MU(n/i);
}
return (_mu[n]=re)%P;
}
int main(){
for(sum[1]=u[1]=1,i=2;i<=5000000;i++){
if(!f[i])prime[++p]=i,u[i]=-1;
for(j=1;j<=p&&i*prime[j]<=5000000;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0){
u[prime[j]*i]=0;
break;
}
u[prime[j]*i]=-u[i];
}
sum[i]=sum[i-1]+u[i];
}
for(scanf("%d",&T);T--;){
scanf("%d",&n);ans=0;
for(i=1;i<=n;i=la+1){
la=n/(n/i);
ans+=1ll*(n/i)*((n/i)-1)%P*((n/i)-2)%P*166666668%P*(MU(la)-MU(i-1)+P)%P;
}
printf("%lld\n",ans*2%P);
}
}
BestCoder Round #69 (div.1)
开场看T1码农题，就码码码，小号第一个过了，大号检查了一会才过
然后看T2，觉得是搜索傻逼题，写完第二个过
然后看T3，觉得是枚举第一行题，但发现我状态要4^n表示GG，然后就不知道在想什么，一直颓..
然后小号试了下T1，×了个人发现A＜B时算的是A..那我T1写错了曰
然后大号去找T1 A＜B的人，但是没有找到，然后发现T2被×了曰
然后看到一个T2字符串只开到15的人，去×，失败了两次曰，真是摸不着头脑【HACK作大死】
又看到一个只开到15的人，又失败了曰。。掉到了RK100，要掉紫了。。
最后测完T1没有FST，T2是实数精度问题，不过排名还是不能看，50+，早知道不HACK了不至于跌太惨。。【死于爆精度】
T3真是傻逼题啊，都想到枚举一列就可以判断状态了。。我在干什么都不知道。。太作死了，把号玩废了>_<
int T,n,m,x,y,i,j,A,B,o,w,u,tot,a[13],c[13]={0,31,29,31,30,31,30,31,31,30,31,30,31},b[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
long long ans;char s[19];bool ff;
int main(){
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d",&T);
for(;T--;){
scanf("%d",&n);scanf("%d%d",&A,&B);ans=0;
for(i=1;i<=n;i++){
scanf("%s",s+1);ff=0;
for(j=1;j<=11;j++)a[j]=s[j]-'0';
if(s[11]==s[10]&&s[10]==s[9]&&s[9]==s[8]&&s[8]==s[7])ff=1;
if(a[7]+1==a[8]&&a[8]+1==a[9]&&a[9]+1==a[10]&&a[10]+1==a[11])ff=1;
if(a[7]-1==a[8]&&a[8]-1==a[9]&&a[9]-1==a[10]&&a[10]-1==a[11])ff=1;
u=a[4]*1000+a[5]*100+a[6]*10+a[7];o=a[8]*10+a[9];w=a[10]*10+a[11];
if(u>=1980&&u<=2016){
if(u%4==0){
if(o>=1&&o<=12){
if(w>=1&&w<=c[o])ff=1;
}
}else{
if(o>=1&&o<=12){
if(w>=1&&w<=b[o])ff=1;
}
}
}
if(ff)ans+=max(A,B);else ans+=B;
}
printf("%I64d\n",ans);
}
}
int T,n,m,x,y,i,j,cnt,tot,pos[N][N],a[N],fir[N],va[M],ne[M],la[M];
long long sum;bool ff,v[N];char s[N][N];
void ins(int x,int y,char z){
la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;
if(z=='+')va[tot]=1;
if(z=='-')va[tot]=2;
if(z=='*')va[tot]=3;
if(z=='/')va[tot]=4;
}
void dfs(int x,LL y,LL z){
if((long double)z*sum==(long double)y)ff=1;
if(ff)return;
for(int i=fir[x];i;i=ne[i])if(!v[la[i]]){
v[la[i]]=1;
if(va[i]==1)dfs(la[i],y+z*a[la[i]],z);
if(va[i]==2)dfs(la[i],y-z*a[la[i]],z);
if(va[i]==3)dfs(la[i],y*a[la[i]],z);
if(va[i]==4&&a[la[i]]!=0)dfs(la[i],y,z*a[la[i]]);
v[la[i]]=0;
}
}
int main(){
//freopen("2.in","r",stdin);freopen("2.out","w",stdout);
scanf("%d",&T);
for(;T--;){
scanf("%d%d%lld",&n,&m,&sum);cnt=0;tot=0;ff=0;CL(fir);
for(i=1;i<=n;i++)scanf("%s",s[i]+1);
for(i=1;i<=n;i+=2)for(j=1;j<=m;j+=2)pos[i][j]=++cnt,a[cnt]=s[i][j]-'0';
for(i=1;i<=n;i+=2)for(j=1;j<=m;j+=2){
if(i!=1)ins(pos[i][j],pos[i-2][j],s[i-1][j]);
if(i!=n)ins(pos[i][j],pos[i+2][j],s[i+1][j]);
if(j!=1)ins(pos[i][j],pos[i][j-2],s[i][j-1]);
if(j!=m)ins(pos[i][j],pos[i][j+2],s[i][j+1]);
}
for(i=1;i<=cnt;i++){
v[i]=1;
dfs(i,a[i],1);
v[i]=0;
}
puts(ff?"Possible":"Impossible");
}
}
#include<bits/stdc++.h>
using namespace std;
int T,n,m,i,j,w,a[14][111],A[14][111],v[14][111];
int no(int x){return x<0||x>1;}
int G(int x,int y){return v[x][y-1]+v[x][y]+v[x][y+1];}
bool dfs(int x){
int i,j;bool ff;
if(x==n){
for(j=1;j<=m;j++)if(a[n][j]!=G(n-1,j))return 0;
if((++w)>=2)return 1;
return memcpy(A,v,sizeof(v)),0;
}
for(i=0;i<2;i++){
v[x+1][1]=i;ff=1;
for(j=2;j<=m&&ff;j++)if(no(v[x+1][j]=a[x][j-1]-G(x,j-1)-G(x-1,j-1)-v[x+1][j-1]-v[x+1][j-2]))ff=0;
if(!ff||a[x][m]!=G(x,m)+G(x-1,m)+v[x+1][m-1]+v[x+1][m]) continue;
if(dfs(x+1))return 1;
}return 0;
}
int main(){
for(scanf("%d",&T);T--;){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)
for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
w=0;memset(v,0,sizeof(v));
if(dfs(1))puts("Multiple");else if(!w)puts("Impossible");else
for(i=1;i<=n;i++)for(j=1;j<=m;j++)printf("%d%c",A[i][j],j==m?'\n':' ');
}
}
BestCoder Round #71(div.1)
T1好傻逼啊，写了一个，发现正好卡100000
算了下觉得ULL过不去？高精度！！！
写完发现被艹爆了..
T3被秒了？让我看看，这不原题么，让我找一找、、好傻逼的题啊，为什么不放到A题去啊。。
T4被秒了？让我看看，傻逼MST啊，让我上网拉拉板，然后发现有NM的？看来也能过，拉过来用用
不对。。T4拉过来的数组开小了，曰。。。
然后T2，想了一会，没什么办法，直接基环树上啊！！！！！
WA WA WA WA WA WA WA WA。。曰狗了。。错哪里了呢。。。
HACK时间到，T2让我n=1试试看，小号×成功两个，爽~
大号去×，连续×失败3个。。曰了，为什么没有和小号一样的RP
然后看T1，好多傻逼啊，我×××。。ULL竟然能过？自己才是傻逼啊。。
已经×错6发了，没什么希望了，看到一个T3数组开小的×掉。。
真是傻逼比赛。。自己太作死了啊、、
程序不贴了。。太傻逼了
BestCoder Round #72 (div.1)
开场T1，好难啊，曼哈顿凸包？
发现自己太愚蠢了，直接分类讨论判断就可以了吧。。写了一个炸了。把数组开大就A了
然后T2，似乎更傻逼，直接从高位到低位搞就好了，然后13分钟2A了
然后看T3，好长的数学公式啊，似乎不太可做
看T4，好难啊，感觉更不可做啊
回去想T3，发现可以nklgnDP，然后每次转移是一样的，然后就A了啊
就写了一个，直接A了。。
然后发现跑得好慢。。感觉要被卡。。
然后发现可以用最小表示法把程序加快几十倍啊。。问了下管理员，说两个log过得去，就懒得写了
HACK开始，先把小号×了。颓了会，突然发现T2被×了，然后发现有人×了20多发了
想了想，觉得肯定是n=1的自环，就又×了几个人玩
当然最后都不算啦。。最后测得时候发现T3被卡了TAT，为什么要作死啊QAQ，vector自带log【死于用vector】
int T,n,m,i,j,tot,a[N];
LL x[N],y[N],A1,A2,A3,A4,B1,B2,B3,B4;
LL seed;
inline long long rand(long long l, long long r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}
int main(){
scanf("%d",&T);
for(;T--;){
A1=A2=A3=A4=-1e18;B1=B2=B3=B4=1e18;
scanf("%d%I64d",&n,&seed);if(n==358)puts("!");
for (int i = 0; i < n; i++){
x[i] = rand(-1000000000, 1000000000),
y[i] = rand(-1000000000, 1000000000);
MAX(A1,x[i]+y[i]);MIN(B1,x[i]+y[i]);
MAX(A2,-x[i]+y[i]);MIN(B2,-x[i]+y[i]);
MAX(A3,-x[i]-y[i]);MIN(B3,-x[i]-y[i]);
MAX(A4,x[i]-y[i]);MIN(B4,x[i]-y[i]);
}
printf("%I64d\n",max(max(A1-B1,A2-B2),max(A3-B3,A4-B4)));
}
}
int T,n,m,x,y,i,j,tot,ans,a[N],b[N],c[N],F[N];bool gg[N],ff;
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
void uni(int x,int y){F[gf(x)]=gf(y);}
int main(){
freopen("BB.in","r",stdin);freopen("B.out","w",stdout);
scanf("%d",&T);
for(;T--;){
scanf("%d%d",&n,&m);ans=0;CL(gg);
for(i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(j=30;j>=0;j--){
for(i=1;i<=n;i++)F[i]=i;
for(i=1;i<=m;i++)if(!gg[i]&&(c[i]>>j&1))uni(a[i],b[i]);
ff=1;
for(i=1;i<=n;i++)if(gf(i)!=gf(1)){ff=0;break;}
if(ff)for(ans+=(1<<j),i=1;i<=m;i++)if(!gg[i])if(!(c[i]>>j&1))gg[i]=1;
}
printf("%d\n",ans);
}
}
int T,n,k,m,x,y,i,j,tot,cnt;vector<int>v[N];LL f[N],g[N],h[N],a[N];
int main(){
scanf("%d",&T);
for(i=1;i<N;i++)for(j=1;j*j<=i;j++)if(i%j==0){
v[i].push_back(j);
if(j*j!=i)v[i].push_back(i/j);
}
for(;T--;){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%I64d",&a[i]),f[i]=g[i]=1;
for(k--;k;k>>=1){
if(k&1){
CL(h);
for(i=1;i<=n;i++)for(j=0;j<v[i].size();j++)h[i]=(h[i]+g[v[i][j]]*f[i/v[i][j]])%M;
for(i=1;i<=n;i++)f[i]=h[i];
}
CL(h);
for(i=1;i<=n;i++)for(j=0;j<v[i].size();j++)h[i]=(h[i]+g[v[i][j]]*g[i/v[i][j]])%M;
for(i=1;i<=n;i++)g[i]=h[i];
}
CL(h);
for(i=1;i<=n;i++)for(j=0;j<v[i].size();j++)h[i]=(h[i]+a[v[i][j]]*f[i/v[i][j]])%M;
for(i=1;i<=n;i++)printf("%I64d%c",h[i],i==n?'\n':' ');
}
}
int O,T,n,k,m,x,y,i,j,tot,cnt;LL f[N],g[N],h[N],a[N];
int main(){
scanf("%d",&T);
for(;T--;){
scanf("%d%d",&n,&O);
for(i=1;i<=n;i++)scanf("%I64d",&a[i]),f[i]=g[i]=1;
for(O--;O;O>>=1){
if(O&1){
CL(h);
for(j=1;j<=n;j++)for(k=1;j*k<=n;k++)h[j*k]=(h[j*k]+g[j]*f[k])%M;
//for(i=1;i<=n;i++)for(j=0;j<v[i].size();j++)h[i]=(h[i]+g[v[i][j]]*f[i/v[i][j]])%M;
for(i=1;i<=n;i++)f[i]=h[i];
}
CL(h);
for(j=1;j<=n;j++)for(k=1;j*k<=n;k++)h[j*k]=(h[j*k]+g[j]*g[k])%M;
for(i=1;i<=n;i++)g[i]=h[i];
}
CL(h);
for(j=1;j<=n;j++)for(k=1;j*k<=n;k++)h[j*k]=(h[j*k]+a[j]*f[k])%M;
for(i=1;i<=n;i++)printf("%I64d%c",h[i],i==n?'\n':' ');
}
}
BestCoder Round #74 (div.1)
开场看T1，好难啊。。完全没有一点思路QAQ。。弃疗看T2，好难啊。。颓了5分钟多回来弄T1
手写了个大力8*8的建图（这是打字比赛么。。），然后20分钟才A。。然后想T2似乎不太会，就没给大号交。。
然后看T2，觉得直接DP就好了啊，就给大号交了T1，交完后发现DP是不对的TAT。。
然后发现可以BFS，就写了发，但边似乎有点多啊。。先交一发MLE了。。然后改成不建边的才A。。
然后看T3，似乎不是很难的样子。。感觉只要找出≤k中标号最小的点就好了。。感觉线段树就可以弄啦。。在1个多小时的时候A掉。
然后看T4，这TM能做？听Claris说是智商题，我这种没有智商的选手还是弃疗算了。。
最后测完RANK5，竟然获得了历史最佳排名。。
int T,n,m,x,y,h,t,I,i,j,tot,A1,B1,A2,B2,A3,B3,a[N],d[9],q[N],fir[9],ne[99],la[99],va[99];bool v[9];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;la[++tot]=x;va[tot]=z;ne[tot]=fir[y];fir[y]=tot;}
int main(){
freopen("A.in","r",stdin);freopen("A.out","w",stdout);
scanf("%d",&T);
for(;T--;){LL S=0;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d%d%d",&A1,&B1,&A2,&B2,&A3,&B3);
for(I=1;I<=m;I++){
scanf("%d%d",&x,&y);CL(fir);tot=0;
ins(3,4,1);ins(5,6,1);ins(7,8,1);
ins(1,2,abs(x-y));
ins(1,3,abs(x-A1));
ins(1,4,abs(x-B1));
ins(1,5,abs(x-A2));
ins(1,6,abs(x-B2));
ins(1,7,abs(x-A3));
ins(1,8,abs(x-B3));
ins(2,3,abs(y-A1));
ins(2,4,abs(y-B1));
ins(2,5,abs(y-A2));
ins(2,6,abs(y-B2));
ins(2,7,abs(y-A3));
ins(2,8,abs(y-B3));
ins(3,5,abs(A1-A2));
ins(3,6,abs(A1-B2));
ins(3,7,abs(A1-A3));
ins(3,8,abs(A1-B3));
ins(4,5,abs(B1-A2));
ins(4,6,abs(B1-B2));
ins(4,7,abs(B1-A3));
ins(4,8,abs(B1-B3));
ins(5,7,abs(A2-A3));
ins(5,8,abs(A2-B3));
ins(6,7,abs(B2-A3));
ins(6,8,abs(B2-B3));
for(memset(d,63,sizeof(d)),CL(v),h=d[q[t=1]=1]=0,v[1]=1;h^t;)
for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[++t]=y]=1;
S=(S+1ll*I*d[2])%M;
}
printf("%lld\n",S);
//fr(i,n)scanf("%d",&a[i]);
}
}
int T,n,m,x,y,i,j,h,t,tot,a[N],d[N],q[N];//la[W],ne[W],fir[W];
int main(){
freopen("B.in","r",stdin);freopen("B.out","w",stdout);
scanf("%d",&T);
for(;T--;){
LL S=0;
scanf("%d%d",&n,&m);memset(d,63,sizeof(d));
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(h=0,q[t=1]=0,d[0]=0;h^t;){
x=q[++h];
for(i=0;i<=16;i++){
y=x^(1<<i);
if(d[y]>1e7){
d[y]=d[x]+1;q[++t]=y;
}
}
for(i=1;i<=n;i++){
y=x^a[i];
if(d[y]>1e7){
d[y]=d[x]+1;q[++t]=y;
}
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
S=(S+1ll*i*d[x^y])%M;
}
printf("%lld\n",S);
//fr(i,n)scanf("%d",&a[i]);
}
}
int T,n,m,x,y,i,j,k,h,t,tot,a[N],du[N],la[N*2],ne[N*2],fir[N],mv[N*4];bool v[N];
void ins(int x,int y){
la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[y]++;
}
void bt(int k,int l,int r){
if(l==r){mv[k]=du[l];return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
mv[k]=min(mv[k<<1],mv[k<<1|1]);
}
int get(int k,int l,int r,int x){
if(l==r){
if(mv[k]<=x)return l;else return -1;
}
int mid=l+r>>1;
if(mv[k<<1]<=x)return get(k<<1,l,mid,x);
if(mv[k<<1|1]<=x)return get(k<<1|1,mid+1,r,x);
return -1;
}
void cha(int k,int l,int r,int x,int z){
if(l==r){mv[k]=z;return;}
int mid=l+r>>1;
if(x<=mid)cha(k<<1,l,mid,x,z);else cha(k<<1|1,mid+1,r,x,z);
mv[k]=min(mv[k<<1],mv[k<<1|1]);
}
int main(){
scanf("%d",&T);
for(;T--;){
CL(fir);tot=0;CL(du);CL(v);CL(mv);LL S=0;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y);
bt(1,1,n);
for(i=1;i<=n;i++){
x=get(1,1,n,k);
S=(S+1ll*i*x)%M;
cha(1,1,n,x,1e9);k-=du[x];v[x]=1;
for(int j=fir[x];j;j=ne[j]){
du[la[j]]--;
if(!v[la[j]])cha(1,1,n,la[j],du[la[j]]);
}
}
printf("%lld\n",S);
//fr(i,n)scanf("%d",&a[i]);
}
}
BestCoder Round #75
开场秒C，真是太愚蠢了。然后把A也秒了。
然后开D，感觉要打表，要写很久的样子。就去看B，感觉直接模拟就好了。
写了发，无限WA，眼睛看了10MIN还是没看出来。然后去摞D了，5分钟不到打出表A了。。
然后继续B，发现读入的数可能很大。。改一下就A了。。曰
然后看E，就是道傻逼费用流嘛。。调了一会调出来了，爆了几发A了。。
然后就颓了一个小时。。
最后测前发现T3数组开小了。。好虚啊。。
测完发现T3过了，T2 FST了。。原来TM读入大数的vis数组RE了。。
曰狗了。。T2消耗了我20MIN，让我直接损失850分间接损失500分。。直接从#4跌到#15，以至于差了4分没有上粉QAQ
int T,n,m,x,y,i,j,tot,a[N];
int get(int n,int m){
if(!n||!m)return 0;
if(n<m)swap(n,m);
return get(n-m,m)+1;
}
int main(){
scanf("%d",&T);
for(;T--;){
scanf("%d%d",&n,&m);
printf("%d\n",get(n,m));
//fr(i,n)scanf("%d",&a[i]);
}
}
int T,n,m,x,y,i,j,tot,a[N];int sz[12];bool v[12],ff;
int main(){
scanf("%d",&T);
for(;T--;){
scanf("%d",&n);
CL(sz);ff=1;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>9||a[i]==0)ff=0;else{
sz[a[i]]++;
if(sz[a[i]]>1)ff=0;
}
}
for(i=1;i<=9;i++)v[i]=1;
if(n<4)ff=0;
for(i=1;i<n;i++){
v[a[i]]=0;
if(a[i]==1&&a[i+1]==3||a[i]==3&&a[i+1]==1){
if(v[2])ff=0;
}
if(a[i]==4&&a[i+1]==6||a[i]==6&&a[i+1]==4){
if(v[5])ff=0;
}
if(a[i]==7&&a[i+1]==9||a[i]==9&&a[i+1]==7){
if(v[8])ff=0;
}
if(a[i]==1&&a[i+1]==7||a[i]==7&&a[i+1]==1){
if(v[4])ff=0;
}
if(a[i]==2&&a[i+1]==8||a[i]==8&&a[i+1]==2){
if(v[5])ff=0;
}
if(a[i]==3&&a[i+1]==9||a[i]==9&&a[i+1]==3){
if(v[6])ff=0;
}
if(a[i]==1&&a[i+1]==9||a[i]==9&&a[i+1]==1||a[i]==3&&a[i+1]==7||a[i]==7&&a[i+1]==3){
if(v[5])ff=0;
}
}
puts(ff?"valid":"invalid");
//fr(i,n)scanf("%d",&a[i]);
}
}
int T,n,m,x,y,i,j,tot,a[N];
int get(int n,int m){
if(!n||!m)return 0;
if(n<m)swap(n,m);
return get(n-m,m)+1;
}
int main(){
scanf("%d",&T);
for(;T--;){
scanf("%d%d",&n,&m);
printf("%d\n",get(n,m));
//fr(i,n)scanf("%d",&a[i]);
}
}
#include<cstdio>
int a[]={0,1,2,2,2,4,5,4,8,8,7,11,8,13,4,11,12,8,12,2,13,7,22,2,8,13,26,4,26,29,17,27,26,7,33,20,16,22,29,4,13,22,25,14,22,37,18,46,42,46,9,41,12,7,26,42,24,5,44,53,52,58,29,22,12,48,27,30,58,52,49,57,13,14,32,24,75,8,67,56,40,61,51,77,35,57,74,63,75,12,72,89,11,32,32,59,61,62,89,22,31,67,33,101,101,34,74,90,89,61,73,18,26,72,96,25,53,93,42,11,80,42,94,32,80,12,7,97,22,82,119,94,88,60,123,88,119,76,128,34,116,57,140,103,133,107,44,100,53,20,51,12,74,59,146,111,13,119,39,9,142,31,154,99,26,5,99,110,135,155,99,86,2,8,49,16,126,149,76,123,101,168,128,94,51,38,107,119,70,64,149,4,62,94,99,61,2,39,164,149,73,109,83,81,169,26,181,166,109,140,89,64,62,94,30,168,27,31,192,82,215,7,184,199,158,198,215,62,157,58,18,51,200,57,226,2,236,50,106,188,22,128,149,162,206,228,150,26,205,18,9,107,68,188,165,184,238,48,95,92,62,143,164,238,156,64,86,134,130,245,258,252,62,191,138,71,243,102,111,187,25,95,59,186,185,274,111,261,72,272,42,137,235,62,86,144,193,77,146,265,156,54,188,40,49,125,110,16,29,218,219,68,138,268,70,223,296,142,146,247,49,133,310,131,63,60,94,315,59,240,177,14,226,332,164,94,53,227,33,130,331,97,23,316,114,271,67,339,330,247,299,189,278,158,283,54,215,49,219,157,31,344,128,37,213,335,57,298,102,9,356,99,362,342,133,14,121,30,64,314,102,318,209,41,34,57,247,77,219,96,248,177,238,169,268,342,347,256,31,278,118,369,33,395,229,16,218,158,208,250,9,335,75,93,146,399,230,116,357,372,282,257,193,152,269,131,233,258,7,376,170,222,244,242,393,407,154,47,286,191,422,340,217,83,209,233,374,355,144,87,266,238,44,363,197,240,377,297,167,453,282,279,387,358,254,107,414,427,117,220,342,333,177,199,396,280,113,22,348,14,424,162,86,339,219,141,408,432,117,108,400,436,236,195,145,456,295,371,122,69,360,312,197,108,326,396,259,161,197,20,385,369,225,161,8,182,358,215,224,167,124,42,225,263,96,100,26,129,330,524,214,247,187,31,380,334,183,251,254,366,336,56,482,491,206,278,39,162,107,14,441,13,189,330,297,238,104,298,552,491,456,480,310,396,73,205,59,177,208,75,447,520,394,402,332,507,157,268,196,388,249,179,498,493,471,577,501,85,316,580,508,502,458,488,241,316,363,395,259,589,113,255,256,364,240,288,27,304,172,182,73,319,126,152,172,379,170,420,110,151,156,199,217,258,560,383,132,379,290,537,76,360,281,329,389,568,425,440,487,553,466,531,318,619,541,23,25,246,27,205,157,226,212,445,193,420,338,249,457,250,439,594,12,285,256,298,68,265,290,287,391,47,443,524,650,193,104,202,344,234,449,639,385,98,519,237,591,228,305,457,441,518,631,73,112,346,74,298,500,539,673,588,670,248,316,262,513,705,405,140,229,260,339,639,477,637,706,125,218,609,196,600,89,285,377,472,508,697,485,24,142,535,421,76,176,320,358,597,641,643,590,320,407,554,518,250,194,459,434,110,660,203,475,530,719,313,686,275,411,735,727,285,146,572,627,160,369,82,398,320,169,421,508,187,123,356,384,747,64,449,101,26,118,228,410,684,540,179,299,726,16,385,44,737,97,391,344,88,740,197,436,713,114,433,308,38,140,377,785,223,65,422,505,192,333,771,645,169,263,679,245,389,396,823,64,458,671,117,57,795,16,477,422,96,75,343,501,418,359,230,552,274,590,77,392,773,650,464,419,783,159,20,584,223,424,843,111,708,590,127,483,793,164,628,510,479,408,633,159,635,708,173,553,125,162,76,841,369,716,324,529,638,852,445,669,31,481,243,814,752,90,632,813,209,546,662,196,810,894,761,700,219,629,892,535,779,714,706,806,272,578,157,233,866,297,786,123,576,793,312,396,57,264,223,829,639,219,508,853,527,560,116,501,866,200,933,292,573,867,575,885,454,607,199,329,69,428,199,229,892,257,611,770,636,787,213,635,420,790,479,134,164,386,145,475,33,882,585,107,428,867,766,669,540,967,559,855,526,696,973,592,184,635,321,262,237,474,60,715,183,35,678,261,941,244,131,192,656,335,609,154,669,947,635,952,589,79,825,891,569,63,685,918,850,64,377,58,526,75,268,754,535,925,696,116,879,999,708,1019,880,984,71,923,810,394,127,450,198,409,835,348,143,524,194,178,54,545,274,840,608,604,14,819,417,787,509,965,322,1013,661,310,867,983,900,194,815,238,1061,262,1063,714,316,613,559,725,239,899,447,87,151,862,902,327,110,612,118,212,123,626,407,816,832,994,705,59,943,529,193,437,1068,660,410,982,377,838,728,1017,738,375,1023,489,81,758,433,774,938,936,734,281,1036,567,1010,477,194,830,309,939,902,984,1059,619,212,591,480,818,483,951,811,129,212,170,307,1020,781,112,958,62,125,402,181,676,726,1149,718,222,1091,506,329,988,634,843,639,436,1133,509,295,921,668,89,1023,376,96,829,471,966,1136,238,1135,283,184,1124,870,997,1024,479,1109,970,841,1009,62,387,264,875,668,118,789,320,46,765,891,692,819,614,295,1004,520,1013,914,473,280,610,775,1148,982,680,478,1017,1141,269,1093,686,550,1000,672,50,133,871,538,82,117,365,466,984,712,127,517,490,482,112,798,634,342,504,778,184,1153,656,567,748,1157,451,546,1168,1224,1252,104,836,566,321,185,322,184,282,2,681,263,836,956,389,63,1062,1195,176,65,797,737,195,360,678,394,1202,843,932,747,906,11,786,586,41,1214,244,209,1132,872,742,785,1209,961,481,183,1187,889,63,1235,1112,680,364,359,1073,1027,530,236,76,82,580,135,1057,776,424,835,960,994,860,574,341,1307,743,730,151,82,298,1133,46,1239,1310,909,420,607,1200,798,525,578,1316,1127,63,221,342,1269,863,697,358,243,1079,911,688,545,1300,1152,952,931,131,1253,544,764,1324,35,1199,977,414,696,131,83,784,1171,35,175,927,759,590,1005,1046,283,1013,1044,824,424,1182,1247,514,469,148,374,976,1120,801,531,211,221,1105,922,248,464,1353,176,587,886,361,257,31,71,852,685,358,426,1335,124,677,690,234,419,31,1311,515,788,319,389,1414,103,669,1300,545,330,162,82,886,499,596,372,206,470,486,1154,868,862,610,145,1192,1356,862,799,370,701,1262,61,166,1253,746,1202,218,46,1199,1387,915,1050,254,527,223,246,179,5,692,492,215,458,251,601,1287,816,997,1077,613,713,1158,1256,1100,963,873,1473,162,549,239,510,1450,150,884,775,902,434,639,813,766,1343,1154,1413,1065,963,252,532,354,418,34,489,944,1075,956,995,854,1055,399,63,1453,1511,1292,1369,512,1052,494,560,650,803,173,1286,1491,1413,965,4,486,802,982,655,544,320,1514,1522,1413,1374,1354,1438,216,777,915,608,311,865,58,241,1291,266,1500,303,730,1005,947,1318,1007,730,69,573,1388,348,1364,47,1096,1253,1402,159,1050,1216,865,578,818,669,777,572,1412,723,1565,356,200,82,1017,1432,1458,962,975,1544,786,1089,930,790,587,602,295,550,82,303,219,853,1472,279,145,56,1324,386,1173,1205,1080,1367,942,1543,158,947,651,1071,1095,919,712,720,620,455,467,772,8,728,809,756,283,576,110,1489,1257,188,230,296,1151,371,92,1569,250,267,1311,115,1406,67,1410,380,951,1292,1319,1478,1511,1611,1140,134,1297,1377,1186,150,754,1526,1144,19,1237,174,1160,1067,988,1508,1170,705,202,1449,1161,50,133,128,1155,1635,1111,1534,1476,400,1213,88,1659,348,1670,221,1472,1614,1445,353,236,449,1630,186,38,372,483,507,1688,214,506,705,505,838,289,506,534,974,1179,825,130,785,782,769,1070,1709,756,1385,1473,1590,1527,1686,1459,1379,1734,291,1673,945,1250,538,498,574,851,825,459,934,852,1143,312,1434,685,1240,1093,1363,1418,215,1517,375,34,217,398,549,1715,523,735,615,943,1299,740,1336,1117,1205,1060,142,1193,1563,111,736,471,376,1691,560,164,537,676,1459,758,1289,1733,1755,1448,217,1729,1779,284,677,732,1672,514,1231,895,1455,1448,1530,1399,198,334,295,116,1114,625,839,1103,1642,1107,141,7,204,8,186,244,803,103,705,801,1075,1254,1583,1371,1804,49,712,173,1278,633,1353,711,1612,37,1714,1462,297,101,394,938,1255,775,1662,1672,288,1683,832,317,315,645,921,1172,121,1153,1696,280,436,587,943,478,1168,1088,93,1383,427,1777,330,1080,1251,1098,240,1591,368,1591,48,505,1006,481,1556,1374,52,154,831,134,835,768,1245,1367,636,356,1865,424,933,1085,1503,1214,1867,1450,267,542,1196,598,1748,1559,1835,1744,845,388,516,1163,1219,1855,806,1713,556,1116,1285,1355,1806,1526,206,533,844,917,114,1523,68,32,690,1175,1898,1332,1320,1884,443,732,1137,621,1748,20,381,859,1206,997,1135,1403,332,361,1210,790,1199,1476,158,127,733,173,1480,1108,1635,1934,529,67,1179,1441,34,115,1014,831,1190,729,1568,50,1215,1889,745,1441,109,315,829,295,1443,1230,114,1359,1017,487,1416,1585,138,396,896,852,1133,1444,251,520,1167,527,1791,1613,601,211,871,947,1570,17,998,618,1774,1271,33,76,784,775,1511,1295,1995,433,576,1092,1761,1322,882,924,1944,1325,439,1907,787,597,1193,1687,1477,41,1322,1473,303,205,891,499,1853,1547,427,96,1516,1297,495,348,945,1021,79,95,244,1172,1241,1496,593,243,890,1460,1650,1957,809,956,1616,1723,825,687,1874,1365,1846,367,1104,1499,1800,119,675,735,1826,1756,718,149,167,1594,578,652,1362,1604,2043,1992,1047,1542,636,1131,1076,1471,73,1925,1031,753,1590,1696,293,649,1950,1760,549,821,1219,1362,597,651,912,1317,1936,601,1440,1075,1713,392,939,1144,228,2072,542,1190,1817,230,1643,972,2,1967,870,1719,1954,1369,893,1141,1338,2096,1074,638,72,117,955,1392,22,199,546,920,163,128,1548,189,1758,557,1095,1287,2133,1869,970,1347,2137,295,1424,865,345,822,1005,1867,390,260,1194,1477,308,311,1966,973,360,1076,1591,207,1183,647,1244,1919,410,819,256,1898,1074,1402,7,656,1292,938,2060,130,1014,1691,587,894,1681,4,732,1105,2180,2024,769,1070,1884,345,1988,1012,4,381,1898,7,407,936,1676,1709,761,977,643,2106,827,1799,798,757,2054,1800,265,1287,1916,240,1350,470,433,514,1261,2070,450,463,1456,155,935,1066,1108,547,1444,1907,427,735,1472,1616,746,1416,148,270,1952,1346,699,767,2105,2221,1628,1249,1630,541,1199,1842,1101,360,1716,237,1560,2132,371,402,1985,1924,193,1017,379,8,1403,152,1131,1135,2274,83,714,1426,555,1037,2024,1180,849,1438,43,1212,1890,1954,1000,1298,2147,817,2101,1737,515,1201,111,364,1568,1654,655,1224,1704,365,1684,1750,1409,831,2147,486,1692,1687,2216,952,1701,201,33,534,620,1216,24,931,1399,1072,1141,1115,1662,331,2192,2115,744,1231,143,981,1800,258,195,1818,180,794,2025,2013,1388,1571,262,1436,1986,1758,636,1752,402,1073,483,2280,656,1550,522,1465,2345,269,1886,1909,998,1157,1098,518,2017,606,1306,2134,955,778,2124,710,1720,2195,1763,287,41,1273,47,773,1323,1555,909,1262,13,614,2343,1908,1263,1903,1224,972,543,689,1255,2268,935,1808,885,952,2279,336,1732,523,1067,1027,442,777,1909,330,2225,1896,1091,1744,767,1387,2304,213,1552,2101,554,2403,722,978,2442,444,1715,2248,1658,1524,266,1157,196,750,132,1825,921,1986,994,1872,2413,799,2372,516,1876,2096,1637,1387,290,1301,73,810,211,2352,1274,2171,864,1601,419,481,71,444,1800,2359,1362,1676,670,1738,471,793,142,2235,1781,654,1457,2313,525,1473,357,586,1915,491,1896,2175,1459,2287,1161,1436,1179,975,2352,567,1714,156,474,1103,552,2141,699,1698,546,522,1987,2328,1473,2379,2231,1720,1013,2111,1085,1331,695,1024,1987,2404,1502,355,2139,1510,1205,1802,574,1552,323,1327,2461,776,1947,173,2371,2434,1017,2044,494,1888,2376,85,2284,781,1797,578,2493,1840,1809,2109,574,2100,734,1920,2174,1202,2414,845,213,1886,2089,642,1565,534,889,1744,940,1398,2354,880,695,537,2139,1256,2207,974,17,60,1290,1841,1443,282,1147,787,332,2066,318,1154,586,194,1541,603,2575,132,2055,2436,970,2520,1434,2310,1155,914,583,1221,2519,1320,2609,104,70,661,2584,394,60,2537,1305,100,1174,102,2119,1597,1441,1758,807,2215,931,567,671,1530,2520,1332,573,2642,2508,931,2394,349,2455,529,1648,457,1895,2455,1810,1494,987,2289,1271,141,1448,2055,541,1749,825,1436,656,1196,256,833,211,1337,1954,356,2086,269,2257,652,2598,2345,2432,810,1885,2664,2532,298,996,2101,1410,2326,2365,1602,1352,2545,1247,2597,1168,1590,1032,2259,1178,1488,1284,1137,706,1852,964,1801,1335,1673,294,1597,308,1521,296,522,49,1569,302,845,202,1082,2664,642,2730,1349,1344,756,2288,882,424,855,2547,446,2473,2712,1773,727,189,62,50,1016,2734,413,2748,1178,1869,391,2317,1286,205,17,2753,1162,2289,1295,2730,2731,2340,812,1958,1012,2675,2683,2645,965,2375,1284,177,1012,2508,766,2608,675,158,274,434,1258,2605,1551,130,1370,2251,834,709,728,718,1230,239,1716,241,2064,914,1323,476,1316,569,2540,1153,559,1082,2033,766,1930,1608,1975,876,1741,1173,2783,2238,1391,1258,148,2107,407,2462,2142,1765,297,2029,161,2065,385,2233,1224,490,1562,724,959,2142,772,2682,1370,708,1220,770,1626,746,1941,1114,1515,782,2617,1250,2454,2371,2068,1468,2722,1562,236,2511,2669,2313,768,1672,661,414,141,220,1094,70,1040,783,1576,654,1779,892,2716,2614,1977,1138,2669,2274,658,1668,62,2183,623,2542,16,605,480,513,1299,925,2550,1392,1759,640,2511,1558,2751,1957,1409,2336,635,2693,762,100,721,593,1622,143,1303,987,1724,547,2877,979,302,1215,1994,1693,299,1866,201,2504,382,2889,1238,764,1739,1683,1758,763,2127,1324,2832,624,1760,2037,714,336,1523,234,169,453,1493,1166,1377,2548,2612,1747,2946,2168,2862,2648,539,2497,1432,2857,2040,923,1767,1161,2275,1529,61,1707,2947,2474,1233,2264,1400,1049,1433,856,1871,638,129,1500,2106,1744,405,1986,1096,373,1000,1064,1231,1347,2572,2237,2231,1232,178,2493,1148,511,2915,529,2867,1305,2794,1240,2822,2696,2829,2319,499,621,1525,726,2694,1255,2433,2427,113,2384,636,2785,1291,3011,485,736,2124,1036,292,2580,3019,2536,768,2917,1230,1417,1984,758,2676,2065,2994,2453,299,2579,1071,530,2477,1690,1759,2639,2921,2460,889,532,1245,272,1503,980,2653,2769,2258,2404,880,556,1855,661,1756,1478,2646,2030,562,509,1083,326,2115,1482,1972,2546,2904,1610,602,2865,1344,444,1086,1447,2339,1790,1287,2877,862,26,1557,660,2398,2526,2929,2673,916,96,2073,910,1801,1184,2644,1728,889,109,1329,740,1892,1571,324,2871,326,2091,1386,722,1986,2221,2154,1704,559,3082,2251,468,1823,1581,2606,2327,110,865,913,3021,2629,2213,3084,2704,3118,2276,1377,673,2543,1486,1989,2466,382,657,2024,1472,1447,1439,2912,2178,1253,1214,2133,591,2967,2558,76,2274,310,226,1551,1028,151,2893,739,2855,1528,725,1859,1862,2570,2046,1105,2374,1515,2704,1812,1651,752,3008,2648,614,1610,1470,3010,1642,350,606,1170,889,546,2826,966,319,2208,751,2835,2270,350,3102,336,959,1397,1190,34,2191,411,77,1847,1250,3113,2192,387,2777,1645,689,2669,979,2751,2638,1129,344,2475,2115,2300,2759,2169,2876,2490,2079,3080,2110,813,3136,1667,2005,1909,2079,962,313,2727,1314,2821,2640,375,2545,1005,1739,2902,2549,1544,358,2063,1320,155,1445,41,286,2004,1870,2496,2465,466,13,2065,1759,2022,2115,1049,3070,2096,1514,2604,1905,883,529,2159,1195,2606,2143,1014,3104,2285,2225,2363,377,1579,407,2220,2099,2995,2179,1219,268,2851,3205,2426,3134,1927,1374,182,2424,543,334,1236,1218,2732,3181,797,644,2902,1676,3214,314,1414,3295,2589,2003,654,125,927,1281,3104,1968,1297,854,1910,958,3205,2987,910,1099,2044,1548,752,37,2730,1597,2437,2611,452,302,2536,2289,3093,3337,2061,1358,22,3112,739,2838,1611,1858,755,1001,3274,695,3180,2522,1125,850,1677,1253,3293,2779,1557,1444,2165,1980,921,270,1496,1712,408,2070,1666,375,2692,123,3218,679,2124,1337,49,3273,1241,310,2744,2525,661,1852,2134,1793,997,3355,3011,739,2371,2307,1152,3324,2632,3018,535,416,2495,1956,63,461,1918,400,3078,3045,663,1814,2077,2053,824,255,2826,1542,3236,133,1564,805,2925,2603,943,64,230,2331,632,749,2387,2014,52,2953,1456,2550,2565,3252,1900,86,3193,2830,1021,160,2384,2867,50,1125,2326,1496,699,3246,2241,1906,117,2803,1418,622,179,3139,722,1387,2766,2611,422,1226,2665,1560,335,493,2264,3072,3208,17,1997,1777,658,299,1098,1557,3315,2660,1628,2309,2427,3196,1966,1745,3177,2812,1776,3335,2683,1943,2086,1510,2109,2772,1257,536,3093,2332,552,3188,2995,2397,1077,1908,2445,1898,1091,50,2596,1984,3270,149,2057,1786,359,1025,1938,1788,660,3376,2355,1998,441,2816,2192,2276,272,1213,1202,1136,605,3327,3322,2125,3475,3273,2234,1046,266,1030,577,1290,980,1001,2819,2914,473,3393,2279,2135,1514,693,590,1766,1445,208,2974,2578,3451,3031,2797,2546,1145,1712,2681,1665,1465,1188,195,2766,402,270,2259,2024,652,2511,2712,2766,1879,1737,3543,417,1518,243,271,2267,2078,3575,2509,3482,2558,1744,804,733,1076,1748,1152,654,1917,3311,1115,285,3085,2865,1993,1219,3464,2937,1320,1411,116,128,1457,1304,3417,3406,2237,1932,667,193,2773,2282,728,2288,2873,2823,1519,1572,3365,2778,1375,1164,366,3313,1682,2001,3530,271,3355,2823,748,874,2642,2512,650,425,3494,101,627,1772,1098,809,2807,2231,83,918,2063,2187,944,1139,3634,3660,2325,2362,1054,1029,2627,1988,805,3672,2932,2631,1065,1386,3184,3319,2137,1881,130,115,2726,2092,1623,1889,3022,2852,1720,1626,433,3559,1669,2475,791,173,3413,3539,1026,2070,196,3208,1957,2030,972,3165,3162,2702,1712,2137,3323,3491,2029,2083,977,433,2638,2154,1249,1302,3495,3505,2234,2162,633,627,3212,332,1635,360,380,3293,2364,2856,3637,411,3168,3488,2739,1945,3311,196,2285,2161,648,1590,2348,3073,2983,1103,1362,540,1307,2544,1011,1300,3756,49,2142,2060,1065,710,3180,333,1415,1255,508,3037,183,769,3586,256,3770,399,2888,2130,3594,454,3394,3290,1733,2823,623,1463,2950,3661,1982,2869,3096,3576,3550,2225,2434,2035,2451,3795,2886,2272,1011,969,3057,3201,1956,1877,1347,1950,2864,2743,2510,2037,971,115,2042,3063,1964,1124,391,748,2690,3084,1932,1789,1105,1057,3140,2322,1543,612,3388,1405,1635,1974,2464,2176,1137,3726,2773,2785,1736,1672,3623,1384,2366,2625,2409,1679,474,840,2641,2560,1136,2281,336,199,1669,2202,1762,1542,386,3777,3226,3015,1762,2110,192,522,3387,2643,2482,2219,295,3845,2276,2874,1892,1441,1234,764,3026,598,3014,3345,1090,2088,3419,3375,1420,1648,1935,2587,3098,374,3779,2570,2196,2164,3532,793,2842,2715,2274,2688,1097,1312,266,3640,2051,3376,1321,981,568,3813,3100,3424,941,2310,493,42,3918,3354,2460,2178,750,1145,3862,710,2646,1839,1614,2081,526,895,2207,2453,1629,1715,1324,1018,2608,391,2843,2785,1936,2082,1239,2925,3268,3195,2478,3126,3031,984,887,3743,49,2579,1304,2396,23,486,2966,73,1701,2257,2142,2199,891,1525,2586,2910,2256,2745,860,880,2521,3649,3471,3135,3084,2671,546,87,3544,2944,2971,575,1254,497,411,1038,3763,3959,1760,2713,498,1205,1339,1644,2578,12,2565,2782,1885,1327,3883,3883,80,8,3006,3551,647,1441,785,847,783,3555,2198,2160,2129,1306,1503,791,2592,3550,3199,3227,2478,2271,1042,3768,3473,3914,2527,37,1166,2612,787,958,1434,1595,2681,2743,2720,1875,691,2034,3763,620,186,3762,3400,2421,1356,1926,208,907,3186,797,2295,3121,2616,2045,1013,2442,72,3794,3316,3594,3046,93,597,1409,691,1350,1015,419,3286,3372,1284,2695,1241,2618,63,4059,694,890,3176,3960,2007,1574,1131,2361,1053,455,2968,260,2705,3252,1734,2375,658,1138,1143,763,3584,68,2511,2870,2289,3144,821,1334,3415,620,3650,3180,3332,3775,1691,2199,1886,787,3845,839,3900,3276,2458,2303,2409,3539,3682,1952,4098,870,728,79,2596,2670,1842,1664,939,2654,20,1246,1087,1154,811,11,2771,1423,1841,1948,2463,1463,3199,647,4074,4020,3674,292,2572,3634,3097,2811,422,2618,3713,3582,76,3203,3993,3272,1769,3043,1527,1571,947,1793,2909,1163,4184,431,3312,4128,2322,2243,1069,1782,1175,3326,2361,939,3918,1193,3507,3662,1494,2574,1085,2075,1818,2938,1054,1155,970,1067,3656,892,2098,2244,2874,1917,2738,3069,713,1514,473,221,723,294,2253,3056,2751,2958,2440,3053,1460,1145,384,1357,1645,383,3860,3743,2912,3216,2235,3720,973,3041,1816,2418,1744,2229,581,3733,4135,999,3392,1921,1724,3551,3161,3118,3401,2998,1247,2306,890,1374,398,2199,3007,119,3842,4228,2784,3435,2949,2875,2117,2254,1693,1870,3784,445,438,4266,229,1513,3454,83,3448,3470,1784,3899,2620,2477,1759,2552,3017,1698,130,982,54,197,413,968,3227,339,3834,206,2824,3149,1923,1848,1411,2344,1446,3215,430,992,1051,920,354,1519,3404,769,4051,3301,2578,62,2792,3354,1989,3405,1569,2228,2170,2149,1306,884,889,2392,3738,1147,791,3867,4046,49,3032,3806,3368,4290,2067,94,1623,2950,1658,1835,2689,1938,629,1445,896,255,624,1508,51,1278,900,254,4071,862,3624,2468,3137,3690,3487,4292,941,2471,3659,2508,2303,2513,1561,1562,871,1010,554,1022,3432,4382,1188,1806,3953,1954,4104,19,2724,3839,3749,93,1861,3775,3650,3640,2611,2906,605,2845,1897,2804,2184,3946,2436,2058,968,1543,1332,1663,4048,1024,26,117,471,1273,3795,696,4172,4320,3314,449,3275,3591,3277,3134,3676,1364,1718,3057,2725,3246,3816,3371,1569,2426,2118,2721,1673,3621,1457,2444,2399,2364,2496,2741,1465,1487,436,1465,2383,2215,3778,785,597,698,327,1233,4260,4270,202,457,577,1181,3505,364,63,245,225,191,3156,434,3760,4299,3674,4011,2606,3711,3319,3609,3283,4462,3687,3806,2693,3064,2826,154,2010,3110,3191,3758,3632,4292,2444,3138,2140,3348,1858,3831,2438,2367,3168,2933,2749,4019,2292,2895,2131,2752,2217,2656,1606,2645,2175,3015,1520,3204,1970,1744,1776,2650,1921,4503,1880,1937,1760,2785,1803,1355,416,1920,1294,1548,1557,2569,973,3083,2432,3112,1502,2971,1050,1319,2197,856,2557,4053,4525,3183,1908,2915,2638,2203,1162,2446,1924,3945,1338,3064,2041,2874,2712,2581,2244,3442,2539,2589,2279,2669,2146,3609,1626,3350,2469,2625,2143,3895,2448,3163,2011,2997,2849,4487,2330,2728,3142,2977,3665,4256,2465,3838,2914,4461,3435,4116,1792,197,3590,4549,4243,567,3787,3932,3184,4386,180,1526,1786,1090,245,818,1178,884,3144,728,4091,677,4581,1832,359,1863,1044,1581,1405,2629,1031,1418,1987,1135,1561,2771,916,2319,1353,2438,1563,3414,1259,2831,1804,3032,2719,333,2761,2519,3868,3436,144,4223,1034,4124,3340,4388,44,1137,3503,1091,4075,646,207,1172,93,488,99,2003,1354,1876,4393,1069,1595,1961,2159,3238,1300,2984,2159,2737,2766,4624,1394,3286,3895,4528,3371,886,3215,3412,3977,335,4501,1205,2767,1331,664,1263,2035,2250,656,1625,1048,2255,1689,3440,1434,3102,3103,3131,3195,4114,1790,2874,3032,4176,3533,4706,3559,338,387,403,282,1874,456,991,453,1553,1375,4400,382,2266,2398,3045,3296,3311,2194,3652,3150,3991,3659,940,2998,1226,143,321,49,1594,1129,674,1748,1702,2164,2510,97,4079,2516,2562,3878,3376,2672,2967,4528,209,4473,1654,3762,51,729,1405,282,1068,413,1116,2218,2058,2042,2572,2483,4022,3495,3892,4663,1383,3523,4332,4246,542,483,2985,4166,1199,2875,2643,2786,3481,2313,3942,1062,3066,2597,333,3029,57,510,2078,810,1818,795,1142,353,2183,2621,3463,4672,2725,2648,3722,3915,199,3633,133,458,566,900,3013,920,1087,1085,2555,2990,3416,1570,3751,2494,4312,4607,1977,3911,1809,200,640,1231,2794,1527,1123,1988,2961,3272,4836,1421,33,3710,1205,1258,639,4147,1734,1347,2620,2497,4449,2519,4180,2921,4713,4871,1190,1420,462,822,1474,1569,2781,1012,2658,2043,2832,4511,4871,3378,3941,31,416,501,2912,769,1045,2162,3704,3558,3095,2971,4284,3292,4843,4483,1922,4381,2068,2575,3265,2536,3763,2632,3185,4375,770,4562,2405,3129,1049,1227,2996,2771,3151,2729,3951,3702,4562,4364,1468,4423,1111,1833,2433,2404,4365,2785,3569,3431,4820,4766,632,3885,2675,1009,2010,2261,4033,2816,3165,3747,3587,3737,2101,4452,1477,1858,3158,2898,3270,1863,3820,3496,3489,986,1809,308,1158,1893,3378,2392,3700,2532,2865,4966,4357,4816,2384,260,1850,1288,2891,4642,2998,3258,3804,4212,529,4696,3575,1443,1939,4077,3739,3503,1233,4964,3977,68};
int main(){
int T,x;
for(scanf("%d",&T);T--;){
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
int n,m,W,S,T,p,x,y,k,i,j,P,Q,fl,wl,tot,sum,ans,h,t,fir[N],va[M],la[M],ne[M],co[M],q[N],d[N],fa[N],pre[N];bool v[N];
void ins(int x,int y,int fl,int z){
la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;co[tot]=z;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];va[tot]=0;co[tot]=-z;fir[y]=tot;
}
bool spfa(){
for(i=1;i<=T;i++)d[i]=1e9;
for(memset(v,0,sizeof(v)),d[S]=h=0,v[q[t=1]=S]=1;h^t;)
for(i=fir[x=q[h=h%T+1]],v[x]=0;i;i=ne[i])
if(d[x]+co[i]<d[y=la[i]]&&va[i]){
d[y]=d[fa[y]=x]+co[pre[y]=i];
if(!v[y])v[q[t=t%T+1]=y]=1;
}
return d[T]<1e9;
}
void end(){
for(sum=1e9,i=T;i!=S;i=fa[i])sum=min(sum,va[pre[i]]);fl+=sum;
for(i=T;i!=S;i=fa[i])va[p=pre[i]]-=sum,va[p^1]+=sum,ans+=sum*co[p];
}
int main(){
scanf("%d",&W);
for(;W--;){
ans=0;fl=0;wl=0;CL(fir);
scanf("%d%d",&n,&k);
S=n*2+1;T=S+1;tot=1;
ins(S,n+1,k,0);
for(i=1;i<=n;i++){
scanf("%d",&x);
wl+=x;
ins(S,i,x,0);
ins(i+n,T,x,0);
if(i<n)ins(i,i+1,40000,0),ins(i+n,i+n+1,40000,0);
}
scanf("%d%d%d",&m,&P,&Q);
if(P<=n)ins(S,P+n,40000,Q);
for(i=1;i<=m;i++){
scanf("%d%d",&y,&x);
for(j=1;j<=n;j++)if(j+x<=n)ins(j,j+n+x,200,y);
}
for(;spfa();end());
if(fl<wl)puts("No solution");else printf("%d\n",ans);
//fr(i,n)scanf("%d",&a[i]);
}
}
int T,n,m,x,y,i,j,tot,a[N];int sz[12];bool v[12],ff;
int main(){
scanf("%d",&T);
for(;T--;){
scanf("%d",&n);
CL(sz);ff=1;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>9||a[i]==0)ff=0;else{
sz[a[i]]++;
if(sz[a[i]]>1)ff=0;
}
}
for(i=1;i<=9;i++)v[i]=1;
if(n<4)ff=0;
if(ff)for(i=1;i<n;i++){
v[a[i]]=0;
if(a[i]==1&&a[i+1]==3||a[i]==3&&a[i+1]==1){
if(v[2])ff=0;
}
if(a[i]==4&&a[i+1]==6||a[i]==6&&a[i+1]==4){
if(v[5])ff=0;
}
if(a[i]==7&&a[i+1]==9||a[i]==9&&a[i+1]==7){
if(v[8])ff=0;
}
if(a[i]==1&&a[i+1]==7||a[i]==7&&a[i+1]==1){
if(v[4])ff=0;
}
if(a[i]==2&&a[i+1]==8||a[i]==8&&a[i+1]==2){
if(v[5])ff=0;
}
if(a[i]==3&&a[i+1]==9||a[i]==9&&a[i+1]==3){
if(v[6])ff=0;
}
if(a[i]==1&&a[i+1]==9||a[i]==9&&a[i+1]==1||a[i]==3&&a[i+1]==7||a[i]==7&&a[i+1]==3){
if(v[5])ff=0;
}
}
puts(ff?"valid":"invalid");
//fr(i,n)scanf("%d",&a[i]);
}
}
BestCoder Round #76 (div.1)
开场看T1，似乎是傻逼题。1min后发现题意读错，发现还是傻逼题。手速慢了点没抢到1血
然后看T2，觉得是鏼爷的题就有点弃疗，去颓了会儿。。觉得可能是上次TC的原题啊，就去找题，找了10多分钟没找到。。算了自己想。。TMD是傻逼题啊，把儿子乘起来就好了。。于是30min才A。。
然后看到T4有人A了，就去看，觉得太神了。。就颓了会。。
然后看了下T3，这数据范围好小啊，难道是O(1)gcd？可是那英文读物我看不懂啊。。于是想可以分块打表暴力啊。。
就写了一发，发现代码超长了。。然后改了一发交，竟然过不了编译。。
然后把表用int存，总算过了编译A了。。然后就颓颓颓。。
到了X人时间，直接去找B题不开栈的人，X了十多个人，然后自己也莫名其妙地被X了。。
最后终测，A了B题的人竟然比A了C题的人还少。。原来求逆不能直接求啊。。
D题其实也不是很难。。二分以后线段树直接搞就好了。。太傻了没想到
最后排名还是不错，涨了一笔上粉咯~
int T;
LL n,k,A,i,sg,gs,jd,w,o;
int main(){
for(scanf("%d",&T);T--;){
scanf("%I64d%I64d",&n,&k);
o=(k+1)*k/2;
if(n<o){puts("-1");continue;}
w=n-o;A=1;
jd=w/k;
gs=n-jd*k-o;sg=k-gs;
for(i=1;i<=sg;i++)A=(A*(i+jd))%M;
for(i=sg+1;i<=k;i++)A=(A*(i+jd+1))%M;
printf("%I64d\n",A);
//fr(i,n)gi(a[i]);
}
}
int T,n,m,x,y,i,j,tot,cnt,a[N],fir[N],la[N],ne[N];LL f[N],A;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
f[x]=1;
for(int i=fir[x],y;i;i=ne[i]){
dfs(y=la[i]);
f[x]=(f[x]*(f[y]+1))%M;
}
}
void dfs2(int x){
for(int i=fir[x],y;i;i=ne[i]){
y=la[i];
f[y]=f[y]*(f[x]%M*pow(f[y]+1,M-2,M)%M+1)%M;
dfs2(y);
}
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);tot=0;CL(fir);
for(i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
dfs(1);dfs2(1);A=0;
for(i=1;i<=n;i++)A=(A+f[i])%M;
printf("%I64d\n",A);
//fr(i,n)gi(a[i]);
}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;typedef long long LL;
int T,n,m,x,y,i,j,A,B;LL ans;
int V1[]={3275884,8495860,16311378,27345852,38444692,56562144,74636782,97188816,121066098,145274178,175925516,205461368,244528662,281025620,320161028,363094294,400651536,458403036,506880548,560990190,617838162,669815456,733458074,796858362,870647680,935743426,6389075,83026861,143575893,244796021,324141729,406816711,498315891,575798809,678692479,773466063,878383355,977931833,74211744,184620242,284304814,412981986,524094528,639044444,759402158,862917026,12107059,132189917,268523899,403250929,8495860,19416016,28776204,50637676,70643060,97540466,124202696,163976336,204963040,231133244,289753268,339992276,390954008,449676876,515984568,585756190,624022788,730212174,813251386,876882592,975726188,62064749,157899447,240012313,367846257,477159199,555769465,697702023,796566971,934821225,56879062,193888660,343130352,422805372,613038228,771151278,898009066,64598107,223351881,392904213,511170405,737191215,922900759,52369626,269707318,437738418,646132918,819888232,47097955,268299079,16311378,28776204,38701008,73088426,100616286,127906842,163969520,223409230,266260288,292814398,380348602,442692612,494081956,576190900,670357456,740759280,779370314,937284174,30469297,94496905,236891991,352043671,448233023,550015889,735304805,850764069,929800299,136141698,263929694,402566748,567553126,762983374,915050856,995112388,273553535,457680221,584915147,819936389,34979190,204912094,342193494,670555340,870542794,446955,313325245,531491141,740275789,967339471,291674656,518934114,27345852,50637676,73088426,115428788,143321358,171058720,217580022,301809386,369497352,422013488,520558134,583359434,635227484,743917434,875492652,982913844,59621761,229710737,323286167,387729685,576131583,740213221,884769743,40979826,233963098,349864716,429360830,702804968,889278358,102428339,324451001,522309395,674775231,755246535,125341180,393541080,602771376,893553104,108996055,279344217,435962261,875052771,170085878,395431344,755995336,974555116,183743085,466265459,904828543,240489610,38444692,70643060,100616286,143321358,171941516,200078952,258200202,359448870,449559028,512332126,611342156,674561896,726942548,862128490,12352325,159183995,245526661,416033089,509976211,574818861,808319877,988717633,191127248,355027006,548432016,664737984,744730374,83776927,282543279,575409619,799651527,997905829,150764316,231618226,688071686,2106215,271441457,562611447,778504429,949303355,125827970,654675450,17411541,291018739,651978807,870920831,80553672,420015736,928864670,360315487,56562144,97540466,127906842,171058720,200078952,229042064,299556932,434231734,536297334,599495612,698993426,762673796,815467742,978839208,178374239,335427713,422136937,593083967,687422525,752732361,35141786,277868360,486676088,651012098,844844224,961751954,42253123,453511725,724617629,20519424,245146716,443817878,597042606,678291404,236961321,625868879,895573679,187170310,403506638,574783146,771664668,430581905,850345137,124341402,485710442,705079836,915211658,311943279,957736145,432379952,74636782,124202696,163969520,217580022,258200202,299556932,391311872,538509044,641015986,704704226,804694980,869000994,922254802,116332909,348359353,526814547,637131529,832369525,951397853,42762688,375510544,625610716,834833616,999628876,193979883,311370899,392336115,883266457,189950346,522703758,784289252,19440105,212182901,333435207,963913563,353192684,623331246,915353212,132154703,303857695,521458055,289605276,758947218,82303139,492375243,764734877,27499086,508919724,200515343,675557581,97188816,163976336,223409230,301809386,359448870,434231734,538509044,686725336,789592878,853680194,954157242,18926497,72618471,297274017,571928711,801919503,944378041,208139712,376279152,522992640,863323774,114006155,323634211,488986415,683791013,801638031,883068827,451948272,803451026,242875501,576151641,887164667,169524548,350132428,981158496,370920411,641533657,933993763,151348580,323493874,562146848,455225269,19168928,441568118,967094796,312069511,721043089,244021194,936141440,411623067,121066098,204963040,266260288,369497352,449559028,536297334,641015986,789592878,893536380,958011318,58902701,124162317,178343147,435954505,755025049,13608736,156405264,487575468,703056994,856392254,197184521,448350041,658345169,824217607,19484778,137912464,219986726,867309702,278735719,747809495,132954778,518194160,857993074,38978805,670479607,60618250,331670658,624517078,842372504,14950217,275298203,286700624,935382044,363751205,998764175,435093138,888975812,412351339,104914186,580867054,145274178,231133244,292814398,422013488,512332126,599495612,704704226,853680194,958011318,23686501,124989855,190776585,245495589,537963827,885999725,144944692,288131978,685145706,907672250,61434963,402639037,654350541,864810391,31094058,226842694,345879396,428570910,154133097,587780505,57213684,496196906,937114996,277296541,458706933,90653766,481216516,752642404,45873165,264215529,437256631,719710885,839322924,495169055,923928393,666932468,141499391,595788493,119583192,812631094,289085743,175925516,289753268,380348602,520558134,611342156,698993426,804694980,954157242,58902701,124989855,227618069,293842521,349032219,676508867,80868330,395486628,595353512,999812102,222779041,376966707,718706907,970934119,181827420,348550422,544721752,664175932,747358610,550790197,63794342,637815240,136902511,578227151,918815761,100655524,733061808,124035617,395856947,689494567,908341751,81895908,386815880,638153081,415673544,965117588,745196191,220249794,674963912,199240031,892799699,369717086,205461368,339992276,442692612,583359434,674561896,762673796,869000994,18926497,124162317,190776585,293842521,361446625,417150649,782170281,219781406,588294982,795237054,200126161,423503297,578186051,920387049,173030084,384402590,551679976,748238196,868144512,951816164,843683035,383398878,41566473,541032003,982819123,323859574,506164766,139005203,530638409,802902317,97143136,316650988,490710816,818452794,184400688,48575041,641680811,422228420,897791012,352970655,877697229,571748802,49114155,244528662,390954008,494081956,635227484,726942548,815467742,922254802,72618471,178343147,245495589,349032219,417150649,474349225,878086819,376602186,751979542,959351896,364676229,588623009,743812641,86483108,339623292,551773092,719689922,916713274,37090597,121197763,103881756,712737778,371275341,871182335,313402716,654903784,837643408,470900041,862981875,135662674,430357548,650350066,824860260,175920809,689527752,597063907,190585690,971546474,447560667,903180995,428388216,122941493,600812727,281025620,449676876,576190900,743917434,862128490,978839208,116332909,297274017,435954505,537963827,676508867,782170281,878086819,328923418,834791446,210585105,418384675,824239093,48598800,204266644,547474574,801119000,13881203,182226477,379725689,500573279,585109763,659640088,325886091,52828740,616672172,121182643,535052619,785750285,487537864,954810722,299387577,668338371,966947295,217400630,654498006,213661566,121577983,715502563,496900724,973333554,429385321,955090203,650243006,128567681,320161028,515984568,670357456,875492652,12352325,178374239,348359353,571928711,755025049,885999725,80868330,219781406,376602186,834791446,342324971,718500915,926671019,332982638,557751498,713802698,57469731,311758957,525021075,693775379,891712939,13021912,98001988,264392329,966611919,811750634,450708391,31311204,541748418,840424726,660479609,205034850,649899616,117201581,481842683,852733023,333231816,893089971,801722930,396416863,178410958,655219774,111662327,637782021,333389498,812277730,363094294,585756190,740759280,982913844,159183995,335427713,526814547,801919503,13608736,144944692,395486628,588294982,751979542,210585105,718500915,96399872,304949822,711637182,936819422,93318129,437398323,692266409,905912967,75298500,273695050,395471410,480962204,736665773,521879444,385534161,85502640,761490544,321157809,620200523,557300586,199075945,650158085,206669340,681692136,88356271,569250981,129747543,38804458,634108022,416505063,893675289,351077472,877890214,574038319,53366218,400651536,624022788,779370314,59621761,245526661,422136937,637131529,944378041,156405264,288131978,595353512,795237054,959351896,418384675,926671019,304949822,515322548,922370516,147978337,304941951,649448681,904716243,119043940,288888480,487715724,610023030,696096190,41395276,840764472,704838499,466416230,192505315,752531209,51962218,100786229,750488325,201960082,847298046,361178351,768244371,249575946,810721877,720639580,316387279,99209338,576801662,35122907,562467255,259144128,739042254,458403036,730212174,937284174,229710737,416033089,593083967,832369525,208139712,487575468,685145706,999812102,200126161,364676229,824239093,332982638,711637182,922370516,331356709,557357635,714740635,59694304,315391616,530176238,700438302,899707242,22582189,109335055,560092558,458820893,475165208,297180627,23692834,584137562,884020328,75679724,866804130,467119739,158322526,672704800,80225053,562012541,123557497,33909210,630069642,413305761,891310369,350079780,877899044,575087939,55501210,506880548,813251386,30469297,323286167,509976211,687422525,951397853,376279152,703056994,907672250,222779041,423503297,588623009,48598800,557751498,936819422,147978337,557357635,785345353,943122421,288482012,544666892,759903326,930744726,130431533,253753157,341156101,897151120,848981679,933704244,756105235,483022242,43906889,344243091,666945138,545451191,186877988,878526796,393399099,801404895,283615888,845539021,756453352,353102823,136754380,615290884,74522865,602803037,300497834,781369474,560990190,876882592,94496905,387729685,574818861,752732361,42762688,522992640,856392254,61434963,376966707,578186051,743812641,204266644,713802698,93318129,304941951,714740635,943122421,103008202,448757512,705384468,921150810,92541365,292929219,416880759,504756627,162288087,166766248,251876555,74683910,802056632,363396693,664145175,117405221,41677012,683520434,375577819,890894687,299337290,782040460,344363312,255909873,853243073,637621084,116624871,576370061,105155318,803305192,284779717,617838162,975726188,236891991,576131583,808319877,35141786,375510544,863323774,197184521,402639037,718706907,920387049,86483108,547474574,57469731,437398323,649448681,59694304,288482012,448757512,796696082,53779883,270034157,441915349,642855415,767383327,855757383,618449723,707118980,896452757,816262316,638600213,303529040,701366600,197580654,122300401,764528113,457098684,972862212,381788733,864970413,427830871,339805882,937960602,722814667,202263200,662512786,191740069,890346183,372328512,669815456,62064749,352043671,740213221,988717633,277868360,625610716,114006155,448350041,654350541,970934119,173030084,339623292,801119000,311758957,692266409,904716243,315391616,544666892,705384468,53779883,313143747,529809097,702084183,903402881,28346668,117295732,982494153,95304199,409542914,405262573,292736524,61968347,495237631,991943272,917102243,559823036,252922465,769164197,178537470,662372040,225728736,138220845,736934987,522363918,2373295,463081817,992807283,691810504,174227761,733458074,157899447,448233023,884769743,191127248,486676088,834833616,323634211,658345169,864810391,181827420,384402590,551773092,13881203,525021075,905912967,119043940,530176238,759903326,921150810,270034157,529809097,748848363,921524033,123389252,248788568,338186444,303172744,521436923,843492038,906453357,912200876,723300819,156970624,654095297,579777130,222931699,916469405,433144722,842968388,327267087,891154828,804073023,403242880,189139189,669602285,130758870,661147004,360580763,843420195,796858362,240012313,550015889,40979826,355027006,651012098,999628876,488986415,824217607,31094058,348550422,551679976,719689922,182226477,693775379,75298500,288888480,700438302,930744726,92541365,441915349,702084183,921524033,96639168,298991790,424945786,514833352,602238288,864704337,226802951,378816546,431578687,243086176,677194734,174869224,100964169,744519829,438567940,955907110,366195007,850976795,415374675,328897638,928456942,714908317,195903232,657731582,188572741,888416361,371735038,870647680,367846257,735304805,233963098,548432016,844844224,193979883,683791013,19484778,226842694,544721752,748238196,916713274,379725689,891712939,273695050,487715724,899707242,130431533,292929219,642855415,903402881,123389252,298991790,503870516,630215176,720610268,926937516,267310118,792280965,984645154,37925500,849892860,284452589,782616364,709207433,353270970,48005703,565947295,976839939,462131810,27030450,941069242,541097497,328451086,810437376,272862669,804432775,504747688,988579026,935743426,477159199,850764069,349864716,664737984,961751954,311370899,801638031,137912464,345879396,664175932,868144512,37090597,500573279,13021912,395471410,610023030,22582189,253753157,416880759,767383327,28346668,248788568,424945786,630215176,759278648,850104952,168219883,585398012,160379528,353169323,406934268,219387735,654362957,153041953,80064428,724650002,419936973,938334015,349706750,835451006,400877270,315363875,916031729,704172462,186735141,649605813,182080434,882903590,367195833,6389075,555769465,929800299,429360830,744730374,42253123,392336115,883068827,219986726,428570910,747358610,951816164,121197763,585109763,98001988,480962204,696096190,109335055,341156101,504756627,855757383,117295732,338186444,514833352,720610268,850104952,943718964,381737547,841712538,417102346,610309383,664523620,477384371,912886865,412010705,339685382,984719756,680460707,199412556,611303358,97500077,663373776,578485575,179688368,968255764,451847449,915202379,448150248,149411647,634236695,83026861,697702023,136141698,702804968,83776927,453511725,883266457,451948272,867309702,154133097,550790197,843683035,103881756,659640088,264392329,736665773,41395276,560092558,897151120,162288087,618449723,982494153,303172744,602238288,926937516,168219883,381737547,856527741,316888609,892688742,86352158,140970081,954260617,390185666,889898363,818018432,463468255,159649444,679118448,91421805,578076639,144864845,60427234,662057724,451055259,935408339,399202578,932634340,634436045,119745052,143575893,796566971,263929694,889278358,282543279,724617629,189950346,803451026,278735719,587780505,63794342,383398878,712737778,325886091,966611919,521879444,840764472,458820893,848981679,166766248,707118980,95304199,521436923,864704337,267310118,585398012,841712538,316888609,780190356,356417450,550517497,605549718,419242007,855584571,355759297,284474662,930296202,626855763,146827994,559577082,46697273,614136988,530603589,132721538,922302040,407178549,871396327,405417952,107759823,593636679,244796021,934821225,402566748,102428339,575409619,20519424,522703758,242875501,747809495,57213684,637815240,41566473,371275341,52828740,811750634,385534161,704838499,475165208,933704244,251876555,896452757,409542914,843492038,226802951,792280965,160379528,417102346,892688742,356417450,935648883,130177669,185621412,999778098,436531317,937090974,866223391,512616194,209597087,729953487,143169474,630820384,198676976,115691139,718649565,508976350,994292216,458939067,993387993,696196704,182504845,324141729,56879062,567553126,324451001,799651527,245146716,784289252,576151641,132954778,496196906,136902511,541032003,871182335,616672172,450708391,85502640,466416230,297180627,756105235,74683910,816262316,405262573,906453357,378816546,984645154,353169323,610309383,86352158,550517497,130177669,327809498,383638305,198178280,635355744,136311442,65822647,712685509,410107084,930971844,344697773,832837439,401155943,318873284,922707756,713443029,199310284,664627360,199544463,902814553,389685082,406816711,193888660,762983374,522309395,997905829,443817878,19440105,887164667,518194160,937114996,578227151,982819123,313402716,121182643,31311204,761490544,192505315,23692834,483022242,802056632,638600213,292736524,912200876,431578687,37925500,406934268,664523620,140970081,605549718,185621412,383638305,442662160,257590789,695225243,196628241,126640518,773886318,471836905,993222949,407535736,896152078,465031866,383260161,987590473,778740048,264986229,731189217,266892340,970672288,458022433,498315891,343130352,915050856,674775231,150764316,597042606,212182901,169524548,857993074,277296541,918815761,323859574,654903784,535052619,541748418,321157809,752531209,584137562,43906889,363396693,303529040,61968347,723300819,243086176,849892860,219387735,477384371,954260617,419242007,999778098,198178280,257590789,75873290,513907674,15729630,946149812,593867395,292304210,814304208,229098875,718285745,287606317,206223188,811003258,602993129,89764996,556495612,92932863,797170109,284944044,575798809,422805372,995112388,755246535,231618226,678291404,333435207,350132428,38978805,458706933,100655524,506164766,837643408,785750285,840424726,620200523,51962218,884020328,344243091,664145175,701366600,495237631,156970624,677194734,284452589,654362957,912886865,390185666,855584571,436531317,635355744,695225243,513907674,955303334,457506102,388420899,36645612,735603866,258062617,673461091,163176556,732961187,652116110,257317891,49915138,537738742,4996107,541828569,246508568,734784848,678692479,613038228,273553535,125341180,688071686,236961321,963913563,981158496,670479607,90653766,733061808,139005203,470900041,487537864,660479609,557300586,100786229,75679724,666945138,117405221,197580654,991943272,654095297,174869224,782616364,153041953,412010705,889898363,355759297,937090974,136311442,196628241,15729630,457506102,963182197,894496688,543175227,242539468,765449600,181293241,671493387,241864589,161469452,767133638,560217477,48606914,516297070,53564231,758739395,247492352,773466063,771151278,457680221,393541080,2106215,625868879,353192684,370920411,60618250,481216516,124035617,530638409,862981875,954810722,205034850,199075945,750488325,866804130,545451191,41677012,122300401,917102243,579777130,100964169,709207433,80064428,339685382,818018432,284474662,866223391,65822647,126640518,946149812,388420899,894496688,829373035,478440002,178234635,701625785,117955094,608600024,179455206,99677781,705818269,499358984,988295282,456418949,994189951,699839904,189003755,878383355,898009066,584915147,602771376,271441457,895573679,623331246,641533657,331670658,752642404,395856947,802902317,135662674,299387577,649899616,650158085,201960082,467119739,186877988,683520434,764528113,559823036,222931699,744519829,353270970,724650002,984719756,463468255,930296202,512616194,712685509,773886318,593867395,36645612,543175227,478440002,131134113,831306131,355161602,771989188,263172053,834496924,755162373,361933532,155973787,645356333,113942790,652225820,358267507,847870849,977931833,64598107,819936389,893553104,562611447,187170310,915353212,933993763,624517078,45873165,689494567,97143136,430357548,668338371,117201581,206669340,847298046,158322526,878526796,375577819,457098684,252922465,916469405,438567940,48005703,419936973,680460707,159649444,626855763,209597087,410107084,471836905,292304210,735603866,242539468,178234635,831306131,535238994,59494193,476799691,968501121,540277055,461491956,68737987,863270923,353144420,822230788,361316257,67989192,558025564,74211744,223351881,34979190,108996055,778504429,403506638,132154703,151348580,842372504,264215529,908341751,316650988,650350066,966947295,481842683,681692136,361178351,672704800,393399099,890894687,972862212,769164197,433144722,955907110,565947295,938334015,199412556,679118448,146827994,729953487,930971844,993222949,814304208,258062617,765449600,701625785,355161602,59494193,587593851,5365552,497546690,69806404,991530848,599222265,394262498,884710646,354413505,894001003,601632788,92563361,184620242,392904213,204912094,279344217,949303355,574783146,303857695,323493874,14950217,437256631,81895908,490710816,824860260,217400630,852733023,88356271,768244371,80225053,801404895,299337290,381788733,178537470,842968388,366195007,976839939,349706750,611303358,91421805,559577082,143169474,344697773,407535736,229098875,673461091,181293241,117955094,771989188,476799691,5365552,427081908,919663856,492381514,414538529,22712104,818207274,309315509,779545937,319745012,28054033,519467569,284304814,511170405,342193494,435962261,125827970,771664668,521458055,562146848,275298203,719710885,386815880,818452794,175920809,654498006,333231816,569250981,249575946,562012541,283615888,782040460,864970413,662372040,327267087,850976795,462131810,835451006,97500077,578076639,46697273,630820384,832837439,896152078,718285745,163176556,671493387,608600024,263172053,968501121,497546690,919663856,416252069,989387052,912050637,520754894,316883515,808472051,279372808,820097788,528877711,21246418,412981986,737191215,670555340,875052771,654675450,430581905,289605276,455225269,286700624,839322924,638153081,184400688,689527752,213661566,893089971,129747543,810721877,123557497,845539021,344363312,427830871,225728736,891154828,415374675,27030450,400877270,663373776,144864845,614136988,198676976,401155943,465031866,287606317,732961187,241864589,179455206,834496924,540277055,69806404,492381514,989387052,566595916,489636897,98756762,895385816,387361641,858759739,399904380,109100339,601908397,524094528,922900759,870542794,170085878,17411541,850345137,758947218,19168928,935382044,495169055,415673544,48575041,597063907,121577983,801722930,38804458,720639580,33909210,756453352,255909873,339805882,138220845,804073023,328897638,941069242,315363875,578485575,60427234,530603589,115691139,318873284,383260161,206223188,652116110,161469452,99677781,755162373,461491956,991530848,414538529,912050637,489636897,416839910,26428797,823511259,315913508,787734738,329326365,38956276,532192454,639044444,52369626,446955,395431344,291018739,124341402,82303139,441568118,363751205,923928393,965117588,641680811,190585690,715502563,396416863,634108022,316387279,630069642,353102823,853243073,937960602,736934987,403242880,928456942,541097497,916031729,179688368,662057724,132721538,718649565,922707756,987590473,811003258,257317891,767133638,705818269,361933532,68737987,599222265,22712104,520754894,98756762,26428797,640369243,437895548,930742302,403058953,945087335,655143958,148826459,759402158,269707318,313325245,755995336,651978807,485710442,492375243,967094796,998764175,666932468,745196191,422228420,971546474,496900724,178410958,416505063,99209338,413305761,136754380,637621084,722814667,522363918,189139189,714908317,328451086,704172462,968255764,451055259,922302040,508976350,713443029,778740048,602993129,49915138,560217477,499358984,155973787,863270923,394262498,818207274,316883515,895385816,823511259,437895548,239780153,733034153,205801586,748325194,458946359,953064149,862917026,437738418,531491141,974555116,870920831,705079836,764734877,312069511,435093138,141499391,220249794,897791012,447560667,973333554,655219774,893675289,576801662,891310369,615290884,116624871,202263200,2373295,669602285,195903232,810437376,186735141,451847449,935408339,407178549,994292216,199310284,264986229,89764996,537738742,48606914,988295282,645356333,353144420,884710646,309315509,808472051,387361641,315913508,930742302,733034153,230714434,703918832,246854531,958126983,452857780,12107059,646132918,740275789,183743085,80553672,915211658,27499086,721043089,888975812,595788493,674963912,352970655,903180995,429385321,111662327,351077472,35122907,350079780,74522865,576370061,662512786,463081817,130758870,657731582,272862669,649605813,915202379,399202578,871396327,458939067,664627360,731189217,556495612,4996107,516297070,456418949,113942790,822230788,354413505,779545937,279372808,858759739,787734738,403058953,205801586,703918832,181729655,725044681,436746458,932136570,132189917,819888232,967339471,466265459,420015736,311943279,508919724,244021194,412351339,119583192,199240031,877697229,428388216,955090203,637782021,877890214,562467255,877899044,602803037,105155318,191740069,992807283,661147004,188572741,804432775,182080434,448150248,932634340,405417952,993387993,199544463,266892340,92932863,541828569,53564231,994189951,652225820,361316257,894001003,319745012,820097788,399904380,329326365,945087335,748325194,246854531,725044681,273035784,985195366,481064973,268523899,47097955,291674656,904828543,928864670,957736145,200515343,936141440,104914186,812631094,892799699,571748802,122941493,650243006,333389498,574038319,259144128,575087939,300497834,803305192,890346183,691810504,360580763,888416361,504747688,882903590,149411647,634436045,107759823,696196704,902814553,970672288,797170109,246508568,758739395,699839904,358267507,67989192,601632788,28054033,528877711,109100339,38956276,655143958,458946359,958126983,436746458,985195366,702071941,198335866,403250929,268299079,518934114,240489610,360315487,432379952,675557581,411623067,580867054,289085743,369717086,49114155,600812727,128567681,812277730,53366218,739042254,55501210,781369474,284779717,372328512,174227761,843420195,371735038,988579026,367195833,634236695,119745052,593636679,182504845,389685082,458022433,284944044,734784848,247492352,189003755,847870849,558025564,92563361,519467569,21246418,601908397,532192454,148826459,953064149,452857780,932136570,481064973,198335866,699448126};
int V2[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,8,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4,4,4,4,4,5,5,5,6,6,6,6,7,7,8,8,8,8,9,9,10,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,8,8,9,9,9,10,10,11,11,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,3,3,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,10,10,10,11,11,12,12,13,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,6,6,6,7,7,8,8,8,8,9,9,10,10,11,11,12,12,13,14,14,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,9,9,10,11,11,12,13,13,14,14,15,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,5,6,6,7,7,7,8,8,9,9,9,9,10,10,11,12,12,13,14,14,15,15,16,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,4,5,6,7,7,7,8,8,9,9,9,10,10,10,10,12,13,13,14,14,15,15,16,17,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,4,4,5,5,6,6,7,7,8,8,8,9,9,10,10,10,10,11,12,13,14,14,15,15,16,17,17,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,7,8,8,9,9,9,10,10,11,11,11,12,12,14,15,15,16,16,17,17,18,19,0,0,0,0,1,1,1,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5,5,5,6,6,7,7,8,9,10,10,10,11,12,12,13,13,13,14,15,16,17,18,18,19,19,20,20,0,0,0,0,1,1,1,1,2,2,2,2,2,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,8,9,10,10,11,11,12,13,13,14,14,15,15,17,18,18,19,19,20,20,21,22,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,8,8,9,10,11,11,12,13,13,14,14,15,15,16,17,18,19,20,20,21,21,22,22,0,0,0,1,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,6,7,7,8,9,10,11,12,12,12,14,14,15,16,16,17,17,19,20,20,21,21,22,22,23,24,0,0,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,9,10,11,12,13,13,14,15,16,16,17,17,18,19,20,21,22,22,23,23,24,24,0,0,1,1,1,1,2,2,2,3,3,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,9,10,11,12,12,13,13,15,16,16,17,17,18,18,20,21,21,22,23,23,24,24,25,0,0,1,1,1,2,2,2,3,3,3,3,4,4,5,5,5,6,6,6,6,7,7,7,7,7,7,9,10,11,12,13,14,14,16,17,17,18,18,19,19,21,22,22,23,24,24,25,25,26,0,1,1,1,1,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,7,8,8,9,11,12,13,14,15,15,16,17,18,19,19,20,20,22,23,23,24,25,25,25,26,27,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,10,11,12,13,14,15,16,17,18,19,19,20,20,21,22,23,24,25,25,26,26,27,27,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,7,7,8,8,8,8,10,11,13,14,15,16,16,18,19,19,20,20,21,21,23,24,24,25,26,26,27,27,28,0,1,1,2,2,2,3,3,4,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,10,12,13,14,16,16,17,18,19,20,21,21,21,22,24,24,25,26,26,27,27,28,28,0,1,1,2,2,2,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,8,11,12,14,15,16,17,17,19,20,20,21,21,22,22,24,25,25,26,27,27,28,28,29,1,1,1,2,2,3,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,8,11,12,14,15,16,17,17,19,20,20,21,22,22,23,24,25,26,26,27,27,28,29,29,1,1,2,2,3,3,3,4,4,5,5,5,6,6,7,7,8,8,8,9,9,9,10,10,10,11,11,13,15,16,18,19,19,20,21,22,23,24,24,25,25,27,28,28,29,29,30,30,31,32,1,1,2,2,3,3,4,4,5,5,6,6,6,7,7,8,8,9,9,10,10,11,11,11,12,12,12,15,16,18,19,20,21,21,23,24,24,25,26,26,27,28,29,30,30,31,31,32,33,33,1,1,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,16,18,19,21,22,22,23,24,25,26,27,27,28,28,30,31,31,32,32,33,33,34,35,1,2,2,3,3,4,4,5,6,6,7,7,7,8,9,10,10,11,11,12,12,13,13,14,14,15,15,18,19,21,22,23,24,24,26,27,27,28,28,29,29,31,32,32,33,34,34,35,35,36,1,2,2,3,3,4,5,5,6,6,7,7,8,9,10,10,11,12,12,12,13,14,14,15,16,16,16,19,20,22,23,24,25,25,27,28,28,29,29,30,30,32,33,33,34,35,35,36,36,37,1,2,2,3,4,4,5,6,6,7,7,8,8,9,10,11,11,12,13,13,14,15,15,16,16,17,17,19,21,22,24,25,26,26,28,28,29,30,30,31,31,33,34,34,35,36,36,37,37,38,1,2,2,3,4,4,5,6,7,7,8,8,8,9,10,11,12,12,13,13,14,15,16,16,17,17,17,20,21,23,24,25,26,26,28,29,30,30,31,31,32,33,34,35,36,36,37,37,38,38,1,2,3,4,4,5,5,6,7,8,8,9,9,10,11,12,13,14,14,15,16,16,17,18,18,19,19,21,23,24,26,27,28,28,29,30,31,32,32,33,33,35,36,36,37,38,38,39,39,40,1,2,3,4,5,5,6,7,8,8,9,9,9,10,12,13,13,14,15,16,17,17,18,19,19,20,20,22,24,25,27,28,28,29,30,31,32,33,33,34,34,36,37,37,38,38,39,39,40,41,1,2,3,4,5,5,6,7,8,8,9,9,10,11,12,13,14,15,16,16,17,18,19,19,20,20,20,23,24,26,27,28,29,30,31,32,33,33,34,34,35,36,37,38,39,39,40,40,41,41,1,3,3,4,5,6,6,7,8,9,9,10,10,11,13,14,14,16,16,17,18,19,19,20,21,21,21,24,25,27,28,29,30,30,32,33,33,34,35,35,35,37,38,39,39,40,40,41,42,42,2,3,4,5,5,6,7,8,8,9,9,10,10,11,13,14,15,16,17,17,18,19,20,20,21,21,22,24,26,27,28,29,30,31,32,33,34,35,35,36,36,38,38,39,40,40,41,41,42,43,2,3,4,5,5,6,7,8,9,9,10,10,10,12,13,15,15,17,17,18,19,20,20,21,21,22,22,25,26,28,29,30,31,31,33,34,34,35,36,36,36,38,39,40,40,41,41,42,43,43,2,3,4,5,6,6,7,8,9,9,10,10,11,12,14,15,16,17,18,18,19,20,21,21,22,22,23,25,27,28,29,30,31,32,33,34,35,35,36,36,37,38,39,40,41,41,42,42,43,44,2,3,4,5,6,7,8,9,10,10,11,12,12,14,15,17,17,19,19,20,21,22,22,23,24,24,24,27,28,30,31,32,33,33,35,36,36,37,38,38,38,40,41,42,42,43,43,44,45,45,2,3,4,6,7,7,8,10,10,11,12,13,13,15,16,18,18,20,20,21,22,23,23,24,24,25,25,28,29,31,32,33,34,34,36,37,37,38,38,39,39,41,42,43,43,44,44,45,46,46,2,4,5,6,7,8,9,10,11,11,12,13,14,15,17,18,19,20,21,21,22,23,24,24,25,25,26,28,30,31,32,33,34,35,36,37,38,39,39,40,40,42,43,43,44,44,45,45,46,47,2,4,5,6,7,8,9,10,11,12,13,14,14,16,18,19,20,21,22,22,23,24,25,25,26,26,26,29,30,32,33,34,35,36,37,38,39,39,40,40,41,42,43,44,45,45,46,46,47,47,2,4,5,6,7,8,9,11,12,13,14,14,15,16,18,19,20,21,22,23,24,25,25,26,26,27,27,29,31,32,34,35,36,36,38,38,39,40,40,41,41,43,44,44,45,46,46,47,47,48,3,4,5,7,8,8,10,11,12,13,14,15,15,17,19,20,21,22,23,23,24,25,26,26,27,27,27,30,31,33,34,35,36,37,38,39,40,40,41,41,42,43,44,45,46,46,47,47,48,48,3,4,5,7,8,9,10,12,13,14,15,15,16,17,19,20,21,22,23,24,25,25,26,27,27,28,28,30,32,33,35,36,37,37,39,39,40,41,41,42,42,44,45,45,46,47,47,48,48,49,3,5,6,7,8,9,11,12,14,14,15,16,17,18,20,21,22,23,24,24,25,26,27,27,28,28,29,31,33,34,35,36,37,38,39,40,41,42,42,43,43,45,46,46,47,47,48,48,49,50,3,5,6,8,9,10,11,13,14,15,16,17,17,19,20,22,22,24,24,25,26,27,27,28,28,29,29,32,33,35,36,37,38,38,40,41,41,42,43,43,44,45,46,47,47,48,48,49,50,50};
int main(){
for(scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);ans=0;
if(n>=300&&m>=300)ans+=1ll*V2[((n/300)-1)*50+m/300-1]*1000000007+V1[((n/300)-1)*50+m/300-1];
A=(n/300)*300;B=(m/300)*300;
for(i=1;i<=n;i++)for(j=B+1;j<=m;j++)ans+=__gcd(i&j,i|j);
for(i=A+1;i<=n;i++)for(j=1;j<=m;j++)ans+=__gcd(i&j,i|j);
for(i=A+1;i<=n;i++)for(j=B+1;j<=m;j++)ans-=__gcd(i&j,i|j);
printf("%I64d\n",ans);
}
}
int T,n,m,x,y,i,j,tot,cnt,a[N],fir[N],la[N],ne[N];LL f[N],g[N],A;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
f[x]=1;g[x]=1;
for(int i=fir[x],y;i;i=ne[i]){
dfs(y=la[i]);
g[x]=((f[y]+1)*g[x]+f[x]*g[y])%M;
f[x]=(f[x]*(f[y]+1))%M;
}
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);tot=0;CL(fir);
for(i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
dfs(1);A=0;
for(i=1;i<=n;i++)A=(A+g[i])%M;
printf("%I64d\n",A);
}
}
BestCoder Round #77 (div.1)
辣鸡BC，辣鸡出题人，数据都弄错。。不弄错没准直接RK1了。。
开场看D，真TM傻逼，直接摞，TM竟然WA了，爆了好几发，TM还是WA
过了30MIN告诉我数据错了？逗我么。。到50min交了5发才让过。。
然后看A，TM能做？A这么难要人命啊。。
看C想了会，好傻逼啊，写了个马上交。。
然后做B，倒序并查集，代码量还挺大。。写了一会WA了。。
查了好久发现有0的情况，交了以后发现只有不到10MIN了。。
赶紧静下心来弄A。。马上搞出来了。。
这场真TM傻逼，真TM傻逼，真TM傻逼。。我原来可以拿RK1的啊曰曰曰。。
BestCoder Round #79 (div.1)
原来要准备会考的，手贱打了发。。
开场看C，傻逼莫比乌斯？写了发WA了。。发现不能暴力求，先预处理一下试试看，改了下又WA了。。然后找到2820的原题看一下，再改了一下就A了。。
然后看B，调和级数后单调队列就没了？爆了2发才A。。
A怎么这么难。。乱写了个贪心WA了两发。。快20分钟了都没写出来。。静下心来分多种情况考虑，总算A了。。
然后看D，感觉就是树分治模板题啊。。只有20分钟了我写残了曰。。
最后测完变成了RK2，打了20多场首次登上了领奖台。。
int T,n,m,x,y,i,j,tot,cnt,a[N];LL A,B,C,D,ans;
int main(){
for(scanf("%d",&T);T--;){
ans=0;
scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&D);if(B<D)swap(A,C),swap(B,D);
for(i=62;~i;i--){
if(B>>i&1)
if(C<(1ll<<i)){
A=max(A-(1ll<<i),0ll);B-=1ll<<i;
ans+=1ll<<i;D=min(D,(1ll<<i)-1);
continue;
//if(B<D)swap(A,C),swap(B,D);
}
swap(A,C);swap(B,D);
if(B>>i&1)
if(C<(1ll<<i)){
A=max(A-(1ll<<i),0ll);B-=1ll<<i;
ans+=1ll<<i;D=min(D,(1ll<<i)-1);
continue;
//if(B<D)swap(A,C),swap(B,D);
}else{
A-=(1ll<<i);B-=(1ll<<i);
C-=(1ll<<i);D-=(1ll<<i);
}
}
printf("%I64d\n",ans);
}
}
int T,n,m,o,x,y,e,k,t,i,j,tot,cnt,a[N],b[N],l[N],r[N],q[N];LL A,B,C,ans,s[N];
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);ans=0;e=0;
fr(i,n)gi(b[i]);
for(k=1;k<=n;k++){
if((e+1)*(e+1)<=k)e++;
for(o=0,i=k;i<=n;i+=k)a[++o]=b[i],s[o]=s[o-1]+a[o];
for(i=1;i<=o;i++)l[i]=r[i]=0;
for(q[t=0]=0,i=1;i<=o;q[++t]=i++){
for(;t&&a[i]<=a[q[t]];t--);
l[i]=q[t]+1;
}
for(q[t=0]=o+1,i=o;i;q[++t]=i--){
for(;t&&a[i]<=a[q[t]];t--);
r[i]=q[t]-1;
}
for(i=1;i<=o;i++)ans=max(ans,(s[r[i]]-s[l[i]-1])*a[i]*e);
}
printf("%I64d\n",ans);
}
}
int T,n,m,x,y,i,j,t,tot,cnt,a[N],p[N],u[N];LL A,B,C,ans,sum[N];bool f[N];
long long calc(int n,int m){
long long re=0;int la;
for(int i=1;i<=min(n,m);i=la+1){
la=min(n/(n/i),m/(m/i));
re+=1ll*(n/i)*(m/i)*(sum[la]-sum[i-1]);
}
return re;
}
int main(){
for(u[1]=1,i=2;i<N;i++){
if(!f[i])p[++t]=i,u[i]=-1;
for(j=1;j<=t&&i*p[j]<N;j++){
f[i*p[j]]=1;
if(i%p[j]==0)break;
u[i*p[j]]=-u[i];
}
}
for(j=1;j*j<N;j++)for(i=j*j;i<N;i+=j*j)sum[i]+=u[i/(j*j)];
for(i=1;i<N;i++)sum[i]+=sum[i-1];
for(scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);
printf("%I64d\n",1ll*n*m-calc(n,m));
}
}
BestCoder Round #80
听说是原题场，来水一水。
哇，D是原题啊，还完全没改。看我1分钟A，曰怎么CE了。。
看了5分钟发现是bits/stdc++.h，改了后变TLE了。。
爆了快10分钟无果，自己试了下，输出调试了会，20分钟后才A原题。。
然后秒A，然后B写了发快速乘也秒了。
C有点难哦，想了5分钟没想出来。静下心来想了想，发现可以矩乘一个幂。
写了发，调了一会，总算在1H的时候A了。
看E咯，感觉就是PA那题。。我码码码，调了好久，写了50多分钟总算过了pretest。估计没什么希望A的。。
叉人开始，直接开叉B。找到了SB直接叉，发现竟然要求质数，赶紧查了下大质数怎么生成，可是生成完B基本被叉光了。。只捡到一个。。
然后很多人叉A，发现他们全判了0，就我这个SB没判，这题意不明啊，太辣鸡了，马上就要被叉咯。。
看A没有和我一样的SB了，就去叉E，看到有个人没有判无解情况，叉掉了。
然后看到有个人n=1直接return了，不知道在干什么。。可是做了组数据爆了。。然后脑子进水就没有叉。。
叉完人后暂时RK1，最后E题FST了。。但还是有RK3，涨了一笔总排名到RK4，上了首页。。
int T,n,m,x,y,i,j,tot,cnt,a[N];LL A,B,C,P,ans;
LL mul(LL a,LL b,LL p){
LL sum=0;for(;b;a=(a+a)%p,b>>=1)if(b&1)sum=(sum+a)%p;
return sum;
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%lld%lld",&A,&P);
if(A<=2){puts("0");continue;}
A-=2;
if(A%2==0)printf("%lld\n",mul(A/2,A+1,P));
else printf("%lld\n",mul(A,(A+1)/2,P));
//fr(i,n)gi(a[i]);
}
}
int T,m,y,i,a,b,c,p,j,tot,cnt;LL A,B,C,E,n,x,ans,f[N];
struct JZ{LL m[5][5];}o,V;
JZ mul(JZ a,JZ b){
JZ c;memset(c.m,0,sizeof c.m);
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c.m[i][j]=(c.m[i][j]+(a.m[i][k]%(p-1))*(b.m[k][j]%(p-1)))%(p-1);
return c;
}
int main(){
for(scanf("%d",&T);T--;){
scanf("%lld%d%d%d%d",&n,&a,&b,&c,&p);
x=pow(a,b,p);memset(o.m,0,sizeof o.m);memset(V.m,0,sizeof V.m);
o.m[1][1]=c;o.m[2][1]=o.m[3][1]=o.m[1][2]=o.m[3][3]=1;
//V.m[1][1]=(c+1)%(p-1);
V.m[1][1]=1;V.m[1][2]=0;V.m[1][3]=1;
if(n==1){
E=0;
}else {
for(n-=2;n;o=mul(o,o),n>>=1)if(n&1)V=mul(V,o);
E=V.m[1][1];
}
//f[1]=0;f[2]=1;
//for(i=3;i<=n;i++)f[i]=(c*f[i-1]+f[i-2]+1)%(p-1);
printf("%lld\n",pow(x,E,p));
//fr(i,n)gi(a[i]);
}
}
#include<cstdio>
#include<cstring>
using namespace std;bool fff;
int T,n,i,j,u,pp,now,la,a[22],b[22],sum,d,x,y,ans,p[]={0,2,3,5,7,11,13,17,19,23};bool v[22];
int G(int x,int y){return !y?x:G(y,x%y);}
void exG(int a,int b,int&x,int&y){
if(!b){x=1;y=0;return;}
exG(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
}
int main(){
for(scanf("%d",&T);T--;){
n=i=j=u=pp=now=la=sum=d=x=y=ans=0;memset(a,0,sizeof a);memset(b,0,sizeof b);memset(v,0,sizeof v);fff=0;
for(scanf("%d",&n),i=sum=1;i<=n;i++)scanf("%d",&a[i]),sum/=G(sum,i),sum*=i;
for(la=i=1;i<=n;i++){
for(j=1;j<=n;j++)if(a[j]==i)u=j;
for(now=1,j=la;j!=u;j=j%n+1)if(!v[j])now++;
if(now==n-i+1)now=0;
b[n-i+1]=now;v[u]=1;la=u;
}
for(i=1;p[i]<=n;i++){
for(j=p[i];j*p[i]<=n;j*=p[i]);
d=sum/j;exG(d,j,x,y);
ans=(ans+d*x*b[j]%sum+sum)%sum;
}
//while(ans<=0)ans+=sum;
if(ans<=0)ans+=sum;
for(i=1;i<=n;i++)if(ans%i!=b[i]){puts("Creation August is a SB!");fff=1;break;}
if(!fff)printf("%d\n",ans);
}
}
int T,n,m,x,y,z,S,i,j,h,t,W,id,X1,Y1,X2,Y2,tot,cnt,a[N],fir[N],d[N],q[N],la[M],ne[M],va[M],ans;bool v[N];
int to[133333][11],ot[133333][11],ed[11];
void ins(int x,int y,int z){
la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;
//printf("%d %d %d\n",x,y,z);
}
void bt(int k,int l,int r){//xia
int i;
for(i=0;i<=W;i++)to[k][i]=++id;
//printf("%d %d %d %d\n",k,l,r,id);
if(l==r){if(l==1)S=to[k][0];if(l==n)for(i=0;i<=W;i++)ed[i]=to[k][i];return;}int md=l+r>>1;
bt(k<<1,l,md);bt(k<<1|1,md+1,r);
for(i=0;i<=W;i++)ins(to[k][i],to[k<<1][i],0),ins(to[k][i],to[k<<1|1][i],0);
// ins(G(k,i,0),G(k<<1,i,0),0),ins(G(k,i,0),G(k<<1|1,i,0),0),
//ins(G(k,i,1),G(k<<1,i,1))
}
void tb(int k,int l,int r){//up
if(l!=r)for(i=0;i<=W;i++)ot[k][i]=++id;
else for(i=0;i<=W;i++)ot[k][i]=to[k][i];
//printf("%d %d %d %d\n",k,l,r,id);
if(l==r){return;}int i,md=l+r>>1;
tb(k<<1,l,md);tb(k<<1|1,md+1,r);
for(i=0;i<=W;i++)ins(ot[k<<1][i],ot[k][i],0),ins(ot[k<<1|1][i],ot[k][i],0);
//to[k<<1][i],0),ins(to[k][i],to[k<<1][i],0);
// ins(G(k,i,0),G(k<<1,i,0),0),ins(G(k,i,0),G(k<<1|1,i,0),0),
//ins(G(k,i,1),G(k<<1,i,1))
}
void cha(int k,int l,int r,int x,int y,int z,int i){//up
if(x<=l&&r<=y){
ins(ot[k][i],z,0);
return;
}int md=l+r>>1;
if(x<=md)cha(k<<1,l,md,x,y,z,i);
if(y>md)cha(k<<1|1,md+1,r,x,y,z,i);
}
void mdf(int k,int l,int r,int x,int y,int z,int i){//up
if(x<=l&&r<=y){
ins(z,to[k][i],0);
return;
}int md=l+r>>1;
if(x<=md)mdf(k<<1,l,md,x,y,z,i);
if(y>md)mdf(k<<1|1,md+1,r,x,y,z,i);
}
int main(){
for(scanf("%d",&T);T--;){
ans=1e9;scanf("%d%d%d",&n,&m,&W);
bt(1,1,n);tb(1,1,n);
for(i=1;i<=m;i++){
scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&z);
for(j=0;j<=W;j++){
x=X1;y=Y1;cha(1,1,n,x,y,id+1,j);mdf(1,1,n,x,y,id+2,j);
x=X2;y=Y2;mdf(1,1,n,x,y,id+2,j);cha(1,1,n,x,y,id+1,j);
ins(id+1,id+2,z);ins(id+2,id+1,z);
id+=2;
}
for(j=0;j<W;j++){
x=X1;y=Y1;cha(1,1,n,x,y,id+1,j);mdf(1,1,n,x,y,id+2,j+1);
x=X2;y=Y2;mdf(1,1,n,x,y,id+2,j+1);cha(1,1,n,x,y,id+1,j);
ins(id+1,id+2,0);ins(id+2,id+1,0);
id+=2;
}
}
for(i=1;i<=id;i++)d[i]=1e9;
for(d[q[t=1]=S]=0,v[S]=1;h^t;)
for(i=fir[x=q[h=h%id+1]],v[x]=0;i;i=ne[i])
if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[t=t%id+1]=y]=1;
for(i=0;i<=W;i++)ans=min(ans,d[ed[i]]);
if(ans==1e9)puts("CreationAugust is a sb!");else printf("%d\n",ans);
}
}
截图留念一下~
2015年8月31日 16:52
橙名lbn？橙名lbn！
2015年8月31日 17:30
红名hzh?红名hzh!
2015年8月31日 18:27
橙名lbn？红名lbn！
2015年9月06日 08:49
双开lbn？双开lbn！
2015年9月13日 09:39
%%%开黑和cheat大师lbn！
2016年4月14日 07:39
这rating不是2333差评啊
2019年11月30日 11:14
敬启者：个人小网站希望大家多多支持 感谢您对我们热心的支持 f88tw┃华歌尔┃I appreciate your kind assistance. f88tw|墓园|捡骨流程|捡骨费用|捡骨时间|禁忌|捡骨颜色|捡骨师|新竹|时间|台北|桃园|苗栗|头份|火化|晋塔|安葬|法事|捡骨|看日子|墓穴|墓园|http://mypaper.m.pchome.com.tw/f88tw
2021年4月07日 20:47
敬启者：个人小网站希望大家多多支持 感谢您对我们热心的支持 f88tw┃华歌尔┃I appreciate your kind assistance. f88tw| 粗工| 粗工内容 | 粗工| 粗工内容 |墓园|捡骨流程|捡骨费用|捡骨时间|禁忌|捡骨颜色|捡骨师|新竹|时间|台北|桃园|苗栗|头份|https://mypaper.m.pchome.com.tw/f88tw
2022年10月04日 01:30
Rajasthan Board Model Paper 2023 Pdf Download for School Education Ajmer & Jaipur Board Sample Model Question Paper for Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 & 12 Standard Theory, Objective (MCQ) and Bit Questions for Hindi Medium, English Medium, Urdu Medium and others. New Exam Scheme orRajasthan Board Question Paper Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.
2023年3月11日 16:37
敬啟者：個人小網站希望大家多多支持 感謝您對我們熱心的支持 f88tw｜華歌爾｜I appreciate your kind assistance.
https://mypaper.pchome.com.tw/f88tw
f88tw|修墳|修墓|新竹|桃園|苗栗|撿骨|拾骨|發票
https://mypaper.pchome.com.tw/f88tw/post/1370781143
https://mypaper.m.pchome.com.tw/f88tw/post/1370781143