2019.10.8

· · 个人记录

T1:

在n*m的矩阵A中所有位置中随机填入0或1,概率比为x:y,令B_i=\sum\limits_{j=1}^{m}A_{i,j},求min(B_i)的期望,将期望乘(x+y)^{nm}后模1000000007的值

先考虑求出f[i]表示一行和为i的方案数

f[i]=C_m^ix^{m-i}y^{i}

考虑求出g[i]表示一行和大于i的方案数

g[i-1]=g[i]+f[i]

枚举最小值i以及等于最小值的行有j个

答案就是:

ans=\sum\limits_{i=0}^{m}\sum\limits_{j=1}^{n}C_n^jf[i]^{j}g[i]^{n-j}

于是70pts就有了

考虑容斥一下:

ans=\sum\limits_{i=0}^{m}(g[i-1]^n*g[i]^n)

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200010;
const ll mod=1000000007;
int n,m,x,y;
ll ans;
ll f[maxn],g[maxn],fac[maxn];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline ll power(ll x,ll k)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=(res*x)%mod;
        x=(x*x)%mod;k>>=1;
    }
    return res;
}
inline ll C(int x,int y){return ((fac[x]*power(fac[x-y],mod-2))%mod*power(fac[y],mod-2))%mod;}
int main()
{
    //freopen("past.in","r",stdin);
    //freopen("past.out","w",stdout);
    n=read(),m=read(),x=read(),y=read();
    fac[0]=fac[1]=1;for(int i=2;i<=m;i++)fac[i]=(fac[i-1]*i)%mod;
    //printf("%lld\n",C(2,1));
    for(int i=0;i<=m;i++)f[i]=((C(m,i)*(power(x,m-i))%mod*power(y,i))%mod)%mod;
    for(int i=m;i;i--)g[i-1]=(g[i]+f[i])%mod;
    for(int i=1;i<=m;i++)ans=(ans+(((power(g[i-1],n)-power(g[i],n))%mod+mod)%mod)*i)%mod;
    printf("%lld",ans);
    return 0;
}

T2:

对n*m的零矩阵A进行Q次操作:

1\ i\ j$:将$A_{i,j}$取反$(xor\ 1) $3\ j$:将$A$矩阵第$j$列的所有元素取反 $4\ k$:将$A$矩阵还原成第$k$次操作之后的状态 离线将所有操作建成操作树,按着dfs的顺序求出每个操作的答案 考试时给每个点开了个vector,存下一个点是谁,本质相同 $O(NQ)

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int maxq=100010;
int n,m,Q,sum;
int ans[maxq];
int a[maxn][maxn];
bool vis[maxn];
vector<int>nxt[maxq];
struct Query{int op,x,y;}qr[maxq];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
inline void change(int id)
{
    if(qr[id].op==4||!qr[id].op)return;
    int op=qr[id].op,x=qr[id].x,y;
    if(op==1)y=qr[id].y;
    if(op==1)sum+=a[x][y]?-1:1,a[x][y]^=1;
    if(op==2)
        for(int i=1;i<=m;i++)
            sum+=a[x][i]?-1:1,a[x][i]^=1;
    if(op==3)
        for(int i=1;i<=n;i++)
            sum+=a[i][x]?-1:1,a[i][x]^=1;
}
void solve(int x)
{
    //printf("in::%d \n",x);
    change(x);ans[x]=sum;
    for(unsigned int i=0;i<nxt[x].size();i++)solve(nxt[x][i]);
    change(x);
    //printf("out::%d\n",x);
}
int main()
{
    //freopen("present.in","r",stdin);
    //freopen("present.out","w",stdout);
    n=read(),m=read(),Q=read();
    for(int i=1;i<=Q;i++)
    {
        qr[i].op=read(),qr[i].x=read();
        if(qr[i].op==1)qr[i].y=read();
        if(qr[i].op!=4)nxt[i-1].push_back(i);
        else nxt[qr[i].x].push_back(i);
    }
    solve(0);
    //change(1);printf("%d",sum);
    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
    return 0;
}

T3:

