题面

给定 $n,K$ ，满足 $K$ 是 $2$ 的幂，求
$$\sum _{K|i,0\le i\le n}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$$

对 $998244$$8$$53$ 取模。

$1\le n\le 10^{15},1\le K\le 2^{15}$ 。

题解

这题网上的题解好像很少。

LOJ 讨论区给出了常数非常大的单位根反演做法，但是正如 4 楼说的

不难发现这题答案就是 $(1+x{)}^n$ 进行长度 $K$ 的循环卷积的常数项。我们直接循环卷积加快速幂解决。

但是模数十分阴间，不可做 NTT 模数，于是又得使用任意模数NTT / MTT（那个一点五次方的万能卷积法不行，过不了）。

这次我终于学懂了，不用 __int128 了，

我们获得三个同余式子：
{ x ≡ c 1 m o d    m 1 x ≡ c 2 m o d    m 2 x ≡ c 3 m o d    m 3

⎩⎪⎨⎪⎧​x≡c1​x≡c2​x≡c3​​modm1​modm2​modm3​​

我们先合并前两个得到 $x\equiv k\mathrm{m}\mathrm{o}\mathrm{d}{m}_1{m}_2$ 。

我们令 $m_1^{\prime }$ 为 $m_1$ 取模 $m_2$ 的逆元， $m_2^{\prime }$ 为 $m_2$ 取模 $m_1$ 的逆元，

可以得到：$k=\left((c_1\cdot m_2^{\prime })\%m_1\cdot m_2+(c_2\cdot m_1^{\prime })\%m_2\cdot m_1\right)\%(m_1{m}_2)$ ，

这个过程是不会爆 $\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}$ 的。

然后令 $x=t{m}_1{m}_2+k$ ，那么
$$\begin{gathered} t{m}_1{m}_2+k\equiv c_3\mathrm{m}\mathrm{o}\mathrm{d}{m}_3 \\ \Rightarrow t\equiv (c_3-k)(m_1{m}_2{)}^{-1}\mathrm{m}\mathrm{o}\mathrm{d}{m}_3 \end{gathered}$$

我们想知道 $t{m}_1{m}_2\mathrm{m}\mathrm{o}\mathrm{d}{m}_1{m}_2{m}_3$ 的结果，只需要知道 $t\mathrm{m}\mathrm{o}\mathrm{d}{m}_3$ 的结果就行了。计算 $t$ 的过程是不爆 $\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}$ 的，也不需要龟速乘。

这时候我们只需要保证真实的 $x<m_1{m}_2{m}_3-m_1{m}_2$ ，那么计算 $t{m}_1{m}_2+k$ 得到的就是真实的 $x$ 对指定 $\mathrm{m}\mathrm{o}\mathrm{d}$ 的取模结果。

