Educational Codeforces Round 138 (Rated for Div. 2) D

Educational Codeforces Round 138 (Rated for Div. 2)

D. Counting Arrays

题意

给定长度为$n$的数组$a$，若$gcd(ai,i)=1$（元素与其下标互质）则可以删除$ai$，其后的元素顺序前移直到数组为空。将删除的元素的下标按删除顺序排成一列这就是删除序列$b$。当数组$a$具有两种及以上的不同删除序列时，称数组$a$具有二重性。
求长度为$1$~$n$的数组 ，数组元素$1<=ai<=m$，有多少数组具有二重性。

分析

首先题目询问的是长度分别为$1,2,3,\dots \dots ，n$的数组，而不只是长度为$n$的数组，比赛时样例的26我死活算不出来 。
因为数字$1$与所有数都互质$gcd(1,x)=1$ 所以很容易想到所有的数组都至少有一种删除序列即$b=(1,1,1，\dots \dots ，1)$，所以我们只需要再找到一种删除方式就可以构造出二重性。
求二重性的个数发现有困难，但是正难则反，我们可以考虑求出所有方案$sum$ - 没有二重性的数组数量$res$。

开始求不具有二重性的数组数量，即我们需要构造出删除序列只有$1$的数组。考虑初始数组元素$ai$，要让删除序列全为$1$那么不仅所有的$gcd(ai,i)!=1$ 并且在删除过程中$ai$在向前移动过程中也要保持$gcd(ai,j)!=1(2<=j<=i)$ ，也就是说$ai$的质因数要包含$2$~$i$之间所有的质数 ，而$m$最大为$10^{12}$最多包含十几个质因子,也就是说当数组长度大于一定以后(大概$40$),就不可能有不具有二重性的数组了。

最后我们可以递推的方式求解，然后用累加的方法解决数组长度为$1$~$n$的问题。

代码

#include 
#include 
using namespace std;
#define ll long long
const int N = 3e5 + 10, mod = 998244353;
ll n,m,p[50] = {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0,0,0,23,0,0,0,0,0,29,0,31,0,0,0,0,0,37,41,43,47};//50以内的质数
int main()
{
    cin >> n >> m;
    ll sum = 0, sum1 = 1;
    for(int i = 1; i <= n; i ++){
        sum1 = sum1 * (m % mod) % mod;//sum1是长度为i的数组的总方案
        sum = (sum + sum1) % mod;//sum是累加结果
    }
    ll res = m % mod, res1 = m % mod, k = 1;
    for(int i = 2; i <= n; i ++){
        if(p[i]){
            if(k * i <= m) k = k * i;
            else break;
        }
        res1 = res1 * (m / k % mod) % mod;//res1是长度为i的数组没有二重性的总方案
        res = (res + res1) % mod;//res是累加结果
    }
    printf("%lld\n",(sum + mod - res) % mod);//sum - res为结果
    return 0;
}
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

更新：
D题10.21，E题待更新。