ACM-ICPC 2018 徐州赛区网络预赛

待补：

A.Hard to prepare

设答案 为 dp[n];
考虑第n个人的面具
1.与第一个相同,这时候相当于n-1个人，即dp[n-1]
2. 与第一个不同，根据同或不等于0的原则最后一个有 (2^k-2)中选择（排除自身和同或等于0)

2 k ∗ ( 2 k − 1 ) ( n − 2 ) ∗ ( 2 k − 2 )

这个时候直接打表就足够了，但是化简一下算个快速幂就出来了

g ( n ) = 2 k ∗ ( 2 k − 1 ) ( n − 2 ) ∗ ( 2 k − 2 ) + g ( n − 2 ) ;

g ( 2 ) = 2 k ∗ ( 2 k − 1 )
g ( 1 ) = 2 k ;
g ( 0 ) = 1

g ( n ) = ( 2 k − 1 ) n − ( 2 k − 1 ) ( n − 2 ) + ( 2 k − 1 ) ( n − 2 ) − ( 2 k − 1 ) ( n − 4 ) + + ( 2 k − 1 ) n − ( 2 k − 1 ) 2 + 2 k ∗ ( 2 k − 1 )

n 为 偶数

g ( n ) = ( 2 k − 1 ) n − ( 2 k − 1 ) ( n − 2 ) + ( 2 k − 1 ) ( n − 2 ) − ( 2 k − 1 ) ( n − 4 ) + + ( 2 k − 1 ) 4 − ( 2 k − 1 ) 2 + ( 2 k − 1 ) ∗ ( 2 k − 1 ) + 2 k − 1 ;

g ( n ) = ( 2 k − 1 ) n + 2 k − 1 ;

发现当n== 0 的时候同样符合这个式子
n 为奇数
g ( n ) = ( 2 k − 1 ) n − ( 2 k − 1 ) ( n − 2 ) + ( 2 k − 1 ) ( n − 2 ) − ( 2 k − 1 ) ( n − 4 ) + + ( 2 k − 1 ) 3 − ( 2 k − 1 ) 1 + 2 k − 1 + 1 ;

g ( n ) = ( 2 k − 1 ) n + 1 ; 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 1e9+7;
int n,m;

ll qpow(ll a,ll b){ll s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll ans;
        cin>>n>>m;
        ll k=(qpow(2,m)-1)%mod;

        if(n%2==0)
        ans=((qpow(k,n)+k))%mod;
        else
        ans=((qpow(k,n)+1))%mod;
        printf("%lld\n",ans);

    }


    return 0;
}

B B. BE, GE or NE

记忆化搜索

