2018.7.10模拟赛

T1考场上一直想拿那80分，dp推了半天没出来，搜索40分走人。正解是组合数学，倒着考虑，前面有sum[i]-1个位置，每个位置可以放当前i的num[i]-1个，费马小定理+组合数搞。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long

using namespace std;
const int MAXN = 500005;
const int mod = 998244353;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,sum,num[MAXN];
LL ans=1,inv[MAXN],to[MAXN];

inline LL C(int n,int m){
    return to[n]*inv[m]%mod*inv[n-m]%mod;
}

inline LL fast_pow(LL A,int B){
    LL ret=1;
    for(;B;B>>=1){
        if(B&1) ret=ret*A%mod;
        A=A*A%mod;
    }
    return ret;
}

int main(){
    freopen("qiang.in","r",stdin);
    freopen("qiang.out","w",stdout);
    n=rd();
    to[1]=1;
    for(register int i=2;i<=500000;i++) to[i]=to[i-1]*i%mod;
//  cout<<to[MAXN];
    inv[MAXN-5]=fast_pow(to[MAXN-5],mod-2);
//  cout<<inv[MAXN]<<endl;
    for(register int i=499999;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(register int i=1;i<=n;i++) num[i]=rd(),sum+=num[i];
    for(register int i=n;i;i--){
        LL k=C(sum-1,num[i]-1);
        if(k!=0)
        ans*=k,ans%=mod;
//      cout<<ans<<endl;
        sum-=num[i];
    }
    printf("%lld",ans);
    return 0;
}

T2考场上以为是一个规律题，打表找规律，结果GG，搜索30分滚蛋（我可能是个只会爆搜的蒟蒻）。正解矩阵快速幂，以前做过这种类型的状压题，貌似这次状压就能水60分，

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long

using namespace std;

int n,m;

struct Mat{
    int a[17][17];
    Mat(){
        memset(a,0,sizeof(a));
    }
    Mat operator*(const Mat &h){
        Mat c;
        for(register int i=0;i<16;i++)
            for(register int j=0;j<16;j++)
                for(register int k=0;k<16;k++){
                    c.a[i][j]+=a[i][k]*h.a[j][k]%m;
                    c.a[i][j]%=m;
                }
        return c;
    }
}A,k;

inline bool judge(int x){
    if(x==0 || x==3 || x==9 || x==12 || x==15) return true;
    return false;
}

inline void init(){
    for(register int i=0;i<16;i++)
        k.a[i][i]=1;
    for(register int i=0;i<16;i++)
        for(register int j=0;j<16;j++)
            if((!(i&j)) and judge(i|j))
                A.a[i][j]=1;
}

inline Mat fast_pow(Mat a,int x){
    Mat ret=k;
    for(;x;x>>=1){
        if(x&1) ret=ret*a;
        a=a*a;
    }
    return ret;
}

int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    init();
    while(~scanf("%d%d",&n,&m),n){
        Mat B=k*fast_pow(A,n-1);
        LL ans=0;
        for(register int i=0;i<16;i++)
            if(judge(i)) ans+=B.a[0][i],ans%=m;
        printf("%lld
",ans);
    }
    return 0;
}

T3考场上推了半天，以为是个毒瘤dp，就开始狂码。结果爆零，最后说是国家集训队的作业题？？？全场拿分的就两个？？？最高的30？？？溜了。最后看了半天代码也没咋懂，s数组表示的是差分数组，思想是把mod4意义下的数列变成普通的数列，只后似乎是一个贪心的思路，一直找最小值。代码先放这儿，以后再慢慢啃。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}

using namespace std;
const int MAXN = 100005;

int n,a[MAXN],b[MAXN],c[MAXN],s[6];
int T,ans;

int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    T=rd();
    while(T--){
        n=rd();
        for(register int i=1;i<=n;i++) a[i]=rd();
        for(register int i=1;i<=n;i++) b[i]=rd(),c[i]=(4+b[i]-a[i])%4;
        ans=c[1];int j=0;
        memset(s,0,sizeof(s));
        for(register int i=2;i<=n;i++){
            s[(4+c[i]-c[i-1]-1)%4+1]++;
            if(c[i]<=c[i-1]) continue;
            for(j=0;!s[j];j++);
            s[j]--;
            ans+=j;
        }
        printf("%d
",ans);
    }
    return 0;
}