[bzo5412/5413/5414]circle/color/simulate_综合

Description

circle
color
simulate

题解

这三道是一套题所以就放一起吧.
又是被队爷OZYdiss烂的一套题

这是circle
首先需要先知道竞赛图的一个性质
就是他的拓扑序一定是一条链
证明考虑逐连通块加入即可
然后注意到题中的一些限制，即保证去除了K个点后的图无环
可以发现如果这个K个点中存在环即无解，于是我们可以知道这两个图都是无环的
那么做出他们的拓扑序后，每个点都会向他后面的所有点有一条有向边
那么考虑如何在这K个点的图中加入尽可能多的点
以下的编号都用拓扑序后从前往后的编号
称去除了的图为图A，K个点的图为图B
可以知道有环的情况一定是从一段A开始走，走一段B最后回到A
那么每个A点记录能去到的编号最前的图B中的点，以及记录能到达他的编号最后的图B中的点
分别称为 $A [i]$ 与 $B [i]$
那么选出的点要满足任意 $i < j$ ， $A [j] > B [i]$
这个直接 $n^2$ 做 $d p$ 即可

这是color
手玩一下可以发现一个性质，就是如果一种颜色在中间出现了，那么最左边这一列与最右边这一列一定要都有这种颜色
证明考虑分开成两个有这种颜色与没有这种颜色的块即可
那么一个naive的想法就是枚举总共可以用多少颜色，算一下用 $i$ 种颜色填满 $j$ 个格子，每种颜色至少用一次的方案数，随意组合一下就可以了
剩下的格子就可以随意填颜色了
算颜色填满的方案数的话直接容斥 $O (n)$ 算即可
但是可以注意一点，我们可以有只在某一边出现没有在中间出现的颜色
注意到只出现了一次的颜色在左边和右边的分布个数是相等的
于是可以枚举有多少种颜色只在左边或者右边出现，这个也随意组合一下就可以了
代码可读性很高

这是simulate
做的我心服口服的一道模拟
真实大模拟
我们分几种模拟，不妨设前面的格子都变成了0或1
1：i=1时 $a[i+1]+=a[i]/2,a[i]\%=2$
2：前面都为1的时候手玩一下可以发现 $a [1] = 0, a [i] ? ?, a [i + 1] + +$
3：前一个为1的时候手玩一下可以发现是把最近的一个零往后移一位，同时 $a [i] ? ?, a [i + 1] + +$
4：前一个是0的时候可以发现是把 $a [i ? 1] + +, a [i] ? = 2, a [i + 1] + +$
用一个栈维护0的位置、
第二种操作的复杂度不超过所有 $a$ 的和
第三种操作可以优化成 $O (1)$ ，配合第四种操作可以知道每次能把栈弹出一个点
复杂度是优秀的 $O (n)$
注意卡常

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
    LL f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(int x){
    write(x);putchar('\n');}
const int MAXN=2005;
struct edge{
    int x,y,next;}a[MAXN*MAXN];int len,last[MAXN];
