RepeatedApplication
SRM 852 · 2024-01-23 · by misof
Problem Statement
Given is a positive integer N.
Let S = { 0, 1, ..., N-1 }. All functions in this problem are functions defined on the set S with values from the set S.
Let f[t](x) denote the function f applied t times to the input x. In other words, f[1](x) is simply f(x), f[2](x) is f(f(x)), and so on.
Formally, f[0](x) = x and for all t, f[t+1](x) = f( f[t](x) ).
In addition to N, you are given another positive integer K. We are now interested in functions with the following property:
for all x in S: x + f[K](x) = N - 1
Count all such functions. Return their count modulo 10^9 + 7.
Notes
- The total number of functions on S is finite, so the return value is always well-defined.
Constraints
- N will be between 1 and 2,000, inclusive.
- K will be between 1 and 2,000, inclusive.
42 1 Returns: 1
There is clearly exactly one function f such that for all x from 0 to 41, inclusive, x + f(x) = 41.
2 4 Returns: 0
For N = 2 we have S = {0, 1}. There are only four functions on this S: we have two options for the value of f(0) and two for the value of f(1). We can easily verify that none of the four functions have the desired property.
5 2 Returns: 2
One of the two functions that have the desired property has the following values: f(0)=1, f(1)=4, f(2)=2, f(3)=0, and f(4)=3. We can easily verify that: 0 + f(f(0)) = 0 + f(1) = 0 + 4 = 4. 1 + f(f(1)) = 1 + f(4) = 1 + 3 = 4. 2 + f(f(2)) = 2 + f(2) = 2 + 2 = 4. 3 + f(f(3)) = 3 + f(0) = 3 + 1 = 4. 4 + f(f(4)) = 4 + f(3) = 4 + 0 = 4.
7 4 Returns: 0
8 4 Returns: 48
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RepeatedApplication with a public method int count(int N, int K) · 84 test cases · 2 s / 256 MB per case