Codeforces Round #369 (Div. 2)

题目链接：http://codeforces.com/contest/711

A.Bus to Udayland

题意：已知一辆公交车，有些座位已经有人(X),现在两个人要上车，要求坐在同一排而且相邻

SB模拟

#include
#include
#include
#include
using namespace std;
int main(){
    int n;
    char a[1005][8];
    bool z=0;
    cin>>n;
    int m,x,y;
    for(int i=0;i>a[i][j];
            if((a[i][0]=='O'&&a[i][1]=='O')){   
                z=1;
                m=i;x=0;
                y=1;
            }
            if((a[i][3]=='O'&&a[i][4]=='O'))
            {   
               z=1;
               m=i;x=3;
               y=4;
            }
     }
     if(z){
        a[m][x]='+';
        a[m][y]='+';
        cout<<"YES"<

B.Chris and Magic Square
题意：已知一个方阵有且仅有一个元素为0，问你能否将这个0改为一个数，使得该方阵每一行，每一列，两条对角线上的元素和都相等，不存在输出-1，注意方阵为1*1时随便输出一个值

#include
#include
#include
#include
using namespace std;
int main(){
    long long int a[505][505],b[505]={0},c[505]={0},p=0,q=0,v=0;
    int n;
    cin>>n;
    int x,y;
    for(int i=0;i>a[i][j];
            b[i]+=a[i][j];
            if(a[i][j]==0){
                 x=i;
                 y=j;
            }
            if(i==j)
                 p+=a[i][j];
            if(i+j==n-1)
                 q+=a[i][j];
        }
    }

    for(int j=0;j0)
           cout<0)
           cout<0)
           cout<0)
           cout<

C.Coloring Trees
题意：已知n棵树排成一排，和m种颜色1,2,3,4,,,m，每个树有一个值c[i]，表示树被染成的颜色，0表示没有染上颜色，现在需要将没有染色的树染上色，将第i(1<=i<=n)棵树染成第j(1<=j<=m)种颜色需要花费pi，定义树染色后的序列美丽度为颜色连续相同的组数，例2,?1,?1,?1,?3,?2,?2,?3,?1,?3 美丽度为 7 ：{2},?{1,?1,?1},?{3},?{2,?2},?{3},?{1},?{3}.问你使得树的美丽度为k的最小花费 1<=k<=n<=100 m<=100，dp的思想很明显，dp[i][j][q]表示第i棵树选择第j种颜色时前i棵树美丽度为q时的最小花费，由于美丽度是否增加和前一棵树有关故，枚举前一棵树的颜色，很好转移复杂度$O(nm^2k)$
注意会爆int

#include
#include
#include
#include
#define minn(a,b) a

D. Directed Roads
题意：已知n个小镇编号为1,2,3,,,n,每个小镇向其他小镇连了一条有向边，现在你可以随便改变这些边的方向，使得任意两个小镇不能相互到达，题目给出的连法也算在内。
初始ans=1，首先将有向图变为无向图，要找到所有的环，则环内点相互到达只有两种途径，要么顺时针，要么逆时针，设环内的点为x，则$ans=ans(2^x-2)$,对于所有不在环内的点，它的边无论怎么改变都都符合要求，设环外点数为y，则$ans=ans2^y$;

#include
#include
#include
#include
#include
#include
#define minn(a,b) a g[maxn],bcc[maxn];
stack s;
int dfs(int u,int fa){
    int lowu=pre[u]=++dfs_clock;
    int child=0;
    for(int i=0;i=pre[u]){
                iscut[u]=true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                for(;;){
                    Edge x=s.top();s.pop();
                    if(bccno[x.u]!=bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;}
                    if(bccno[x.v]!=bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;}
                    if(x.u==u&&x.v==v) break;
                }
            }
        }
        else if(pre[v]

E. ZS and The Birthday Paradox
题意：在某个岛上一年有$2^n$天($1<=n<=10^{18}$),有k个人($2<=k<=10^{18}$)，问你这k个人中至少有两个人同一天生日的概率是多大，答案将分数先化为最简分数再对$M=10^6+3$取模
首先，如果人数大于天数，则概率为1 
根据概率公式，至少两人同一天生日的概率为：$\begin{align} P &=1- \frac{2^n(2^n-1)...*(2^n-(k-1))}{(2^n)^k} \end{align} $
首先对分子分母化简，应当同时除以$2^{n+\sum_{i=1}^{k-1} i/2}$
由于最后的结果要对M取模，分子为连续k个整数，分母只有2的倍数，分子分母只同时除以2的倍数，考虑到M为质数，故当k>=M时，这连续k个数中一定有M的倍数，此时化简后同时对M取模，则分子取模后为0，此时分子分母均为$2^{n*k-(n+\sum_{i=1}^{k-1} i/2)}$，使用快速幂即可。
当k

#include
#include
#include
#include
#include
#include
#define minn(a,b) ak)
        break;
   }
   if(z0){
    sum2+=q/2;
    q=q/2;
   }
   ll x=(n%m*((k-1)%m)%m-sum2%m+m)%m;
   ll y=powmod(2,x);
   if(k-1>=M){
    printf("%lld %lld\n",y,y)
    return 0;
   }
   else {
    ll ans=1;
    for(int i=1;i<=k-1;i++){
        ll p=n;
        int j=i;
        while(j%2==0){
            j=j/2;
            p--;
        }
        ans=ans*(powmod(2,p)-j)%M;
    }
    printf("%lld %lld\n",(y-ans+M)%M,y);
   }
}