const int maxn = 1e5+100;
int a[maxn],b[maxn],c[maxn],cnt[maxn];
int result[maxn][300];
int n,m,l,r; 
int check(int n){
    if(n <-100)  return -100;
    if(n > 100)  return 100;
    return n;
}
int dfs(int pos,int m){
    if(pos == n){
        if(m <= l)
            return 1;
        else if(m >= r)
            return 0;
        else
            return 2;
    }
    int t = pos&1;
    int aa,bb,cc;
    aa=bb=cc=-1;
    if(a[pos]){
        int x = pos+1,y = check(m+a[pos]);
        if(result[x][y+100] != 1000)
           aa = result[x][y+100];
        else 
           aa = result[x][y+100] = dfs(x,y);
        if(aa==t) return t;
    } 
    if(b[pos]){
        int x = pos+1,y = check(m-b[pos]);
        if(result[x][y+100] != 1000)
           bb = result[x][y+100];
        else 
           bb = result[x][y+100] = dfs(x,y);
        if(bb==t) return t;
    } 
    if(c[pos]){
        int x = pos+1,y = -m;
        if(result[x][y+100] != 1000)
            cc = result[x][y+100];
        else
            cc = result[x][y+100] = dfs(x,y);
        if(cc==t) return t;
    } 
    if(aa == 2||bb == 2||cc == 2) return 2;
    return !t;
}
int main(void)
{

   cin>>n>>m>>r>>l;
   rep(i,0,n+1)
     rep(j,-100,100+1)
         result[i][j+100] = 1000;
   rep(i,0,n) scanf("%d%d%d",&a[i],&b[i],&c[i]);
   int ans = dfs(0,m);
   if(ans == 0) printf("Good Ending\n");
   else if(ans == 1) printf("Bad Ending\n");
   else puts("Normal Ending"); 

   return 0;

H. Ryuji doesn’t want to study

用线段树维护前缀和，每一次单点更改x点的值，相当于更新所有x-n的前缀和，查询的时候，是l，r的前缀和的和- (r-l+1)*sum(l-1)


#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
using namespace std;
typedef long long LL;
const LL     mod = 1e9 + 7;
#define lson (o<<1)
#define rson (o<<1|1)
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e6+10;
int ar[maxn];
const int maxnode = 4*maxn;

LL sumv[maxnode]; 
LL addv[maxnode];
LL S[maxn];
void Fre(){
  freopen("input.txt","r",stdin);
  freopen("output.txt","w+",stdout);
}
void build(int o,int L,int R)
{ 
    int m = (R+L)>>1;
    if(L == R) sumv[o] = S[L];
    else
    {
        build(lson,L,m);
        build(rson,m+1,R);
        sumv[o] = sumv[lson]+sumv[rson];
    }
}

void update(int o,int L,int R,int y1,int y2,int add){
    // cout<<1<<endl;
    if(y1 <= L && y2 >= R){
        addv[o] += add;
    }
    else{
        // assert(L,)
        sumv[o] += 1ll*(min(R,y2)-max(L,y1)+1)*add;
        int M = (R+L)>>1;
        if(y1 <= M) update(lson,L,M,y1,y2,add);
        if(y2 > M) update(rson,M+1,R,y1,y2,add);

    }

}

LL query(int o,int L,int R,int y1,int y2){
    LL _sum = 0;
    if(y1 <= L&&y2 >= R){
        _sum += sumv[o] +addv[o]*(R-L+1);
    }
    else{
        int M = (R+L)>>1;
        sumv[o]  = sumv[o]+1ll*(R-L+1)*addv[o];
        addv[lson] += addv[o];
        addv[rson] += addv[o];
        addv[o] = 0;
        if(y1 <= M) _sum += query(lson,L,M,y1,y2);
        if(y2 > M) _sum += query(rson,M+1,R,y1,y2);
    } 
    return _sum;
}

int main(void)
{
   int n,q;
   cin>>n>>q;
   rep(i,1,n+1) {
    scanf("%d",&ar[i]);
    S[i] = S[i-1]+ar[i];
   }

   build(1,1,n);
   rep(i,0,q){
    int op,x,y;
    scanf("%d%d%d",&op,&x,&y);
    LL ans = 0;
    if(op==1)  {
        ans = query(1,1,n,x,y);
        if(x!=1) 
            ans -= 1ll*(y-x+1)*query(1,1,n,x-1,x-1);
        printf("%lld\n",ans);
       }
    else  {
        update(1,1,n,x,n,y-ar[x]);
        ar[x] = y;
       }
   }

   return 0;
}

K. Cacti Lottery

具体题解参考CatDsy
可以用bitset 优化矩阵的乘法


LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 70;
struct Matrix{
   int  n,m;
   int a[maxn][maxn];
   Matrix(int nn = 0,int mm = 0):n(nn),m(mm){me(a);}
};

Matrix operator *(const Matrix &a,const Matrix &b){
    Matrix c(a.n,b.m);
    bitset<70> A[70],B[70];
    rep(i,0,a.n)
       rep(j,0,a.m)
        A[i][j] = a.a[i][j];
    rep(i,0,b.n)
       rep(j,0,b.m)  
          B[j][i] = b.a[i][j];
    for(int i = 0;i < a.n; ++i){
        for(int j  = 0;j < b.m; ++j){

            c.a[i][j] = (A[i]&B[j]).count()&1 ;
        }
    }
    return c;
}


int A[10][10],B[10][10];
void solve(int n,int m,int t){
    m /= 2;

    Matrix a(1,n*n),M(n*n,n*n);
    rep(i,0,n){
        rep(j,0,n){
            a.a[0][i*n+j] = A[i][j]&1;
            for(int p = i-m; p <= i+m; ++p){
                for(int q = j-m; q <= j+m; ++q){
                    if(p < 0||p >= n||q < 0||q >= n) continue;
                    M.a[p*n+q][i*n+j] = B[p-i+m][q-j+m]&1;
                }
            }
        }
    }
    // DEBUG;
    while(t > 0){
        if(t & 1)
            a = a*M;
        M = M*M;
        t >>= 1;
         // DEBUG;
    }
    int cnt = 0;
    rep(i,0,n)
      rep(j,0,n)
          if(a.a[0][i*n+j])
                cnt++;
    printf("%d\n",cnt);
 }

int main(void){
    int T;
    scanf("%d",&T);
    while(T--){
        int N,M,t;
        scanf("%d%d%d",&N,&M,&t);
    rep(i,0,N) 
      rep(j,0,N)
       scanf("%d",&A[i][j]);
    rep(i,0,M)
      rep(j,0,M)
       scanf("%d",&B[i][j]);
       solve(N,M,t);
    }




    return 0;
}