gym101480

A. ASCII Addition

模拟 

#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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 hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
char s[10][N],ans[10][N];

int id(int i) {
    if (string(s[1]+i,s[1]+i+5)=="....x") {
    if (string(s[2]+i,s[2]+i+5)=="....x")
    if (string(s[3]+i,s[3]+i+5)=="....x")
    if (string(s[4]+i,s[4]+i+5)=="....x")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="....x")
    return 1;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="....x")
    if (string(s[3]+i,s[3]+i+5)=="....x")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="x....")
    if (string(s[6]+i,s[6]+i+5)=="x....")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 2;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="....x")
    if (string(s[3]+i,s[3]+i+5)=="....x")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 3;
    }
    if (string(s[1]+i,s[1]+i+5)=="x...x") {
    if (string(s[2]+i,s[2]+i+5)=="x...x")
    if (string(s[3]+i,s[3]+i+5)=="x...x")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="....x")
    return 4;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="x....")
    if (string(s[3]+i,s[3]+i+5)=="x....")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 5;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="x....")
    if (string(s[3]+i,s[3]+i+5)=="x....")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="x...x")
    if (string(s[6]+i,s[6]+i+5)=="x...x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 6;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="....x")
    if (string(s[3]+i,s[3]+i+5)=="....x")
    if (string(s[4]+i,s[4]+i+5)=="....x")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="....x")
    return 7;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="x...x")
    if (string(s[3]+i,s[3]+i+5)=="x...x")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="x...x")
    if (string(s[6]+i,s[6]+i+5)=="x...x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 8;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="x...x")
    if (string(s[3]+i,s[3]+i+5)=="x...x")
    if (string(s[4]+i,s[4]+i+5)=="xxxxx")
    if (string(s[5]+i,s[5]+i+5)=="....x")
    if (string(s[6]+i,s[6]+i+5)=="....x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 9;
    }
    if (string(s[1]+i,s[1]+i+5)=="xxxxx") {
    if (string(s[2]+i,s[2]+i+5)=="x...x")
    if (string(s[3]+i,s[3]+i+5)=="x...x")
    if (string(s[4]+i,s[4]+i+5)=="x...x")
    if (string(s[5]+i,s[5]+i+5)=="x...x")
    if (string(s[6]+i,s[6]+i+5)=="x...x")
    if (string(s[7]+i,s[7]+i+5)=="xxxxx")
    return 0;
    }
    return -1;
}

void add(int x, int y, string s) {
    ans[x][y]=s[0],ans[x][y+1]=s[1],ans[x][y+2]=s[2],ans[x][y+3]=s[3],ans[x][y+4]=s[4];
}
int tot;
void pr(int x) {
    ++tot;
    if (x==1) {
        add(1,tot,"....x");
        add(2,tot,"....x");
        add(3,tot,"....x");
        add(4,tot,"....x");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"....x");
    }
    if (x==2) {
        add(1,tot,"xxxxx");
        add(2,tot,"....x");
        add(3,tot,"....x");
        add(4,tot,"xxxxx");
        add(5,tot,"x....");
        add(6,tot,"x....");
        add(7,tot,"xxxxx");
    }
    if (x==3) {
        add(1,tot,"xxxxx");
        add(2,tot,"....x");
        add(3,tot,"....x");
        add(4,tot,"xxxxx");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"xxxxx");
    }
    if (x==4) {
        add(1,tot,"x...x");
        add(2,tot,"x...x");
        add(3,tot,"x...x");
        add(4,tot,"xxxxx");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"....x");
    }
    if (x==5) {
        add(1,tot,"xxxxx");
        add(2,tot,"x....");
        add(3,tot,"x....");
        add(4,tot,"xxxxx");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"xxxxx");
    }
    if (x==6) {
        add(1,tot,"xxxxx");
        add(2,tot,"x....");
        add(3,tot,"x....");
        add(4,tot,"xxxxx");
        add(5,tot,"x...x");
        add(6,tot,"x...x");
        add(7,tot,"xxxxx");
    }
    if (x==7) {
        add(1,tot,"xxxxx");
        add(2,tot,"....x");
        add(3,tot,"....x");
        add(4,tot,"....x");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"....x");
    }
    if (x==8) {
        add(1,tot,"xxxxx");
        add(2,tot,"x...x");
        add(3,tot,"x...x");
        add(4,tot,"xxxxx");
        add(5,tot,"x...x");
        add(6,tot,"x...x");
        add(7,tot,"xxxxx");
    }
    if (x==9) {
        add(1,tot,"xxxxx");
        add(2,tot,"x...x");
        add(3,tot,"x...x");
        add(4,tot,"xxxxx");
        add(5,tot,"....x");
        add(6,tot,"....x");
        add(7,tot,"xxxxx");
    }
    if (x==0) {
        add(1,tot,"xxxxx");
        add(2,tot,"x...x");
        add(3,tot,"x...x");
        add(4,tot,"x...x");
        add(5,tot,"x...x");
        add(6,tot,"x...x");
        add(7,tot,"xxxxx");
    }
    tot += 4;
}

int a[N],cnt;
int main() {
    REP(i,1,7) scanf("%s",s[i]+1);
    int len = strlen(s[1]+1);
    REP(i,1,len) {
        a[++cnt] = id(i);
        i += 5;            
    }
    ll L = 0, R = 0;
    REP(i,1,cnt) {
        if (a[i]==-1) {
            REP(j,i+1,cnt) R = R*10+a[j];
            break;
        }
        L = L*10+a[i];
    }
    L += R;
    int s[100],cnt=0;
    while (L) s[++cnt]=L%10,L/=10;
    PER(i,1,cnt) { 
        pr(s[i]);
        if (i!=1) {
            ++tot;
            ans[1][tot]='.';
            ans[2][tot]='.';
            ans[3][tot]='.';
            ans[4][tot]='.';
            ans[5][tot]='.';
            ans[6][tot]='.';
            ans[7][tot]='.';
        }
    }
    REP(i,1,7) puts(ans[i]+1);
}