将1到n*m之间的所有整数分别填入一个n*m的矩阵中，并要求其中的k个元素为局部极小值，即该元素小于周围的八个元素（如果存在），其他元素不做要求。求一共有多少种不同的矩阵，并将答案对1e9+7取模。保证一定存在合法的矩阵。

N,M<=100,K<=13

发现N*M很大而K很小,只用考虑K个标记点及其周边点即可,以下统称为关键点

记关键点数目为sum

考虑关键点的取值有A_{n*m}^{n*m-sum}种,即除关键点以外的点随便选,注意这是个排列问题

确定了关键点的值域后,考虑从小到大将值插进去,这时发现如果一个标记点没有赋值,那么它周边点必定不能赋值(把数值从小到大插入,之后必定比现在大),于是考虑状压标记点

1.这一步放一个标记点 枚举未包含在$s$的点$j$,$f[i+1][s|(2^{j-1})]+=f[i][s]

2.这一步不放标记点

预处理g[s]表示状态为s时能放的关键点(不包含标记点)的数目

设cnt表示s中有多少个1

f[i+1][s]+=f[i][s]*(g[s]-i+cnt)

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
const int maxn=110;
const int maxk=15;
const int mod=1e9+7;
int n,m,K,tot;
int dx[8]={-1,1,0,0,-1,1,-1,1},dy[8]={0,0,-1,1,-1,-1,1,1};
int g[1<<maxk],fac[maxn*maxn],inv[maxn*maxn];
int f[8*maxk][1<<maxk];
bool vis[maxn][maxn],check[maxn][maxn];
pii pt1[maxk];
vector<pii>pt2;
inline int power(int x,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(res*x)%mod;
        x=(x*x)%mod;k>>=1;
    }
    return res;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&K);
    for(int i=1;i<=K;i++)scanf("%lld%lld",&pt1[i].fir,&pt1[i].sec),check[pt1[i].fir][pt1[i].sec]=1;
    fac[0]=1;for(int i=1;i<=n*m;i++)fac[i]=(fac[i-1]*i)%mod;
    inv[n*m]=power(fac[n*m],mod-2);for(int i=n*m;i;i--)inv[i-1]=(inv[i]*i)%mod;
    for(int i=1;i<=K;i++)
    {
        int x=pt1[i].fir,y=pt1[i].sec;
        for(int j=0;j<8;j++)
        {
            int mx=x+dx[j],my=y+dy[j];
            if(mx<1||mx>n||my<1||my>m||vis[mx][my]||check[mx][my])continue;
            vis[mx][my]=1;tot++;
        }
    }
    for(int s=0;s<(1<<K);s++)
    {
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(int i=1;i<=K;i++)
        {
            if(s&(1<<(i-1)))continue;
            int x=pt1[i].fir,y=pt1[i].sec;
            for(int j=0;j<8;j++)
            {
                int mx=x+dx[j],my=y+dy[j];
                if(mx<1||mx>n||my<1||my>m||vis[mx][my]||check[mx][my])continue;
                vis[mx][my]=1;cnt++;
            }
        }
        g[s]=tot-cnt;
    }
    //printf("%lld\n",tot);
    /*for(int i=0;i<(1<<K);i++)printf("%d ",g[i]);
    puts("---");*/
    f[0][0]=1;
    for(int i=0;i<tot+K;i++)
    {
        //printf("case::%lld ",i);
        for(int s=0;s<(1<<K);s++)
        {   
            //printf("%lld ",s);
            int cnt=0;
            for(int j=1;j<=K;j++)if(!(s&(1<<(j-1))))f[i+1][s|(1<<(j-1))]=(f[i+1][s|(1<<(j-1))]+f[i][s])%mod,cnt++;
            cnt=K-cnt;
            if(g[s]-i+cnt>0)f[i+1][s]=(f[i+1][s]+(f[i][s]*(g[s]-i+cnt+mod)%mod)%mod)%mod;
        }
    }
    /*
    for(int i=0;i<=tot;i++,puts(""))
        for(int j=0;j<(1<<K);j++)
            printf("%lld ",f[i][j]);
            */
    //printf("%lld\n",f[tot][(1<<K)-1]);
    printf("%lld",((f[tot+K][(1<<K)-1]*fac[n*m])%mod*inv[tot+K])%mod);
    return 0;
}