给定序列
大概是一道没有什么高端的算法,仅靠推式子的难度评黑的题。
首先我们不难想到,如果设当前计数器的值为
然后不太严谨地思考一下不难发现,我们每次是使除了选择的其它的计数器都加一,所以拖后腿的一定是
于是此时不难想到一个较为简单的状态:令
显然
转化一下:
现在不难发现即较小的都在左侧,较大的都在右侧,不过这个转移仍然不行,也就是我们是已知
考虑令
显然
类比一下之前的推出来:
显然:
不难发现对于固定的
对于
xxxxxxxxxx
891
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27struct Matrix2{
28 ll v00, v01, v10, v11;
29 friend Matrix2 operator * (const Matrix2 &a, const Matrix2 &b){
30 return Matrix2{
31 (a.v00 * b.v00 % MOD + a.v01 * b.v10 % MOD) % MOD,
32 (a.v00 * b.v01 % MOD + a.v01 * b.v11 % MOD) % MOD,
33 (a.v10 * b.v00 % MOD + a.v11 * b.v10 % MOD) % MOD,
34 (a.v10 * b.v01 % MOD + a.v11 * b.v11 % MOD) % MOD
35 };
36 }
37};
38Matrix2 base{1, 0, 0, 1};
39
40ll qpow(ll a, ll b){
41 ll ret(1), mul(a);
42 while(b){
43 if(b & 1)ret = ret * mul % MOD;
44 b >>= 1;
45 mul = mul * mul % MOD;
46 }return ret;
47}
48ll inv(ll v){return qpow(v, MOD - 2);}
49Matrix2 qpow(Matrix2 a, ll b){
50 Matrix2 ret(base), mul(a);
51 while(b){
52 if(b & 1)ret = ret * mul;
53 b >>= 1;
54 mul = mul * mul;
55 }return ret;
56}
57
58int N;
59ll A[210000];
60
61int main(){
62 N = read();
63 for(int i = 1; i <= N; ++i)A[i] = read < ll >();
64 Matrix2 ans{0, 1, 0, 0};
65 ll cur(0);
66 for(int i = N - 1; i >= 1; --i){
67 ll B = N * inv(i) % MOD, C = (N - cur) * inv(i) % MOD;
68 ans = ans * qpow(Matrix2{B, 0, C, 1}, A[i + 1] - A[i]);
69 (cur += ans.v00) %= MOD;
70 }printf("%lld\n", (ans.v00 % MOD + MOD) % MOD);
71 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72 return 0;
73}
74
75template < typename T >
76inline T read(void){
77 T ret(0);
78 int flag(1);
79 char c = getchar();
80 while(c != '-' && !isdigit(c))c = getchar();
81 if(c == '-')flag = -1, c = getchar();
82 while(isdigit(c)){
83 ret *= 10;
84 ret += int(c - '0');
85 c = getchar();
86 }
87 ret *= flag;
88 return ret;
89}
update-2023_01_27 初稿