尼玛pdf依旧不会粘23333
/* 每段合并到总的里面 假设总的有X个 这一段有Y个 一共有X+1个空 那么就有 C(X+1,1)+C(X+1,2)+C(X+1,3)+...+C(X+1,Y) 这样是WA的！！！ 比如说 C(X+1,2) 那就是Y个放到两个空里 分别放几个...忘了算了23333 自己就想到这里 Wa了 10分 (暴力40 吐血了) */ #include<iostream> #include<cstdio> #define maxn 1010 #define mod 1000000007 #define ll long long using namespace std; ll n,m,a[maxn],f[maxn],len[maxn],c[maxn][maxn],ans=1; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Get_c(){ for(int i=0;i<=n;i++)c[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } ll G(ll x,ll y){ ll sum=0; for(ll i=1;i<=y;i++) sum+=c[x+1][i]; return sum; } int main() { freopen("lantern.in","r",stdin); freopen("lantern.out","w",stdout); n=init();m=init(); for(int i=1;i<=m;i++){ ll x=init();f[x]=1; } Get_c(); ll sum=0;f[n+1]=1; for(int i=1;i<=n+1;i++){ if(!f[i])sum++; else { len[++len[0]]=sum;sum=0; } } sum=len[1]; for(int i=2;i<=len[0];i++){ ans=ans*G(sum,len[i]); ans%=mod;sum+=len[i]; } for(int i=2;i<len[0];i++){ ans=ans*(1<<len[i]-1); ans%=mod; } cout<<ans<<endl; }
/* 同桌想到了更简单的方法 合并的方案数有(n-m)!/(πlen[i]!) 证明吗 我们联想 4个红球 3个黑球 5个蓝球 放在一起的方案数 (4+3+5)!/(4!*3!*5!) 就是把一样的颜色删掉 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 #define mod 1000000007 #define inf 1e10 #define ll long long using namespace std; ll n,m,a[maxn],f[maxn],ans=1,len[maxn],c[maxn],prime[maxn],num; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Prime(){ for(int i=2;i<=n;i++){ if(f[i]==0)prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>n)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } void J(ll x){ for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n){ c[i]+=x/P; P*=prime[i]; } } } void JJ(ll x){ for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n){ c[i]-=x/P; P*=prime[i]; } } } ll Pow(ll x,ll y){ ll r=1; for(int i=1;i<=y;i++) r=r*x,r%=mod; return r; } int main() { freopen("lantern.in","r",stdin); freopen("lantern.out","w",stdout); n=init();m=init(); for(int i=1;i<=m;i++){ ll x=init();f[x]=1; } ll sum=0;f[n+1]=1; for(int i=1;i<=n+1;i++){ if(!f[i])sum++; else { len[++len[0]]=sum;sum=0; } } memset(f,0,sizeof(f)); Prime();J(n-m); for(int i=1;i<=len[0];i++) JJ(len[i]); for(int i=2;i<len[0];i++){ ans=ans*Pow(2,len[i]-1); ans%=mod; } for(int i=1;i<=n;i++) ans=ans*Pow(prime[i],c[i]),ans%=mod; cout<<ans<<endl; return 0; }
#include<iostream> #include<cstdio> #include<algorithm> #define maxn 100010 #define inf 1e18 #define ll long long using namespace std; ll n,m,p[maxn],c[maxn],ans; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } bool Judge(ll x){ for(int j=1,i=1;i<=n;i++){ if(p[i]-c[j]>x)return 0; ll R=0; if(c[j]<p[i])R=max(x-(p[i]-c[j])+c[j],(x+p[i]+c[j])/2); else R=p[i]+x; while(j<=m+1&&R>=c[j])j++; if(j>m)return 1; } return 0; } int main() { freopen("data.in","r",stdin); freopen("data.out","w",stdout); n=init();m=init(); for(int i=1;i<=n;i++)p[i]=init(); for(int i=1;i<=m;i++)c[i]=init(); ll l=0,r=inf; while(l<=r){ ll mid=l+r>>1; if(Judge(mid)){ r=mid-1;ans=mid; } else l=mid+1; } cout<<ans<<endl; return 0; }
/*暴力没调出来 输出了不修改的 然而没数据 过几天再改吧*/ #include<cstdio> #include<cstring> #include<iostream> #define maxn 100010 #define inf 100000000 #define ll long long using namespace std; ll n,m,num,head[maxn],len[maxn],C,f[maxn]; struct node{ ll v,t,pre,o; }e[maxn*2]; struct edge{ ll u,v,t; }p[maxn]; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } ll min(ll x,ll y){ return x>y?x:y; } void Add(ll from,ll to,ll dis,ll fal){ num++;e[num].v=to; e[num].t=dis; e[num].o=fal; e[num].pre=head[from]; head[from]=num; } ll Dfs(ll now,ll from){ ll s=1;f[now]=1; for(ll i=head[now];i;i=e[i].pre){ ll v=e[i].v; if(v!=from&&i!=C)s+=Dfs(v,now); } return s; } ll Get(){ ll sum=0; for(ll i=1;i<=m;i++){ ll l=Dfs(p[i].u,p[i].v); ll r=Dfs(p[i].v,p[i].u); len[i]=l*r*p[i].t;sum+=len[i]; } return sum; } ll Solve(ll u,ll v,ll x){ C=x;memset(f,0,sizeof(f));m++; Add(u,v,p[x].t,n);Add(v,u,p[x].t,n); ll sum=Get();for(ll i=1;i<=n;i++) if(f[i]==0)return inf; num-=2;m--;return sum; } int main() { //freopen("road.in","r",stdin); //freopen("road.out","w",stdout); n=init();ll u,v,t;m=n-1; for(ll i=1;i<n;i++){ u=init();v=init();t=init(); p[i].u=u;p[i].v=v;p[i].t=t; Add(u,v,t,i);Add(v,u,t,i); } ll mx=Get(); /*for(ll i=1;i<=n;i++) for(ll j=i+1;j<=n;j++) for(ll k=1;k<=m;k++){ mx=min(mx,Solve(i,j,k)); }*/ cout<<mx<<endl; return 0; }