Project Euler 743

题目

Window into a Matrix

A window into a matrix is a contiguous sub matrix.

Consider a $2\times n$ matrix where every entry is either $0$ or $1$.

Let $A(k,n)$ be the total number of these matrices such that the sum of the entries in every $2\times k$ window is $k$.

You are given that $A(3,9) = 560$ and $A(4,20) = 1060870$.

Find $A(10^8,10^{16})$. Give your answer modulo $1\,000\,000\,007$.

解决方案

本方案只适用于$k\mid n$的情况。

不难发现，对于$1\le i\le k$，第$i,i+k,i+2k,i+3k,\dots$列中，$1$的个数是相同的。

因此可以只考虑前$k$列的情况。

由于前$2\times k$个格子中，只有$k$个为$1$，因此最多只有$\left\lfloor\dfrac{k}{2}\right\rfloor$列是拥有两个$1$。剩下的$1$中，都被分配到了一个$1$的列。

枚举前$k$个格子中填充两个$1$的列的个数，那么答案为：

$$A(k,n)=\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\frac{k!}{(n-2i)!(i!)^2}2^{\frac{n}{k}\cdot(k-2i)}$$

如果有$i$列有两个$1$，那么有$i$列没有$1$，有$k-2i$只有一个$1$。那么，$1$的分配方式就有$\dbinom{k}{i}\cdot\dbinom{k-i}{i}=\dfrac{k!}{(n-2i)!(i!)^2}$种。整个$2\times n$的格子中，有$\dfrac{n}{k}\cdot(k-2i)$列是只有一个$1$的，每一列有$2$种填法，由此得到$2^{\frac{n}{k}\cdot(k-2i)}$。最终通过组合得到上式。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N = 1e16;
const ll K = 1e8;
const ll B = N/K;
ll mod=1e9+7;
ll qpow(ll n,ll m,ll mod){
    ll ans=1;
    for(;m;m>>=1){
        if(m&1) ans=ans*n%mod;
        n=n*n%mod;
    }
    return ans;
}
ll inv(ll n,ll p){
    return qpow(n,p-2,p);
}
int fac[K + 4],finv[K + 4];
int main(){
    fac[0]=fac[1]=1;
    finv[0]=1;
    for(int i=2; i <= K; i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    finv[K]=inv(fac[K], mod);
    for(int i= K - 1; i > 0; i--)
        finv[i]=1ll*finv[i+1]*(i+1)%mod;
    ll pw2B=qpow(2,B,mod);
    ll invpw4B=inv(pw2B*pw2B%mod,mod);
    ll now=qpow(2,N,mod);
    ll ans=0;
    for(int i=0;i<=K/2;i++){
        ans=(ans+1ll*fac[K]*finv[K-2*i]%mod*finv[i]%mod*finv[i]%mod*now)%mod;
        now=now*invpw4B%mod;
    }
    printf("%lld\n",ans);
}