void ins(int x,int y){
    len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
vector<int> vec1[MAXN],vec2[MAXN];
int L[MAXN],R[MAXN];
int n,K,vis[MAXN];int num[MAXN],fac[MAXN],cnt1,cnt2,g1;
int ru[MAXN];queue<int> li;
int f[MAXN];
int main()
{
    n=read();K=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    int x=read();if(x==1)vec1[i].push_back(j),vec2[j].push_back(i);}for(int i=1;i<=K;i++)vis[read()]=1;for(int i=1;i<=n;i++)if(!vis[i]){
    for(int j=0;j<vec1[i].size();j++){
    int y=vec1[i][j];if(!vis[y])ins(i,y),ru[y]++;}}for(int i=1;i<=n;i++)if(!vis[i]&&!ru[i])li.push(i);while(!li.empty()){
    int x=li.front();li.pop();num[x]=++cnt1;fac[cnt1]=x;for(int k=last[x];k;k=a[k].next){
    ru[a[k].y]--;if(!ru[a[k].y])li.push(a[k].y);}}len=0;memset(last,0,sizeof(last));for(int i=1;i<=n;i++)if(vis[i]){
    g1++;for(int j=0;j<vec1[i].size();j++){
    int y=vec1[i][j];if(vis[y])ins(i,y),ru[y]++;}}for(int i=1;i<=n;i++)if(vis[i]&&!ru[i])li.push(i);while(!li.empty()){
    int x=li.front();li.pop();num[x]=++cnt2;for(int k=last[x];k;k=a[k].next){
    ru[a[k].y]--;if(!ru[a[k].y])li.push(a[k].y);}}if(cnt2!=g1)return puts("impossible"),0;memset(L,63,sizeof(L));for(int i=1;i<=n;i++)if(!vis[i]){
    for(int j=0;j<vec1[i].size();j++){
    int y=vec1[i][j];if(vis[y])L[i]=min(L[i],num[y]);}for(int j=0;j<vec2[i].size();j++){
    int y=vec2[i][j];if(vis[y])R[i]=max(R[i],num[y]);}}for(int i=1;i<=n-g1;i++){
    int x=fac[i];if(L[x]<=R[x])continue;for(int j=min(g1,L[x]-1);j>=0;j--)f[max(R[x],j)]=max(f[max(R[x],j)],f[j]+1);}int sum=K;for(int i=0;i<=g1;i++)sum=max(sum,K+f[i]);if(n-sum>=K)puts("impossible");else pr2(n-sum);return 0;
}

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
const int MAXN=1005;
const int MAXK=1000005;
const int mod=1000000007;
LL pow_mod(LL a,LL b)
{
    LL ret=1;while(b){
    if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
LL pre[MAXK],inv[MAXK];
LL C(int n,int m){
    return pre[n]*inv[m]%mod*inv[n-m]%mod;}
//LL C[MAXN][MAXN];
void ad(LL &x,LL y){
    x+=y;if(x>=mod)x-=mod;}
void dl(LL &x,LL y){
    x-=y;if(x<0)x+=mod;}
int n,m,K;
LL u1[MAXK],u2[MAXN];
LL calc(int u)
{
    LL ret=0;for(int i=u;i>=1;i--){
    LL temp=u1[i];if((u-i)&1)dl(ret,temp*C(u,i)%mod);else ad(ret,temp*C(u,i)%mod);}return ret;
}
int main()
{
    pre[0]=1;for(int i=1;i<MAXK;i++)pre[i]=pre[i-1]*i%mod;inv[MAXK-1]=pow_mod(pre[MAXK-1],mod-2);for(int i=MAXK-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;int T=read();while(T--){
    n=read();m=read();K=read();for(int i=1;i<=K;i++)u1[i]=pow_mod(i,n);if(m==1)pr2(pow_mod(K,n));else if(m==2){
    LL ans=0;for(int i=1;i<=min(n,K);i++){
    LL temp=calc(i);ad(ans,temp*C(K,i)%mod*temp%mod*C(K,i)%mod);}pr2(ans);}else{
    LL ans=0,us=n*(m-2);int lim=min(n,K);for(int i=1;i<=lim;i++)u2[i]=pow_mod(i,us);for(int i=1;i<=lim;i++){
    LL temp=calc(i);for(int j=1;j<=i;j++)if(K-j>=(i-j)*2)ad(ans,temp*C(K,j)%mod*temp%mod*C(K-j,i-j)%mod*C(K-j-(i-j),i-j)%mod*u2[j]%mod);}pr2(ans);}}return 0;
}

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(LL x){
    write(x);putchar('\n');}
const int MAXN=20000005;
//const int MAXN=1005;
char ch[MAXN];
int s[MAXN];
int sta[MAXN],tp;
int main()
{
    
// freopen("data110.in","r",stdin);
// freopen("a.out","w",stdout);gets(ch+1);int len=strlen(ch+1);for(int i=1;i<=len;i++){
    if(ch[i]<'0'||ch[i]>'2'){
    len=i-1;break;}s[i]=ch[i]-'0';}s[2]+=s[1]/2;s[1]&=1;int o;if(s[1]==0)sta[++tp]=1;for(int i=2;i<=len;++i){
    while(s[i]>=2){
    if(!tp)s[1]=0,sta[++tp]=1,--s[i],++s[i+1];else if(sta[tp]==i-1)s[i-1]=1,s[i]-=2,++s[i+1],--tp;else{
    o=i-1-sta[tp];if(o<s[i]){
    s[sta[tp]]=1;sta[tp]=i-1;s[i-1]=0;s[i]-=o;s[i+1]+=o;}else{
    s[sta[tp]]=1;s[sta[tp]+s[i]-1]=0;sta[tp]+=s[i]-1;s[i+1]+=s[i]-1;s[i]=1;}}}if(!s[i])sta[++tp]=i;}for(int i=1;i<=len;i++)ch[i]=s[i]+'0';ch[len+1]='\0';puts(ch+1);return 0;
}