Similar Polynomials (Codeforces 1817C)
Tags: Math, combinatorics

A polynomial $$$A(x)$$$ of degree $$$d$$$ is an expression of the form $$$A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$$$, where $$$a_i$$$ are integers, and $$$a_d \neq 0$$$. Two polynomials $$$A(x)$$$ and $$$B(x)$$$ are called similar if there is an integer $$$s$$$ such that for any integer $$$x$$$ it holds that$$$$$$ B(x) \equiv A(x+s) \pmod{10^9+7}. $$$$$$For two similar polynomials $$$A(x)$$$ and $$$B(x)$$$ of degree $$$d$$$, you're given their values in the points $$$x=0,1,\dots, d$$$ modulo $$$10^9+7$$$.Find a value $$$s$$$ such that $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ for all integers $$$x$$$.

Input: The first line contains a single integer $$$d$$$ ($$$1 \le d \le 2\,500\,000$$$).The second line contains $$$d+1$$$ integers $$$A(0), A(1), \ldots, A(d)$$$ ($$$0 \le A(i) < 10^9+7$$$) — the values of the polynomial $$$A(x)$$$.The third line contains $$$d+1$$$ integers $$$B(0), B(1), \ldots, B(d)$$$ ($$$0 \le B(i) < 10^9+7$$$) — the values of the polynomial $$$B(x)$$$.It is guaranteed that $$$A(x)$$$ and $$$B(x)$$$ are similar and that the leading coefficients (i.e., the coefficients in front of $$$x^d$$$) of $$$A(x)$$$ and $$$B(x)$$$ are not divisible by $$$10^9+7$$$.

Output: Print a single integer $$$s$$$ ($$$0 \leq s < 10^9+7$$$) such that $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ for all integers $$$x$$$.If there are multiple solutions, print any.

Note: In the first example, $$$A(x) \equiv x-1 \pmod{10^9+7}$$$ and $$$B(x)\equiv x+2 \pmod{10^9+7}$$$. They're similar because $$$$$$B(x) \equiv A(x+3) \pmod{10^9+7}.$$$$$$In the second example, $$$A(x) \equiv (x+1)^2 \pmod{10^9+7}$$$ and $$$B(x) \equiv (x+10)^2 \pmod{10^9+7}$$$, hence $$$$$$B(x) \equiv A(x+9) \pmod{10^9+7}.$$$$$$

Sample Inputs:
1
1000000006 0
2 3

2
1 4 9
100 121 144

Sample Outputs:
3

9

Solution (Python):
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from typing import *
input = sys.stdin.readline

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
input = sys.stdin.readline

class Factorial:

    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod
(_index, _sep, buffer) = (0, True, [])

def read_int():
    global _index, buffer, _sep
    if _index >= len(buffer) - 1 + _sep:
        try:
            s = '' if _sep else buffer[-1]
            s += sys.stdin.readline(4096)
            _sep = s[-1].isspace()
            buffer = s.split()
        except:
            pass
        _index = 0
    _index += 1
    return int(buffer[_index - 1])
d = II()
mod = 10 ** 9 + 7
fact = Factorial(10 ** 5 * 25, mod)
(x1, x2) = (0, 0)
for i in range(d + 1):
    val = read_int()
    if i % 2 == 0:
        if i < d:
            x1 += fact.comb(d - 1, i) * val
        x2 += fact.comb(d, i) * val
    else:
        if i < d:
            x1 -= fact.comb(d - 1, i) * val
        x2 -= fact.comb(d, i) * val
    x1 %= mod
    x2 %= mod
y1 = 0
for i in range(d):
    val = read_int()
    if i < d:
        if i % 2 == 0:
            y1 += fact.comb(d - 1, i) * val
        else:
            y1 -= fact.comb(d - 1, i) * val
diff = (x1 - y1) % mod
print(diff * pow(x2, mod - 2, mod) % mod)

Solution (Python):
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from typing import *
input = sys.stdin.readline

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
input = sys.stdin.readline

class Factorial:

    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod
(_index, _sep, buffer) = (1, False, [''])

def read_int():
    global _index, buffer, _sep
    if _index < len(buffer) - 1 or (_sep and _index < len(buffer)):
        _index += 1
        return int(buffer[_index - 1])
    else:
        try:
            s = '' if _sep else buffer[-1]
            s += sys.stdin.readline(4096)
            _sep = not s[-1].isdigit()
            buffer = s.split()
        except:
            pass
        _index = 0
    _index += 1
    return int(buffer[_index - 1])
d = II()
mod = 10 ** 9 + 7
fact = Factorial(10 ** 5 * 25, mod)
(x1, x2) = (0, 0)
for i in range(d + 1):
    val = read_int()
    if i % 2 == 0:
        if i < d:
            x1 += fact.comb(d - 1, i) * val
        x2 += fact.comb(d, i) * val
    else:
        if i < d:
            x1 -= fact.comb(d - 1, i) * val
        x2 -= fact.comb(d, i) * val
    x1 %= mod
    x2 %= mod
y1 = 0
for i in range(d):
    val = read_int()
    if i < d:
        if i % 2 == 0:
            y1 += fact.comb(d - 1, i) * val
        else:
            y1 -= fact.comb(d - 1, i) * val
diff = (x1 - y1) % mod
print(diff * pow(x2, mod - 2, mod) % mod)

Solution (Python):
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from typing import *
input = sys.stdin.readline

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
input = sys.stdin.readline

class Factorial:

    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        if n < m or m < 0 or n < 0:
            return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod
(_index, _sep, buffer) = (1, False, [''])

def read_int():
    global _index, buffer, _sep
    if _index < len(buffer) - 1 or (_sep and _index < len(buffer)):
        _index += 1
        return int(buffer[_index - 1])
    else:
        try:
            s = '' if _sep else buffer[-1]
            s += sys.stdin.readline(8192)
            _sep = not s[-1].isdigit()
            buffer = s.split()
        except:
            pass
        _index = 0
    _index += 1
    return int(buffer[_index - 1])
d = II()
mod = 10 ** 9 + 7
fact = Factorial(10 ** 5 * 25, mod)
(x1, x2) = (0, 0)
for i in range(d + 1):
    val = read_int()
    if i % 2 == 0:
        if i < d:
            x1 += fact.comb(d - 1, i) * val
        x2 += fact.comb(d, i) * val
    else:
        if i < d:
            x1 -= fact.comb(d - 1, i) * val
        x2 -= fact.comb(d, i) * val
    x1 %= mod
    x2 %= mod
y1 = 0
for i in range(d):
    val = read_int()
    if i < d:
        if i % 2 == 0:
            y1 += fact.comb(d - 1, i) * val
        else:
            y1 -= fact.comb(d - 1, i) * val
diff = (x1 - y1) % mod
print(diff * pow(x2, mod - 2, mod) % mod)