Codeforces 1106 F Lunar New Year and a Recursive Sequence | BSGS / exgcd / 행렬 곱셈
고 3 은퇴 선수 들 이 천리 와 김 시험지 CF 를 가까스로 포기 하고 결국 shi 처럼......................................................................한 학기 동안 코드 를 두 드 리 지 않 아서 정말 잊 어 버 렸 어 요.
시험 문 제 는 역시 정정 해 야 한다.
P. S. 이 알고리즘 들 은 하나 로 생각 이 안 나 요. TAT.
제목 링크
Codeforces 1106 F Lunar New Year and a Recursive Sequence 새해 및 전달 수열
제목 설명
어떤 수열 \ (\ {f i \} \ \) 전달 공식: \ [f i = (\ prod {j = 1} ^ kf {i - j} ^ {b j}) \ bmod p \]
그 중 \ (b \) 는 알려 진 길이 가 \ (k \) 인 수열, \ (p = 998244353 \), \ (f 1 = f 2 =... = f {k - 1} = 1 \), \ (f k \) 알 수 없습니다.
두 개의 수 를 드 립 니 다.
\(k \le 100, n \le 10^9\)
해제
수론정말 머리 가 벗 겨 진다!
우선 이 데이터 범 위 는 무엇 을 생각 나 게 합 니까?행렬 곱셈!
행렬 곱셈 이 이것 을 모두 곱셈 과 곱셈 의 전달 수열 로 미 루 려 면 어떻게 합 니까?숫자 를 맞 춰 라!이산 대수!
그래서 이 문제 의 관건 적 인 두 개의 시험 점 이 너 에 게 발견 되 었 다!
(그러나 나 는 너무 요리 해서 발견 할 수 없다 =)
이산 대수 란 무엇 입 니까?
모두 가 알다 시 피 (대중 = = NTT 를 배 운 사람 등) 이 즐겨 듣 는 계수 \ (p = 998244353 \) 는 원래 뿌리 \ (g = 3 \) 가 있 고 \ (g ^ i (0 \ le i < P - 1) \) 와 \ (1 \ le x < P \) 가 일일이 대응한다.그러면 우리 가 배 운 대 수 를 비교 해서 이 \ (i \) 를 \ (x \) 의 이산 대수 라 고 부른다.
수열 (h i \) 을 \ (f i \) 의 이산 대수 로 합 니 다.
그러면 전달 식: \ \ [h i = (\ sum {j = 1} ^ kb j \ cdot h {i - j}) \ bmod (p - 1) \ \]
그 중 에 (h 1 = h 2 =... = h {k - 1} = 0 \)주의 모드 가 \ (p - 1 \) 로 바 뀌 었 습 니 다.
이거 매트릭스 로 가속 할 수 있어!만약 우리 가 \ (h k \) 를 1 로 설정 하여 가지 고 들 어가 서 \ (h n = c \) 를 구한다 면 \ (h n = c \ cdot h k \ bmod (p - 1) \ 가 있다.
\ (h n \) 는 \ (m \) 의 이산 대수 로 BSGS 로 구 할 수 있 습 니 다.
exgcd 는 방금 이 동 여 방정식 을 풀 면 \ (h k \) 를 얻 을 수 있 습 니 다.
\ (f k = g ^ {h k} \), 빠 른 멱 으로 \ (f k \) 를 얻 을 수 있 습 니 다.
exgcd 가 풀 리 지 않 은 것 을 발견 하면 출력 - 1.
생각 이 되 게 또렷 하지 않 아 요?
코드
#include
#include
#include
#include
#include
#include
#define space putchar(' ')
#define enter putchar('
')
using namespace std;
typedef long long ll;
template
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 102, P = 998244353, P2 = 998244352, G = 3;
int K;
ll b[N], n, m, C;
namespace BSGS {
const int S = 32000, M = 2000000;
int cnt = 0, adj[M + 5], nxt[S + 5];
ll key[S + 5], val[S + 5];
void insert(ll K, ll V){
int p = K % M;
key[++cnt] = K;
val[cnt] = V;
nxt[cnt] = adj[p];
adj[p] = cnt;
}
ll search(ll K){
for(int u = adj[K % M]; u; u = nxt[u])
if(key[u] == K) return val[u];
return -1;
}
void init(){
ll sum = 1;
for(int i = 1; i <= S; i++)
sum = sum * G % P;
ll tot = 1;
for(int i = 1; (i - 1) * S < P - 1; i++)
tot = tot * sum % P, insert(tot, i * S);
}
ll log(ll x){
ll sum = 1, ret;
for(int i = 1; i <= S; i++){
sum = sum * G % P;
ret = search(sum * x % P);
if(~ret && ret < P - 1) return ret - i;
}
assert(0);
return -1;
}
}
struct matrix {
ll g[N][N];
matrix(){
memset(g, 0, sizeof(g));
}
matrix(int x){
memset(g, 0, sizeof(g));
for(int i = 1; i <= K; i++)
g[i][i] = 1;
}
matrix operator * (const matrix &b){
matrix c;
for(int i = 1; i <= K; i++)
for(int j = 1; j <= K; j++)
for(int k = 1; k <= K; k++)
c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j]) % P2;
return c;
}
};
ll qpow(ll a, ll x){
ll ret = 1;
while(x){
if(x & 1) ret = ret * a % P;
a = a * a % P;
x >>= 1;
}
return ret;
}
matrix qpow(matrix a, ll x){
matrix ret(1);
while(x){
if(x & 1) ret = ret * a;
a = a * a;
x >>= 1;
}
return ret;
}
ll calcC(){
matrix ret, op;
ret.g[K][1] = 1;
for(int i = 1; i < K; i++)
op.g[i][i + 1] = 1;
for(int i = 1; i <= K; i++)
op.g[K][i] = b[K - i + 1];
ret = qpow(op, n - K) * ret;
return ret.g[K][1];
}
void exgcd(ll a, ll b, ll &g, ll &x, ll &y){
if(!b) return (void)(x = 1, y = 0, g = a);
exgcd(b, a % b, g, y, x);
y -= x * (a / b);
}
ll solve(ll A, ll B){ //Ax % P2 == B, solve x
ll a = A, b = P2, g, x, y;
exgcd(a, b, g, x, y);
if(B % g) return -1;
x *= B / g, y *= B / g;
ll t = b / g;
x = (x % t + t) % t;
return x;
}
int main(){
BSGS::init();
read(K);
for(int i = 1; i <= K; i++) read(b[i]);
read(n), read(m);
C = calcC();
m = BSGS::log(m);
ll ans = solve(C, m);
if(ans == -1) puts("-1");
else write(qpow(G, ans)), enter;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.