[2017省隊模拟]填格子

題目連結

https://begin.lydsy.com/JudgeOnline/problem.php?id=3850

題解

由于相鄰顔色不能相同，是以可以将原矩陣轉化成一個序列，其中第iii個元素是第iii列三種顔色中沒有出現的那種，可以證明三種顔色隻會不出現一種。

由于一個2×22\times 22×2的矩陣中必須有所有的顔色，是以序列相鄰兩個顔色不能相同。

考慮序列中所有R所在的位置已經被确定好，那麼R将原序列分成了R−1,RR-1,RR−1,R或R+1R+1R+1段，每段都隻能交錯的填G,BG,BG,B兩種顔色。假設分成iii段的方案數為f(i)f(i)f(i)，求f(i)f(i)f(i)可以枚舉兩種顔色個數的和為偶數的段有多少段，假設為iii，則方案為

((k−i+a+b)/2−1k−1)(k(k−i−a+b)/2)((k+i+a−b)/2(k−i+a−b)/2)2i \binom{(k-i+a+b)/2-1}{k-1}\binom{k}{(k-i-a+b)/2}\binom{(k+i+a-b)/2}{(k-i+a-b)/2}2^i (k−1(k−i+a+b)/2−1​)((k−i−a+b)/2k​)((k−i+a−b)/2(k+i+a−b)/2​)2i

最終答案就是(f(R+1)+2f(R)+f(R+1))×2(f(R+1)+2f(R)+f(R+1))\times 2(f(R+1)+2f(R)+f(R+1))×2。

代碼

#include <cstdio>
#include <algorithm>

int read()
{
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
      if(ch=='-')
        {
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=1000000;
const int mod=1000000007;

int T,fac[maxn+10],ifac[maxn+10],power[maxn+10];

int C(int a,int b)
{
  if(a<b)
    {
      return 0;
    }
  if(b<0)
    {
      return 0;
    }
  return 1ll*fac[a]*ifac[a-b]%mod*ifac[b]%mod;
}

int solve(int k,int a,int b)
{
  int res=0;
  for(int i=(k+a+b)&1; i<=k; i+=2)
    {
      res=(res+1ll*C((k-i+a+b)/2-1,k-1)*C(k,(k-i-a+b)/2)%mod*C((k+i+a-b)/2,(k-i+a-b)/2)%mod*power[i])%mod;
    }
  return res;
}

int main()
{
  fac[0]=1;
  for(int i=1; i<=maxn; ++i)
    {
      fac[i]=1ll*fac[i-1]*i%mod;
    }
  ifac[0]=ifac[1]=1;
  for(int i=2; i<=maxn; ++i)
    {
      ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;
    }
  for(int i=1; i<=maxn; ++i)
    {
      ifac[i]=1ll*ifac[i-1]*ifac[i]%mod;
    }
  power[0]=1;
  for(int i=1; i<=maxn; ++i)
    {
      power[i]=power[i-1]<<1;
      if(power[i]>=mod)
        {
          power[i]-=mod;
        }
    }
  T=read();
  while(T--)
    {
      int m=read(),r=read(),g=read(),b=read();
      r=m-r;
      g=m-g;
      b=m-b;
      if((r<0)||(g<0)||(b<0))
        {
          puts("0");
          continue;
        }
      if(g<b)
        {
          std::swap(g,b);
        }
      int ans=(solve(r-1,g,b)+solve(r,g,b)*2ll+solve(r+1,g,b))*2%mod;
      printf("%d\n",ans);
    }
  return 0;
}

           

轉載于:https://www.cnblogs.com/Canopus-wym/p/10376105.html