Project Euler 657

题目

Incomplete words

In the context of formal languages, any finite sequence of letters of a given alphabet $\Sigma$ is called a word over $\Sigma$. We call a word incomplete if it does not contain every letter of $\Sigma$.

For example, using the alphabet $\Sigma={ a, b, c}$, ‘$ab$’, ‘$abab$’ and ‘$\,$’ (the empty word) are incomplete words over $\Sigma$, while ‘$abac$’ is a complete word over $\Sigma$.

Given an alphabet $\Sigma$ of $\alpha$ letters, we define $I(\alpha,n)$ to be the number of incomplete words over $\Sigma$ with a length not exceeding $n$.

For example, $I(3,0)=1$, $I(3,2)=13$ and $I(3,4)=79$.

Find $I(10^7,10^{12})$. Give your answer modulo $1\,000\,000\,007$.

解决方案

令$N=10^7,M=10^{12}$。考虑使用容斥原理解决本题。

如果当前只使用其中$i$个字母，那么单词的数量个数$f_{N,M}(i)$如下：

$$f_{N,M}(i)=\dbinom{N}{i}\sum_{j=0}^{M} i^j$$

这是一个很明显的等比数列求和式，但是当$i=1$时，式子不适用等比数列求和公式，因此化简成$N\cdot (M+1)$，否则可以化简成$\dbinom{N}{i}\cdot \dfrac{i^{M+1}-1}{i-1}$。

注意到$f{N,M}(N-1)$中的一些单词实际上有单词使用了$N-2$个字母，因此需要减去$f{N,M}(N-2)$的情况，而使用$N-3$个字母的单词被重复减去了，需要加上……

最终，$I$可以写成：

$$I(N,M)=\sum_{i=0}^{N-1}(-1)^{N-1-i}\cdot f_{N,M}(i)$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000000;
const ll M=1000000000000;
ll mod=1000000007;
ll fac[N+4],inv[N+4],finv[N+4];
ll C(int n,int m){
    return fac[n]*finv[n-m]%mod*finv[m]%mod;
}
ll qpow(ll n,ll m){
    m%=mod-1;
    ll a=1;
    for(;m;m>>=1){
        if(m&1) a=a*n%mod;
        n=n*n%mod;
    }
    return a;
}
int main(){
    fac[0]=fac[1]=inv[1]=finv[0]=finv[1]=1;
    for(int i=2;i<=N;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
    ll ans=0;
    for(int i=N-1,f=1;i>=0;i--,f=-f){
        if(i==0) ans+=f;
        else if(i==1) ans+=(M+1)%mod*N%mod*f;
        else ans+=C(N,i)*(qpow(i,M+1)-1)%mod*inv[i-1]%mod*f;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}