3652.特征值
2026-09-28
题解
发现 a 数组的价值只与其和有关,考虑用同余进行刻画,也就是 min(S(a)modm,m−S(a)modm)。
在 a 上的连续子数组怎么维护?考虑前缀和,令 pi=∑j=1iaj,则 a[l,r]=min((pr−pl−1)modm,(pl−1−pr)modm)。
发现这个东西可以放到 m 的同余环上,那么 a 的特征值即为圆上距离最近的点距离的 k 次方。
由于在同余环上,这个最短距离一定不大于 n+1m,也就是直接枚举最近距离复杂度为 O(nm),而需要求出所有 n 的答案,总复杂度为 O(Tmlogm)。
设当前枚举最短距离为 z,可以分配的距离为 m−(n+1)z,根据插板法得到方案数为 Am−(n+1)z+nn,根据容斥可以得到其系数为 zk−(z−1)k。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , out[SIZE] , *p1=in , *p2=in , *p3=out;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#define flush() (fwrite(out,1,p3-out,stdout) , p3=out)
#define putchar(c) (p3==out+SIZE && flush() , *p3 ++ = c)
class Flush{public: ~Flush(){flush();} } ___;
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(int x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[30] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef flush
#undef putchar
#undef SIZE
#endif
} using namespace IO;
const int M = 2e5+10;
const int MOD = 998244353;
inline int qpow(int a , int b) {
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD; b >>= 1;
}
return res;
}
inline void Add(int& a , int b) {
a += b;
if(a >= MOD) a -= MOD;
}
int m , k;
bitset<M> nprime;
int primes[M] , cnt;
int p[M];
int fac[M] , inv[M];
inline int A(int a , int b) {
if(b > a) return 0;
return 1ll * fac[a] * inv[a-b] % MOD;
}
void solve() {
m = read(); k = read();
nprime.reset(); cnt = 0;
p[1] = 1;
for(int i = 2 ; i <= m ; i ++) {
if(!nprime[i]) {
primes[++ cnt] = i;
p[i] = qpow(i , k);
}
for(int j = 1 ; j <= cnt && 1ll * i * primes[j] <= m ; j ++) {
nprime[i*primes[j]] = true;
p[i*primes[j]] = 1ll * p[i] * p[primes[j]] % MOD;
if(i % primes[j] == 0) break;
}
}
for(int n = 1 ; n < m ; n ++) {
int ans = 0;
for(int z = 1 , t = n+1 , md = m/(n+1) ; z <= md ; z ++ , t += n+1) {
Add(ans , 1ll * A(m-t+n,n) * (p[z]-p[z-1]+MOD) % MOD);
}
write(ans,n==m-1);
}
}
int main() {
fac[0] = 1;
for(int i = 1 ; i < M ; i ++) fac[i] = 1ll * fac[i-1] * i % MOD;
inv[M-1] = qpow(fac[M-1] , MOD-2);
for(int i = M-1 ; i >= 1 ; i --) inv[i-1] = 1ll * inv[i] * i % MOD;
int T = read();
while(T --) solve();
return 0;
}