题目传送门

虽然这是一道容斥水题,但我还是看了题解才写出来的。。。

题意:在一个 N*M 的矩阵中摆放 K 只石子,要求第一行、第一列、第M 行、第 N 列必须有石子,求方案总数。

分析:

只需要大力容斥一波就好了。。。火狐截图_2018-07-27T01-38-47.248Z

(Menci博客里的说,Menci博客

代码:

 

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+10;
const LL mod=1e6+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T,n,m,k;
int combo[500][500];
void init()
{
    combo[1][1]=combo[1][0]=1;
    for(int i=2;i<=410;i++)
    {
        combo[i][0]=combo[i][i]=1;
        for(int j=1;j<i;j++)
            combo[i][j]=(combo[i-1][j-1]+combo[i-1][j])%mod;
    }
}
void solve(int cas)
{
    long long ans=combo[n*m][k];
    
    ans-=2*combo[(n-1)*m][k];ans=(ans+mod)%mod;
    ans-=2*combo[n*(m-1)][k];ans=(ans+mod)%mod;

    ans+=combo[(n-2)*m][k];
    ans+=combo[n*(m-2)][k];
    ans+=combo[(n-1)*(m-1)][k]*4;

    ans-=2*combo[(n-2)*(m-1)][k];ans=(ans+mod)%mod;
    ans-=2*combo[(n-1)*(m-2)][k];ans=(ans+mod)%mod;

    ans+=combo[(n-2)*(m-2)][k];ans=(ans+mod)%mod;
    printf("Case %d: %lld\n",cas,ans);
}
main()
{
    init();
    read(T);
    for(int cas=1;cas<=T;cas++)
    {
        read(n),read(m),read(k);
        if(k==0){printf("Case %d: 0\n",cas);continue;}
        solve(cas);
    }
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注