时间复杂度 $O(K\log K\log n)$ 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN (1<<16|5)
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 998244853;
const int M1 = 1012924417,R1 = 5;
const int M2 = 1007681537,R2 = 3;
const int M3 = 1004535809,R3 = 3;
int n,m,s,o,k;
inline void MD(int &x) {if(x>=MOD)x-=MOD;}
int qkpow(int a,LL b) {
	int res = 1;
	while(b > 0) {
		if(b & 1) res = res *1ll* a % MOD;
		a = a *1ll* a % MOD; b >>= 1;
	}return res;
}
int qkpow(int a,int b,int MOD) {
	int res = 1;
	while(b > 0) {
		if(b & 1) res = res *1ll* a % MOD;
		a = a *1ll* a % MOD; b >>= 1;
	}return res;
}
int om,xm[MAXN<<2];
int rev[MAXN<<2];
void NTT(int *s,int n,int op,int MOD,int R) {
	for(int i = 1;i < n;i ++) {
		rev[i] = (rev[i>>1]>>1) | ((i&1) ? (n>>1):0);
		if(rev[i] < i) swap(s[i],s[rev[i]]);
	}
	om = qkpow(R,(MOD-1)/n,MOD); xm[0] = 1;
	if(op < 0) om = qkpow(om,MOD-2,MOD);
	for(int i = 1;i < n;i ++) xm[i] = xm[i-1] *1ll* om % MOD;
	for(int k = 2,t = n>>1;k <= n;k <<= 1,t >>= 1) {
		for(int j = 0;j < n;j += k) {
			for(int i = j,l = 0;i < j+(k>>1);i ++,l += t) {
				int A = s[i],B = s[i+(k>>1)];
				s[i] = (A + xm[l]*1ll*B) % MOD;
				s[i+(k>>1)] = (A +MOD- xm[l]*1ll*B%MOD) % MOD;
			}
		}
	}
	if(op < 0) {
		int invn = qkpow(n,MOD-2,MOD);
		for(int i = 0;i < n;i ++) s[i] = s[i]*1ll*invn % MOD;
	}return ;
}
int a[MAXN<<1],b[MAXN<<1],c[MAXN<<1];
int a_[MAXN<<1],b_[MAXN<<1];
void polymul(int *A,int *B,int le) {
	for(int i = 0;i < le;i ++) a_[i] = A[i],b_[i] = B[i];
	NTT(A,le,1,M1,R1); NTT(B,le,1,M1,R1);
	for(int i = 0;i < le;i ++) a[i] = A[i]*1ll*B[i] % M1;
	for(int i = 0;i < le;i ++) A[i] = a_[i],B[i] = b_[i];
	NTT(a,le,-1,M1,R1);
	NTT(A,le,1,M2,R2); NTT(B,le,1,M2,R2);
	for(int i = 0;i < le;i ++) b[i] = A[i]*1ll*B[i] % M2;
	for(int i = 0;i < le;i ++) A[i] = a_[i],B[i] = b_[i];
	NTT(b,le,-1,M2,R2);
	NTT(A,le,1,M3,R3); NTT(B,le,1,M3,R3);
	for(int i = 0;i < le;i ++) c[i] = A[i]*1ll*B[i] % M3;
	for(int i = 0;i < le;i ++) A[i] = a_[i],B[i] = b_[i];
	NTT(c,le,-1,M3,R3);
	int v1 = qkpow(M2,M1-2,M1);
	int v2 = qkpow(M1,M2-2,M2);
	int v3 = qkpow(M1*1ll*M2%M3,M3-2,M3);
	LL MD = M1*1ll*M2;
	for(int i = 0;i < le;i ++) {
		LL k = (v1*1ll*a[i]%M1*M2 + v2*1ll*b[i]%M2*M1) % MD;
		int t = (c[i]+M3-k%M3) % M3 *1ll* v3 % M3;
		A[i] = (MD % MOD * t % MOD + k) % MOD;
	}
	return ;
}
void polymuls(int *A,int le) {
	for(int i = 0;i < le;i ++) a_[i] = A[i];
	NTT(A,le,1,M1,R1);
	for(int i = 0;i < le;i ++) a[i] = A[i]*1ll*A[i] % M1;
	for(int i = 0;i < le;i ++) A[i] = a_[i];
	NTT(a,le,-1,M1,R1);
	NTT(A,le,1,M2,R2);
	for(int i = 0;i < le;i ++) b[i] = A[i]*1ll*A[i] % M2;
	for(int i = 0;i < le;i ++) A[i] = a_[i];
	NTT(b,le,-1,M2,R2);
	NTT(A,le,1,M3,R3);
	for(int i = 0;i < le;i ++) c[i] = A[i]*1ll*A[i] % M3;
	for(int i = 0;i < le;i ++) A[i] = a_[i];
	NTT(c,le,-1,M3,R3);
	int v1 = qkpow(M2,M1-2,M1);
	int v2 = qkpow(M1,M2-2,M2);
	int v3 = qkpow(M1*1ll*M2%M3,M3-2,M3);
	LL MD = M1*1ll*M2;
	for(int i = 0;i < le;i ++) {
		LL k = (v1*1ll*a[i]%M1*M2 + v2*1ll*b[i]%M2*M1) % MD;
		int t = (c[i]+M3-k%M3) % M3 *1ll* v3 % M3;
		A[i] = (MD % MOD * t % MOD + k) % MOD;
	}
	return ;
}
int A[MAXN],B[MAXN],C[MAXN];
int main() {
	LL N = read(); m = read();
	if(m == 1) {
		return AIput(qkpow(2,N),'\n'),0;
	}
	C[0] = 1; A[0] = 1; A[1] = 1;
	while(N > 0) {
		if(N & 1) {
			polymul(C,A,m);
		}
		for(int i = 0;i < m;i ++) B[i] = A[i];
		polymuls(A,m);
		N >>= 1;
	}
	AIput(C[0],'\n');
	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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163