Project Euler 511

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

Project Euler 511

题目

Sequences with nice divisibility properties

Let $\text{Seq}(n,k)$ be the number of positive-integer sequences ${ai}{1\le i\le n}$ of length $n$ such that:

  • $n$ is divisible by $a_i$ for $1\le i\le n$, and
  • $n + a_1 + a_2 + \dots + a_n$ is divisible by $k$.

Examples:
$\text{Seq}(3,4) = 4$, and the $4$ sequences are:

$\begin{aligned}
{1, 1, 3} \
{1, 3, 1} \
{3, 1, 1} \
{3, 3, 3}
\end{aligned}$

$\text{Seq}(4,11) = 8$, and the $8$ sequences are:

$\begin{aligned}
{1, 1, 1, 4}\
{1, 1, 4, 1}\
{1, 4, 1, 1}\
{4, 1, 1, 1}\
{2, 2, 2, 1}\
{2, 2, 1, 2}\
{2, 1, 2, 2}\
{1, 2, 2, 2}\
\end{aligned}$

The last nine digits of $\text{Seq}(1111,24)$ are $840643584$.

Find the last nine digits of $\text{Seq}(1234567898765,4321)$.

解决方案

注意到第$2$个条件中的式子可以看成是$(a_1+1)+(a_2+1)+\dots+(a_n+1)$。因此在第$1$个条件时，处理完$n$的所有因子后，全部加$1$，那么第$2$个条件就可以转化成条件$a_1’+a_2’+\dots+a_n’$是$k$的倍数。

假设$S$是经过第$1$个条件的限定后，可以填入序列$a’$的数的集合。

那么，不难想到使用动态规划来解决本题。令$N=1234567898765,M=4321$。假设状态$f(i,j)(0\le i\le N,0<j<M)$是长度为$n$的序列中，有多少种填法使得序列$a’$的元素之和模$M$为$j$。那么不难写出状态转移方程为：

但是，对于$N$这种数据范围而言，直接进行转移效率非常低。如果直接使用矩阵快速幂，那么矩阵的边长长达$M$，仍然不可接受。

如果我们已经求出了长度为$a$的序列的各种填法$f(a,\cdot)$和长度为$b$的各种填法$f(b,\cdot)$，不难知道我们可以通过$O(M^2)$的时间复杂度组合出$f(a+b,\cdot)$。

枚举所有的$f(a,i)$和$f(b,j)$，将这两部分值直接合并起来：

$f(a,i)\cdot f(b,j)\rightarrow f(a+b,(i+j)\%M)$

因此，这给了我们一个方案：依次求出$f(2^0,\cdot),f(2^1,\cdot),f(2^2,\cdot),\dots$。然后针对$N$，选择这些求出的$f(2^i,\cdot)$进行合并即可。这种做法的时间复杂度为$O(M^2\cdot \log N)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1234567898765,M=4321;
ll mod=1e9;
ll cnt[M];
ll a[M],b[M];
void getd(ll N){
    for(ll i=1;i*i<=N;i++)
    if(N%i==0){
        ++cnt[(i+1)%M];
        if(i*i!=N) ++cnt[(N/i+1)%M];
    }
}
void cal(ll a[M],ll b[M],ll ans[M]){
    ll c[M]={0};
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            c[(i+j)%M]=(c[(i+j)%M]+a[i]*b[j])%mod;
    memcpy(ans,c,sizeof(c));
}
int main(){
    getd(N);
    a[0]=1;
    memcpy(b,cnt,sizeof(b));
    for(ll M=N;M;M>>=1){
        if(M&1) cal(a,b,a);
        cal(b,b,b);
    }
    printf("%lld\n",a[0]);
}