B. Book Borders

直接二分模拟就能过

#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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 hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n,a,b,sum[N];
string s[N],t;

int len(int i, int j) {
    return sum[j]-sum[i-1]+j-i;
}

int main() {
    getline(cin,t);
    stringstream ss(t);
    while (ss>>t) s[++n]=t;
    cin>>a>>b;
    REP(i,1,n) sum[i]=sum[i-1]+s[i].size();
    REP(x,a,b) {
        int t = 1, ans = 0;
        while (t<=n) {
            int l=t,r=n,pos=-1;
            while (l<=r) {
                if (len(t,mid)<=x) pos=mid,l=mid+1;
                else r=mid-1;
            }
            if (ans) ans += s[t].size()+1;
            else ans += s[t].size();
            t = pos+1;
        }
        printf("%d\n",ans);
    }
}

D. Digit Division

求出所有可划分的位置, 如果位置$n$不能划分那么显然无解, 否则为$2^{cnt-1}$ 

#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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 hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n,m;
char s[N];

int main() {
    scanf("%d%d%s",&n,&m,s+1);
    ll t = 0, cnt = 0;
    REP(i,1,n) {
        t = (t*10+s[i]-'0')%m;
        if (!t) ++cnt;
    }
    if (t) return puts("0"),0;
    printf("%d\n",qpow(2,cnt-1));
}

F. Frightful Formula

先考虑$c=0$的情况

对于$t_i$, 考虑从$(2,i)$到$(n,n)$的所有路径, 可以得到贡献为$a^{n-i}b^{n-1}\binom{2n-i-2}{n-i}$. 

对于$l_i$, 贡献为$a^{n-1}b^{n-i}\binom{2n-i-2}{n-i}$

然后再考虑$c$的贡献, 相当于是以所有点$(i,j)$为起点,终点为$(n,n)$的路径贡献和

也就是$\sum\limits_{i=2}^n\sum\limits_{j=2}^n a^{n-j}b^{n-i}\binom{2n-i-j}{n-i}$

枚举$i+j$,那么这个式子可以看成卷积,然后用任意模数$NTT$来求.

还有一种方法是设$g_{i,j}=f_{i,j}+\frac{c}{a+b-1}$, 那么$g_{i,j}=ag_{i,j-1}+bg_{i-1,j}$, 这样就可以避免求$c$的贡献

#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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 hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
const int P = 1e6+3;
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

const int N = 5e5+10;
int n,a,b,c,l[N],t[N];
int fac[N],ifac[N],pa[N],pb[N];
ll C(int n, int m) {
    return (ll)fac[n]*ifac[m]%P*ifac[n-m]%P;
}
int main() {
    scanf("%d%d%d%d",&n,&a,&b,&c);
    fac[0]=pa[0]=pb[0]=1;
    REP(i,1,N-1) { 
        pa[i]=(ll)pa[i-1]*a%P;
        pb[i]=(ll)pb[i-1]*b%P;
        fac[i]=(ll)fac[i-1]*i%P;
    }
    ifac[N-1] = qpow(fac[N-1],P-2);
    PER(i,0,N-2) ifac[i]=(ll)ifac[i+1]*(i+1)%P;
    int k = (ll)c*qpow(a+b-1,P-2)%P;
    REP(i,1,n) scanf("%d",l+i),l[i]=(l[i]+k)%P;
    REP(i,1,n) scanf("%d",t+i),t[i]=(t[i]+k)%P;
    int ans = 0;
    REP(i,2,n) { 
        ans = (ans+(ll)l[i]*pa[n-1]%P*pb[n-i]%P*C(2*n-i-2,n-i))%P;
        ans = (ans+(ll)t[i]*pb[n-1]%P*pa[n-i]%P*C(2*n-i-2,n-i))%P;
    }
    ans = (ans-k)%P;
    if (ans<0) ans+=P;
    printf("%d\n",ans);
}

K. Kernel Knights

大意: 给定二分图, 每个点出度为$1$. 求一个核, 满足核内的点之间没边, 核外每个点都与核内有一条方向从内向外的边.

出度为$1$, 那么就保证每个点最多属于一个环, 二分图就保证只有偶环. 所以可以先拓排一下, 最后处理一下偶环即可.

#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#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 hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n, deg[N], nxt[N];
queue<int> q;
int vis[N],ans[N];

int main() {
    scanf("%d", &n);
    REP(i,1,2*n) scanf("%d",nxt+i),++deg[nxt[i]];
    REP(i,1,2*n) if (!deg[i]) q.push(i),vis[i]=1;
    while (q.size()) {
        int u = q.front(); q.pop();
        int v = nxt[u];
        if (ans[u]!=2) ans[u] = 1;
        if (vis[v]) continue;
        if (ans[u]==1) ans[v]=2,vis[v]=1,q.push(v);
        if (vis[v]) continue;
        if (!--deg[v]) vis[v]=1,q.push(v);
    }
    REP(i,1,2*n) if (!vis[i]) {
        int now = i, cur = 0;
        while (!vis[now]) {
            cur ^= 1;
            vis[now] = 1;
            if (cur) ans[now] = 1;
            now = nxt[now];
        }
    }
    REP(i,1,2*n) if (ans[i]==1) printf("%d ",i);hr;
}
数学-组合计数图论-拓扑排序

相关

标签