1678.md (36699B)
1 Source: https://codeforces.com/blog/entry/102631 2 3 [1678A - Tokitsukaze и полная нулевая последовательность](/contest/1678/problem/A "Codeforces Round 789 (Div. 2)") 4 5 Idea: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze") 6 Prepare: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze") 7 8 **Tutorial** 9 10 We observe that when there is $0$ in the sequence, it is optimal to choose $0$ and any number other than $0$ for each operation. 11 12 Therefore, when there is $0$ in the sequence, let $cnt$ be the number of $0$s, the answer is $n - cnt$. 13 14 Otherwise, when $0$ does not exist in the sequence, there are two situations: 15 16 1. When there exist two equal numbers in the sequence, we can perform the operation $1$ time to convert it into the situation of having $0$ in the sequence. So the answer must be $n$. 17 2. When all numbers in the sequence are distinct, we can perform the operation $2$ times to convert it into the situation of having $0$ in the sequence. So the answer must be $n + 1$. 18 19 **Solution** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 25 int main(){ 26 int t; 27 scanf("%i",&t); 28 while(t--){ 29 int n; 30 scanf("%i",&n); 31 vector<int> a(n); 32 for(int i=0;i<n;i++) 33 scanf("%i",&a[i]); 34 sort(a.begin(),a.end()); 35 int zero=count(a.begin(),a.end(),0); 36 if(zero>0) 37 printf("%i\n",n-zero); 38 else{ 39 bool same=false; 40 for(int i=1;i<n;i++) 41 if(a[i]==a[i-1]) 42 same=true; 43 if(same)printf("%i\n",n); 44 else printf("%i\n",n+1); 45 } 46 } 47 return 0; 48 } 49 ``` 50 51 **Feedback** 52 53 * Good problem 54 * Average problem 55 * Bad problem 56 57 [1678B1 - Tokitsukaze и хорошая 01-строка (упрощенная версия)](/contest/1678/problem/B1 "Codeforces Round 789 (Div. 2)") and [1678B2 - Tokitsukaze и хорошая 01-строка (усложненная версия)](/contest/1678/problem/B2 "Codeforces Round 789 (Div. 2)") 58 59 Idea: [qsmcgogo](/profile/qsmcgogo "Мастер qsmcgogo")-B1, [74TrAkToR](/profile/74TrAkToR "Гроссмейстер 74TrAkToR")-B2 60 Prepare: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze") 61 62 **Tutorial(greedy)** 63 64 Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $0$ or $1$. In other words, the string is divided into many adjacent binaries with length of $2$. If the binary is "01" or "10", it needs $1$ operation, otherwise the operation is not required. 65 66 If you want to minimize the number of "contiguous segments", a simple greedy way is to change each "binary requiring operation" (i.e. $01$ or $10$) into the form of the previous or next "binary requiring no operation" (i.e. $11$ or $00$). For example: "0010" change to "0000" and "1101" change to "1111". In this way, this "binary requiring operation" has no contribution to the final number of contiguous segments. We only need to count the number of contiguous "11" and "00" binaries. 67 68 In particular, if all binaries are "01" or "10", the final contribution to the number of final contiguous segments is $1$ in total. 69 70 **Tutorial(DP)** 71 72 Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $0$ or $1$. In other words, the string is divided into many adjacent binaries with length of $2$. 73 74 Consider the recursion from the front to the back, it can be observed that the previously maintained prefix must end with "00" or "11". Therefore, it's necessary to convert each divided binary into "00" or "11" by enumerating the cost of changing the current binary into "00" and "11". Maintain the minimum number of operations in the process of DP, try to make the current string consistent with the end of the prefix subsegment. 75 76 $dp[n][2]$, set the first dimension as the maintained length of prefix and the second dimension as the suffix state of the prefix. 77 78 Then the DP transfer equation is: 79 80 $dp[i][0]=min(dp[i-2][0]+\left \{c_0,0\right \},dp[i-2][1]+\left \{c_0,1\right \})$ $dp[i][1]=min(dp[i-2][0]+\left \{c_1,1\right \},dp[i-2][1]+\left \{c_1,0\right \})$ 81 82 where $c_k$ represents the cost of converting the current binary to "kk". 83 84 **Solution(greedy)** 85 86 ``` 87 #include <bits/stdc++.h> 88 using namespace std; 89 using LL = long long; 90 int main() { 91 ios::sync_with_stdio(false); 92 cin.tie(nullptr); 93 int t; 94 for (cin >> t; t; t -= 1) { 95 int n, L = -1, x = 0, y = 0; 96 string s; 97 cin >> n >> s; 98 for (int i = 0; i < n; i += 2) { 99 if (s[i] != s[i + 1]) x += 1; 100 else { 101 if (L != s[i]) y += 1; 102 L = s[i]; 103 } 104 } 105 cout << x << " " << max(y, 1) << "\n"; 106 } 107 } 108 ``` 109 110 **Solution(DP)** 111 112 ``` 113 #include<bits/stdc++.h> 114 #define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout) 115 #define lowit(x) (x&-x) 116 117 #define range(x) begin(x), end(x) 118 #define sz(x) (int)(x).size() 119 #define pb push_back 120 121 #define sto \ 122 std::ios::sync_with_stdio(false); \ 123 std::cin.tie(nullptr); \ 124 std::cout.tie(nullptr); 125 126 using namespace std; 127 128 typedef long long ll; 129 typedef pair<ll,ll> PII; 130 131 inline ll read(){ 132 ll x=0;char ch;bool f=true; 133 for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f; 134 for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48); 135 return f?x:-x; 136 } 137 //#define LOCAL_DEFINE 138 #define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl 139 const int N=2e5+7; 140 const int INF=1e9; 141 char s[N]; 142 int c[N]; 143 PII dp[N][2]; 144 void solve(){ 145 int n=read(); 146 scanf("%s",s+1); 147 for(int i=1;i<=n;i++)s[i]-='0'; 148 for(int i=1;i<=n/2;i++)c[i]=s[i*2]+s[i*2-1]*2; 149 for(int i=1;i<=n/2;i++)for(int j=0;j<2;j++)dp[i][j]={INF,INF}; 150 for(int i=1;i<=n/2;i++)for(int j=0;j<2;j++){ 151 int cc=c[i],dd=j?3:0,cnt=((dd%2)^(cc%2))+((dd/2)^(cc/2)); 152 for(int k=0;k<2;k++) 153 dp[i][j]=min(dp[i][j],{dp[i-1][k].first+cnt,dp[i-1][k].second+(j!=k)}); 154 } 155 PII ans=min(dp[n/2][0],dp[n/2][1]); 156 cout<<ans.first<<" "<<ans.second+1<<"\n"; 157 } 158 159 int main(){ 160 #ifdef ONLINE_JUDGE 161 #else 162 //fre("1"); 163 #endif 164 ll T=1; 165 T=read(); 166 for(int i=1;i<=T;i++)solve(); 167 #ifdef LOCAL_DEFINE 168 cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; 169 #endif 170 return 0; 171 } 172 ``` 173 174 **Feedback-B1** 175 176 * Good problem 177 * Average problem 178 * Bad problem 179 180 **Feedback-B2** 181 182 * Good problem 183 * Average problem 184 * Bad problem 185 186 [1677A - Tokitsukaze и странное неравенство](/contest/1677/problem/A "Codeforces Round 789 (Div. 1)") 187 188 Idea: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze") 189 Prepare: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze") 190 191 **Tutorial** 192 193 We can calculate the answer in two steps. 194 195 The first step, for each $b$, let $f_b$ represents the number of $p_d$ where $p_b \gt p_d$ in the interval $[b+1,n]$. We can calculate $f$ in $\mathcal{O}(n^2)$. 196 197 The second step, calculate the answer. First we enumerate $c$ from $1$ to $n$, and then enumerate $a$ from $1$ to $c-1$. When $p_a \lt p_c$, add $f_b$ in the interval $[a+1,c-1]$ to the answer. Before enumerating $a $, we can calculate the prefix sum of $f$ first, so we can add the $f_b$ in the interval to the answer in $\mathcal{O}(1)$. The time complexity of this step is $\mathcal{O}(n^2)$. However, this will add the result of $d$ in the interval $[a+1,c-1]$ to the answer, which is illegal because $c \lt d$ is required. So we need to maintain $f$ while enumerating $c$: enumerate $b$ from $1$ to $c-1$, if $p_b \gt p_c$, $f_b$ minus $1$. $p_c$ is actually regarded as $p_d$, that is, subtract the case where $c$ is equal to $d$, so as to subtract the illegal case. The time complexity of this step is also $\mathcal{O}(n^2)$. 198 199 Time complexity:$\mathcal{O}(n^2)$. 200 201 By the way, use Fenwick Tree or Segment Tree can also pass, the time complexity is $\mathcal{O}(n^2 log\ n)$ 202 203 **Solution** 204 205 ``` 206 #include <bits/stdc++.h> 207 using namespace std; 208 /************* debug begin *************/ 209 string to_string(string s){return '"'+s+'"';} 210 string to_string(const char* s){return to_string((string)s);} 211 string to_string(const bool& b){return(b?"true":"false");} 212 template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();} 213 template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";} 214 template<class A>string to_string(const vector<A> v){ 215 int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}"; 216 return res; 217 } 218 void debug_out(){puts("");} 219 template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);} 220 #ifdef tokitsukaze 221 #define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__); 222 #else 223 #define debug(...) 233; 224 #endif 225 /************* debug end *************/ 226 #define mem(a,b) memset((a),(b),sizeof(a)) 227 #define MP make_pair 228 #define pb push_back 229 #define fi first 230 #define se second 231 #define sz(x) (int)x.size() 232 #define all(x) x.begin(),x.end() 233 #define sqr(x) (x)*(x) 234 using namespace __gnu_cxx; 235 typedef long long ll; 236 typedef unsigned long long ull; 237 typedef pair<int,int> PII; 238 typedef pair<ll,ll> PLL; 239 typedef pair<int,ll> PIL; 240 typedef pair<ll,int> PLI; 241 typedef vector<int> VI; 242 typedef vector<ll> VL; 243 typedef vector<PII > VPII; 244 /************* define end *************/ 245 void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);} 246 void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);} 247 void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);} 248 void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);} 249 /*************** IO end ***************/ 250 void go(); 251 int main(){ 252 #ifdef tokitsukaze 253 freopen("TEST.txt","r",stdin); 254 #endif 255 go();return 0; 256 } 257 const int INF=0x3f3f3f3f; 258 const ll LLINF=0x3f3f3f3f3f3f3f3fLL; 259 const double PI=acos(-1.0); 260 const double eps=1e-6; 261 const int MAX=1e5+10; 262 const ll mod=998244353; 263 /********************************* head *********************************/ 264 int a[MAX]; 265 ll f[MAX],bitf[MAX]; 266 void go() 267 { 268 int n,i,j,k,l,T; 269 ll ans; 270 scanf("%d",&T); 271 while(T--) 272 { 273 scanf("%d",&n); 274 for(i=1;i<=n;i++) scanf("%d",&a[i]); 275 mem(f,0); 276 for(j=1;j<=n;j++) 277 { 278 for(l=j+1;l<=n;l++) 279 { 280 if(a[j]>a[l]) f[j]++; 281 } 282 } 283 ans=0; 284 for(k=1;k<=n;k++) 285 { 286 for(j=1;j<k;j++) 287 { 288 if(a[j]>a[k]) f[j]--; 289 } 290 bitf[0]=0; 291 for(i=1;i<=k;i++) bitf[i]=bitf[i-1]+f[i]; 292 for(i=1;i<k;i++) 293 { 294 if(a[i]<a[k]) ans+=bitf[k-1]-bitf[i]; 295 } 296 } 297 printf("%lld\n",ans); 298 } 299 } 300 ``` 301 302 **Feedback** 303 304 * Good problem 305 * Average problem 306 * Bad problem 307 308 [1677B - Tokitsukaze и собрание](/contest/1677/problem/B "Codeforces Round 789 (Div. 1)") 309 310 Idea: [funer](/profile/funer "Кандидат в мастера funer") 311 Prepare: [tokitsukaze](/profile/tokitsukaze "Эксперт tokitsukaze"), [funer](/profile/funer "Кандидат в мастера funer") 312 313 **Tutorial** 314 315 Obviously, we can calculate the answers of rows and columns separately. 316 317 For the answers of columns, we can observe that since there are only $n \cdot m$ students in total, no students will leave, and every time a new student entering the meeting hall, all columns will move one step to the right circularly, so the answer will not decrease. If the $i$-th student is a serious student, for all the previous students with subscript $j$ where $0 \lt j \lt i$, and $j \% m = i \% m$ are naughty students, the answer in the column will increase by $1$. 318 319 For the answer of rows, we can transfer it from the answer of $i-m$, which is equivalent to adding a new row to the answer of $i-m$. Suppose the last serious student is the $j$-th student. If $i-j \lt m$, the answer will increase by $1$, otherwise the answer will be the same as that of when the $i-m$ student enters the meeting hall. 320 321 **Solution** 322 323 ``` 324 #include<bits/stdc++.h> 325 using namespace std; 326 int rownum[1000100]; 327 int col[1000100]; 328 int n,m; 329 void init(){ 330 for(int i = 0;i <= max(n,m);i++) { 331 rownum[i] = col[i] = 0; 332 } 333 } 334 void solve(){ 335 scanf("%d%d",&n,&m); 336 init(); 337 int las = -n*m; 338 int colnum = 0; 339 char tmp; 340 for(int i = 0;i < n*m;i++) { 341 scanf(" %c",&tmp); 342 tmp -= '0'; 343 if(tmp == 1) { 344 las = i; 345 if(col[i%m] == 0) { 346 col[i%m] = 1; 347 colnum++; 348 } 349 } 350 if(i - las < m) { 351 rownum[i%m]++; 352 } 353 if(i!=0) printf(" "); 354 printf("%d",rownum[i%m] + colnum); 355 356 } 357 printf("\n"); 358 } 359 int main(){ 360 int T; 361 scanf("%d",&T); 362 while(T--) { 363 solve(); 364 } 365 } 366 ``` 367 368 **Feedback** 369 370 * Good problem 371 * Average problem 372 * Bad problem 373 374 [1677C - Tokitsukaze и две красочные ленты](/contest/1677/problem/C "Codeforces Round 789 (Div. 1)") 375 376 Idea: [qsmcgogo](/profile/qsmcgogo "Мастер qsmcgogo"), [winterzz1](/profile/winterzz1 "Мастер winterzz1") 377 Prepare: [winterzz1](/profile/winterzz1 "Мастер winterzz1") 378 379 **Tutorial** 380 381 First, find the cycle directly, take out all the cycles, and then fill each cycle in the order: maximum, minimum, maximum, minimum $ \ldots $. 382 383 Note that when you encounter an odd cycle, the last one should be empty and fill in the middle value. 384 385 For example, in a ternary cycle, if the first and the second position are filled with $1$ and $9$, it can be observed that the contribution of the ternary cycle to the answer remains unchanged no matter which number between $2 \sim 8$ is filled in the middle. So this situation can be left out first, and finally fill in whatever number is left. The same to the cycles with odd sizes such as self cycles and five membered cycles, because the last number does not provide any contribution. In this way, you can directly construct a solution with the maximum $score$. 386 387 We notice that if we take out the numbers that has already been filled in each cycle and put them into a new cycled array $h$, in fact, the numbers providing contribution are only at the "peak" and "valley" points of the array. We define "peak" as the point with subscript $i$ where $h_{i} \gt h_{i-1}$ and $h_{i} \gt h_{i+1}$, and "valley" is the point with subscript $i$ where $h_{i} \lt h_{i-1}$ and $h_{i} \lt h_{i+1}$. Obviously, each "peak" will provide contribution of $2 \cdot h_{i}$, each "valley" will provide contribution of $-2 \cdot h_{i}$. For the points which are neither "peak"s nor "valley"s, they do not provide any contribution. 388 389 In order to maximize the score, we make the larger number in the permutation "peak" and the smaller number "valley". There are $\left \lfloor \frac{CircleSize}{2} \right \rfloor$ "peak"s and "valley"s for a circle with a length of $Circlesize$. 390 391 So the expression of the final answer can be derived from the summation formula of the arithmetic sequence: 392 393 Let $c=\sum \left \lfloor \frac{CircleSize}{2} \right \rfloor$, $N$ represents the size of the permutation, $score=2c \cdot (N-c)$. 394 395 **Solution** 396 397 ``` 398 #include <bits/stdc++.h> 399 using namespace std; 400 const int MAXN = 100005; 401 int n,col[2][MAXN],col_to_pos_1[MAXN]; 402 long long output; 403 bool vis_0[MAXN]; 404 int T,cnt; 405 long long c; 406 void dfs(int pos) 407 { 408 if(vis_0[pos])return; 409 vis_0[pos]=true; 410 ++cnt; 411 dfs(col_to_pos_1[col[0][pos]]); 412 } 413 int main(int argc, char const *argv[]) 414 { 415 scanf("%d",&T); 416 while(T--) 417 { 418 scanf("%d",&n); 419 for(int i=1;i<=n;++i) 420 { 421 vis_0[i]=false; 422 } 423 for(int i=1;i<=n;++i) 424 { 425 scanf("%d",&col[0][i]); 426 } 427 for(int i=1;i<=n;++i) 428 { 429 scanf("%d",&col[1][i]); 430 col_to_pos_1[col[1][i]]=i; 431 } 432 c=0; 433 for(int i=1;i<=n;++i) 434 { 435 cnt=0; 436 dfs(i); 437 c+=cnt/2; 438 } 439 printf("%lld\n", (c*(n-c))<<1); 440 } 441 442 return 0; 443 } 444 ``` 445 446 **Feedback** 447 448 * Good problem 449 * Average problem 450 * Bad problem 451 452 [1677D - Tokitsukaze и перестановки](/contest/1677/problem/D "Codeforces Round 789 (Div. 1)") 453 454 Idea: [dark_light](/profile/dark_light "Гроссмейстер dark_light"), [FreshP_0325](/profile/FreshP_0325 "Международный мастер FreshP_0325") 455 Prepare: [dark_light](/profile/dark_light "Гроссмейстер dark_light") 456 457 **Tutorial** 458 459 Consider finding out the relationship between sequence $v$ and permutation $p$. It can be observed that the permutation $p$ have bijective relationship with sequence $c$. That is to say, sequence $c$ will only correspond to one permutation $p$, as it can be proved: 460 461 Let $S={1,2,\ldots,n}$, and find that the last number can be determined through $c_n$, because there is no number after this position. We observe that $p_n$ is the $(c_n+1)$ largest number in $S$, then delete $p_n$ from $S$, we can get $p_{n - 1}$. So repeat the process, we can get the whole permutation. 462 463 Consider counting $v$, we observe that each bubble sort will first make $v_i=\max(v_{i}-1,0)$, then the whole $v$ moves left, $v_1$ is directly covered, $v_n$ is set to $0$. Because each valued $v_i$ is preceded by a number larger than the current position, then it will definitely be exchanged and moved forward, $v_i$ minus $1$. 464 465 For example, if the current $v=[0,0,2,1,1]$, after once bubble sort, $v=[0,1,0,0,0]$. 466 467 To avoid confusion, the $V$ array below is the $v$ in the input. It's easy to count after knowing the above conclusion. 468 469 For the position $i(i\le k)$, it can be observed that after $k$ times of bubble sort , it is directly covered, so just multiply the answer by $\prod_{i=1}^k i$. 470 471 For the position $i(k\lt i \le n)$, if $V_{i-k}\ne -1$, then obviously $v_i$ is uniquely determined; If $V_{i-k}=-1$, then $v_i$ has $i$ possible values, multiply the answer by $i$; If $V_{i-k}=0$, then $v_i-k\le 0$, multiply the answer by $k+1$. 472 473 Note that for the position $i(i\ge n-k+1)$, $V_i$ should be $0$ or $-1$, otherwise the answer must be $0 $. 474 475 Complexity:$\mathcal{O}(n)$. 476 477 **Solution** 478 479 ``` 480 #include<cstdio> 481 #include<iostream> 482 #include<cstring> 483 #include<algorithm> 484 #include<queue> 485 #include<map> 486 #include<ctime> 487 #include<cmath> 488 #include<unordered_map> 489 using namespace std; 490 #define LL long long 491 #define pp pair<int,pair<int,int>> 492 #define mp make_pair 493 #define fi first 494 #define se second.first 495 #define th second.second 496 namespace IO{ 497 const int sz=1<<22; 498 char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105]; 499 inline char gc(){ 500 return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++; 501 } 502 template<class T> void gi(T& x){ 503 x=0; int f=1;char c=gc(); 504 if(c=='-')f=-1; 505 for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1; 506 for(;c>='0'&&c<='9';c=gc()) 507 x=x*10+(c-'0'); 508 x=x*f; 509 } 510 inline void flush(){fwrite(b,1,t-b,stdout),t=b; } 511 inline void pc(char x){*t++=x; if(t-b==sz) flush(); } 512 template<class T> void pi(T x,char c='\n'){ 513 if(x==0) pc('0'); int t=0; 514 for(;x;x/=10) p[++t]=x%10+'0'; 515 for(;t;--t) pc(p[t]); pc(c); 516 } 517 struct F{~F(){flush();}}f; 518 } 519 using IO::gi; 520 using IO::pi; 521 using IO::pc; 522 int t,n,a[1000005],ans,k; 523 const int mod=998244353; 524 signed main(){ 525 srand(time(0)); 526 gi(t); 527 while(t--){ 528 gi(n),gi(k); 529 bool f=0; 530 for(int i=1;i<=n;i++)gi(a[i]),f|=(a[i]>i-1); 531 if(f){ 532 pi(0,'\n'); 533 continue; 534 } 535 ans=1; 536 for(int i=1;i<=k;i++)ans=1ll*ans*i%mod; 537 for(int i=n-k+1;i<=n;i++){ 538 if(a[i]!=-1&&a[i]){ 539 pi(0,'\n'); 540 f=1; 541 break; 542 } 543 } 544 if(f)continue; 545 for(int i=k+1;i<=n;i++){ 546 int limit=i-1; 547 if(a[i-k]==-1){ 548 ans=1ll*ans*i%mod; 549 }else{ 550 if(a[i-k]){ 551 limit=a[i-k]+k; 552 if(limit>i-1)f=1; 553 } 554 else { 555 limit=min(limit,k),ans=1ll*ans*(limit+1)%mod; 556 } 557 } 558 } 559 if(f)ans=0; 560 pi(ans,'\n'); 561 } 562 return 0; 563 } 564 ``` 565 566 **Feedback** 567 568 * Good problem 569 * Average problem 570 * Bad problem 571 572 [1677E - Tokitsukaze и красивые подотрезки](/contest/1677/problem/E "Codeforces Round 789 (Div. 1)") 573 574 Idea: [Frank_DD](/profile/Frank_DD "Мастер Frank_DD") 575 Prepare: [Frank_DD](/profile/Frank_DD "Мастер Frank_DD") 576 577 **Tutorial** 578 579 Let's sort the queries $[l,r]$ with $r$ in ascending order. 580 581 Let's move $R$ from $1$ to $n$, and answer queries $[l,r]$ when $r=R$. 582 583 Use segment tree to solve this problem, each leaf node $[ul,ul]$ in the segment tree maintenance the number that how many intervals $[ul,R]$ are beautiful, then answering queries is to get sum. 584 585 Use monotone stack to maintain the maximum number. When moving $R$ one step right, the monotone stack will pop some and push one. 586 587 Let's think about the number $x$ in monotone stack, which means the maximum number of the intervals $[lp,R]$ ($l1 \le lp \le l2$) is $x$. If there exist a $ll$ in $[l1,l2]$ which satisfies $a_{ll}*a_R=x$, then before $x$ is poped, intervals $[l,rr]$ are beautiful($l \in [l1,l2]$,$l \le ll$ ,$R \le rr$). 588 589 So we can assume that $x$ will not be poped when it is pushed in the monotone stack, and do something like difference algorithm in the segment tree, by using the current $R$ as the time stamp. Each node in the segment tree has to maintain $a*R+b$,which like a linear function. 590 591 So when moving $R$ right step, let's enumerate the factor of $a_R$ to update old intervals in monotone stack, enumerate the multiple of $a_R$ to update the new interval in monotone stack and update the intervals which are poped. 592 593 Time complexity: $\mathcal{O}(nlognlogn+qlogn)$. 594 595 **Solution** 596 597 ``` 598 #include<bits/stdc++.h> 599 using namespace std; 600 const int N=2e5+5; 601 typedef pair<int,int> pp; 602 int n,m,ti,top,a[N],d[N],p[N],bz[N],bo[N]; 603 long long ans[1000005]; 604 vector<pp>q[1000005]; 605 vector<int>w[N]; 606 struct dd 607 { 608 long long x,y,tg,len; 609 }tr[N*4]; 610 void make(int x,int l,int r) 611 { 612 tr[x].len=r-l+1; 613 if (l==r) return; 614 int mid=l+r>>1; 615 make(x<<1,l,mid),make(x<<1|1,mid+1,r); 616 } 617 void down(int x) 618 { 619 if (tr[x].x==tr[x].len) 620 { 621 tr[x<<1].x=tr[x<<1].len; 622 tr[x<<1|1].x=tr[x<<1|1].len; 623 } 624 if (tr[x].x==0) 625 { 626 tr[x<<1].x=0; 627 tr[x<<1|1].x=0; 628 } 629 tr[x<<1].tg+=tr[x].tg; 630 tr[x<<1].y+=tr[x].tg*tr[x<<1].len; 631 tr[x<<1|1].tg+=tr[x].tg; 632 tr[x<<1|1].y+=tr[x].tg*tr[x<<1|1].len; 633 tr[x].tg=0; 634 } 635 void up(int x) 636 { 637 tr[x].x=tr[x<<1].x+tr[x<<1|1].x; 638 tr[x].y=tr[x<<1].y+tr[x<<1|1].y; 639 } 640 void clear(int x,int l,int r,int ll,int rr) 641 { 642 if (l>=ll && r<=rr) 643 { 644 tr[x].tg+=ti; 645 tr[x].y+=ti*tr[x].len; 646 tr[x].x=0; 647 return; 648 } 649 down(x); 650 int mid=l+r>>1; 651 if (ll<=mid) clear(x<<1,l,mid,ll,rr); 652 if (rr>mid) clear(x<<1|1,mid+1,r,ll,rr); 653 up(x); 654 } 655 void add(int x,int l,int r,int ll,int rr) 656 { 657 if (l>=ll && r<=rr) 658 { 659 tr[x].tg-=ti; 660 tr[x].x=tr[x].len; 661 tr[x].y-=ti*tr[x].len; 662 return; 663 } 664 down(x); 665 int mid=l+r>>1; 666 if (ll<=mid) add(x<<1,l,mid,ll,rr); 667 if (rr>mid) add(x<<1|1,mid+1,r,ll,rr); 668 up(x); 669 } 670 long long find(int x,int l,int r,int ll,int rr) 671 { 672 if (l>=ll && r<=rr) return tr[x].y+ti*tr[x].x; 673 down(x); 674 int mid=l+r>>1; 675 long long ans=0; 676 if (ll<=mid) ans+=find(x<<1,l,mid,ll,rr); 677 if (rr>mid) ans+=find(x<<1|1,mid+1,r,ll,rr); 678 return ans; 679 } 680 int main() 681 { 682 //freopen("a.in","r",stdin); 683 //freopen("1.out","w",stdout); 684 scanf("%d%d",&n,&m); 685 for (int i=1;i<=n;i++) scanf("%d",&a[i]),bz[a[i]]=i; 686 for (int i=1;i<=m;i++) 687 { 688 int l,r; 689 scanf("%d%d",&l,&r); 690 q[r].emplace_back(l,i); 691 } 692 for (int i=1;i<=n;i++) 693 for (int j=i;j<=n;j+=i) 694 w[j].emplace_back(i); 695 make(1,1,n); 696 for (int i=1;i<=n;i++) 697 { 698 while (top && a[d[top]]<a[i]) 699 { 700 if (p[top]>d[top-1]) clear(1,1,n,d[top-1]+1,p[top]); 701 bo[d[top]]=0; 702 top--; 703 } 704 for (int j=a[i];j<=n;j+=a[i]) 705 if (bo[bz[j]]) 706 { 707 int pt=bo[bz[j]]; 708 int l=d[pt-1]+1,r=d[pt]; 709 int e=bz[j/a[i]]; 710 if (e<l || e>=i) continue; 711 e=min(e,r); 712 if (e<=p[pt]) continue; 713 // if (l<=p[pt]) clear(1,1,n,l,p[pt]); 714 add(1,1,n,p[pt]+1,e); 715 p[pt]=e; 716 } 717 d[++top]=i; 718 bo[i]=top; 719 p[top]=d[top-1]; 720 for (auto j:w[a[i]]) 721 { 722 int l=d[top-1]+1,r=i; 723 int e1=bz[j],e2=bz[a[i]/j]; 724 if (e2<=e1) continue; 725 if (e1<l || e2>i) continue; 726 if (e1<=p[top]) continue; 727 // if (l<=p[top]) clear(1,1,n,l,p[top]); 728 add(1,1,n,p[top]+1,e1); 729 p[top]=e1; 730 } 731 ti++; 732 for (auto t:q[i]) ans[t.second]=find(1,1,n,t.first,i); 733 } 734 for (int i=1;i<=m;i++) printf("%lld\n",ans[i]); 735 return 0; 736 } 737 ``` 738 739 **Feedback** 740 741 * Good problem 742 * Average problem 743 * Bad problem 744 745 [1677F - Tokitsukaze и драгоценные камни](/contest/1677/problem/F "Codeforces Round 789 (Div. 1)") 746 747 Idea: [dark_light](/profile/dark_light "Гроссмейстер dark_light") 748 Prepare: [dark_light](/profile/dark_light "Гроссмейстер dark_light") 749 750 **Tutorial** 751 752 First, consider how to calculate the contribution of a legal path. It can be found that the contribution of a legal path is equivalent to the following formula, where $b_i$ indicates the number of the $i$-th gems on the path. 753 754 $ \sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(\sum_{j=1}^n (P^{i_j}i_j^k)\times\sum_{j=1}^n [i_j\ne 0]) $ 755 756 This formula seems impossible to calculate, but it can be observed that there is a chain structure behind it. Consider dynamic programming, try to calculate the $1\sim (i+1)$-th gems' answer by only considering the $1\sim i$-th gems' answer. Consider maintenance these: 757 758 $dp_{n,1}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(\sum_{j=1}^n (P^{i_j}i_j^k)\times\sum_{j=1}^n [i_j\ne 0])$ 759 760 $dp_{n,2}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}\sum_{j=1}^n (P^{i_j}i_j^k)$ 761 762 $dp_{n,3}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n} \sum_{j=1}^n [i_j\ne 0]$ 763 764 $dp_{n,4}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n} 1$ 765 766 It can be observed that if we enumerate how many the $(n + 1)$-th gem are selected, this can actually be transferred, for example: 767 768 $dp_{n+1,1}=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}((\sum_{j=1}^n P^{i_j}i_j^k+P^p p^k)\times (\sum_{j=1}^n [i_j\ne 0])+[p\ne 0])$ 769 770 Then spread. 771 772 $A=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(\sum_{j=1}^n P^{i_j}i_j^k \times \sum_{j=1}^n [i_j\ne 0])=(1+b_{n+1})dp_{n,1}$ 773 774 $B=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}\sum_{j=1}^n P^{i_j}i_j^k[p\ne 0]=b_{n+1}dp_{n,2}$ 775 776 $C=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}P^p p^k\times \sum_{j=1}^n [i_j\ne 0]=dp_{n,3} \times \sum_{p=0}^{b_{n+1}}P^p p^k=dp_{n,3} \times \sum_{p=1}^{b_{n+1}}P^p p^k$ 777 778 $D=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(P^p p^k)\times [p\ne 0]=dp_{n,4}\times\sum_{p=1}^{b_{n+1}}P^p p^k$ 779 780 Now it can be transferred. The main problem is how to calculate $\sum_{i=1}^n i^kx^i$ quickly, ensuring that $x\gt 1$. 781 782 Let $h_{k,n}$ represent $\sum_{i=1}^n i^k x^i$. 783 784 Calculate the sum according to the proportional sequence, $h_{0,n}=\dfrac{x^{n+1}-x}{x-1}$. 785 786 $ xh_{k,n}-h_{k,n}=\sum_{i=1}^n x^{i+1}i^k-\sum_{i=1}^nx^ii^k $ $ =x^{n+1}n^k+\sum_{i=1}^nx^i((i-1)^k-i^k) $ $ =x^{n+1}n^k+\sum_{i=1}^nx^i([\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}i^j]-i^k) $ $ =x^{n+1}n^k+\sum_{i=0}^{k-1}(-1)^{k-j}\binom{k}{j}h_{i,n} $ 787 788 Finally we get 789 790 $ h_{k,n}=\dfrac{x^{n+1}n^k+\sum_{i=0}^{k-1}(-1)^{k-j}\binom{k}{j}h_{i,n}}{x-1} $ 791 792 According to this recurrence formula, we can get 793 794 $ h_{0,n}=x^{n+1}(\frac{1}{x-1})-x\times(\frac{1}{x-1}) $ $ h_{1,n}=x^{n+1}(\frac{n}{x-1}-\dfrac{1}{(x-1)^2})-x(-\dfrac{1}{(x-1)^2}) $ 795 796 When $k$ is constant, there exist a $k$-degree polynomial $g_k(x)$ about $n$, making $h_{k,n}=x^{n+1}g_k(n)-xg_k(0)$. This conclusion can be proved by mathematical induction. 797 798 Consider how to use interpolation to get this polynomial, we only need to find $g_k(0)\sim g_k(k)$. 799 800 Consider difference method, $h_{k,n}-h_{k,n-1}=x^{n+1}g_k(n)-x^ng_k(n-1)=n^kx^n$. 801 802 So $xg_k(n)-g_k(n-1)=n^k$. But we still can't get $C$. There is a conclusion: the $(n + 1)$-th difference of the $n$-degree polynomial $f(x)$ is $0$. That is to say, $\sum_{i=0}^{n+1}(-1)^{n+1-i}\binom{n+1}{i}f(i)=0$. 803 804 So we can get $g_k(0)$, then use polynomial fast interpolation, and then polynomial multipoint evaluation to get the value of every point we need. 805 806 It can be observed that the DP transfer can be replaced by matrix, so there are matrices each position, the problem is equivalent to get the sum of the matrix products of all intervals. It's easy to solve. You can solve it in the way you like. 807 808 Overall complexity: $\mathcal{O}(k\log^2k+n)$. 809 810 **Solution** 811 812 ``` 813 #include<cmath> 814 #include<queue> 815 #include<cstdio> 816 #include<cstring> 817 #include<assert.h> 818 #include<iostream> 819 #include<algorithm> 820 using namespace std; 821 #define LL long long 822 #define int long long 823 const int MAXN=4e5+5; 824 const int MAXNN=1e5+5; 825 int n,k,P,fac[MAXN],ifac[MAXN],Inv[MAXN],rev[MAXN],x[MAXN],y[MAXN],K[MAXN],B[MAXN],g[MAXN],F[MAXN],Q[MAXN],val[MAXN]; 826 int a[MAXNN],b[MAXNN],W[21][MAXN*2]; 827 const int mod=998244353; 828 vector<int>G[MAXNN]; 829 inline int mul(int a,int b){return 1ll*a*b%mod;} 830 inline int dec(int a,int b){return ((a-b)%mod+mod)%mod;} 831 inline int add(int a,int b){return ((a+b)%mod+mod)%mod;} 832 inline int qkpow(int a,int b){ 833 int ans=1,base=a; 834 while(b){ 835 if(b&1)ans=mul(ans,base); 836 base=mul(base,base); 837 b>>=1; 838 } 839 return ans; 840 } 841 namespace IO{ 842 const int sz=1<<22; 843 char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105]; 844 inline char gc(){ 845 return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++; 846 } 847 template<class T> void gi(T& x){ 848 x=0; char c=gc(); 849 for(;c<'0'||c>'9';c=gc()); 850 for(;c>='0'&&c<='9';c=gc()) 851 x=x*10+(c-'0'); 852 } 853 inline void flush(){fwrite(b,1,t-b,stdout),t=b; } 854 inline void pc(char x){*t++=x; if(t-b==sz) flush(); } 855 template<class T> void pi(T x,char c='\n'){ 856 if(x==0) pc('0'); int t=0; 857 for(;x;x/=10) p[++t]=x%10+'0'; 858 for(;t;--t) pc(p[t]); pc(c); 859 } 860 struct F{~F(){flush();}}f; 861 } 862 using IO::gi; 863 using IO::pi; 864 using IO::pc; 865 const int S=4; 866 struct Matrix{ 867 int a[4][4]; 868 Matrix(){memset(a,0,sizeof a);} 869 void clear(){memset(a,0,sizeof a);} 870 void init(){for(int i=0;i<S;i++)a[i][i]=1;} 871 int* operator [] (int x){return a[x];} 872 Matrix friend operator +(Matrix A,Matrix B){ 873 Matrix ret=Matrix(); 874 for(int i=0;i<S;i++) 875 for(int j=0;j<=i;j++) 876 ret[i][j]=add(A[i][j],B[i][j]); 877 return ret; 878 } 879 Matrix friend operator -(Matrix A,Matrix B){ 880 Matrix ret=Matrix(); 881 for(int i=0;i<S;i++) 882 for(int j=0;j<=i;j++) 883 ret[i][j]=dec(A[i][j],B[i][j]); 884 return ret; 885 } 886 Matrix friend operator *(Matrix A,Matrix B){ 887 Matrix ret=Matrix(); 888 for(int k=0;k<S;k++) 889 for(int j=0;j<=k;j++) 890 if(B[k][j]) 891 for(int i=k;i<S;i++) 892 ret[i][j]=1ll*(ret[i][j]+1ll*A[i][k]*B[k][j])%mod; 893 return ret; 894 } 895 Matrix friend operator *(Matrix A,int x){ 896 Matrix ret=Matrix(); 897 for(int i=0;i<S;i++) 898 for(int j=0;j<=i;j++) 899 ret[i][j]=1ll*A[i][j]*x%mod; 900 return ret; 901 } 902 }d[MAXNN],dp[MAXNN],ans; 903 Matrix operator += (Matrix &p,Matrix q){return p=p+q;} 904 Matrix operator -= (Matrix &p,Matrix q){return p=p-q;} 905 Matrix operator *= (Matrix &p,Matrix q){return p=p*q;} 906 inline int C(int n,int m){ 907 if(n<m||m<0)return 0; 908 return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod; 909 } 910 void init(){ 911 fac[0]=ifac[0]=Inv[0]=Inv[1]=1; 912 for(int i=1;i<MAXN;i++)fac[i]=1ll*fac[i-1]*i%mod; 913 ifac[MAXN-1]=qkpow(fac[MAXN-1],mod-2); 914 for(int i=MAXN-2;i>=1;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod; 915 for(int i=2;i<MAXN;i++)Inv[i]=1ll*(mod-mod/i)*Inv[mod%i]%mod; 916 int wn; 917 for(int i=0,x=1;x<MAXN;i++,x<<=1){ 918 W[i][x]=1; 919 wn=qkpow(3,(mod-1)/(x<<1)); 920 for(int j=1;j<x;j++)W[i][x+j]=1ll*wn*W[i][x+j-1]%mod; 921 wn=qkpow(wn,mod-2); 922 for(int j=1;j<x;j++)W[i][x-j]=1ll*wn*W[i][x-j+1]%mod; 923 } 924 } 925 inline void NTT(int *a,int type,int n){ 926 for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]); 927 LL x,y; 928 for(int i=1,cnt=0;i<n;cnt++,i<<=1){ 929 for(int j=0;j<n;j+=(i<<1)){ 930 for(int t=0,k=j;k<j+i;k++,t+=type){ 931 x=a[k],y=1ll*W[cnt][i+t]*a[k+i]; 932 a[k]=(x+y)%mod; 933 a[k+i]=(x-y)%mod; 934 } 935 } 936 } 937 if(type==-1)for(int i=0;i<n;i++)a[i]=mul(a[i],Inv[n]); 938 } 939 void Polyinv(int *a,int *b,int len){ 940 static int c[MAXN]; 941 if(len==1){ 942 b[0]=qkpow(a[0],mod-2); 943 return ; 944 } 945 Polyinv(a,b,(len+1)>>1); 946 int l=0,m=(len<<1),n=1; 947 for(;n<=m;n<<=1,l++); 948 for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1)); 949 for(int i=0;i<len;i++)c[i]=a[i]; 950 for(int i=len;i<n;i++)c[i]=0; 951 NTT(c,1,n),NTT(b,1,n); 952 for(int i=0;i<n;i++)b[i]=1ll*(2-1ll*b[i]*c[i])%mod*b[i]%mod; 953 NTT(b,-1,n); 954 for(int i=len;i<n;i++)b[i]=0; 955 } 956 inline void Polydao(int *Aa,int *Bb,int len){ 957 Bb[len-1]=0; 958 for(int i=1;i<len;i++)Bb[i-1]=1ll*i*Aa[i]%mod; 959 } 960 int init_NTT(int L){ 961 int l=0,m=L,n=1; 962 for(;n<=m;n<<=1,l++); 963 for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1)); 964 return n; 965 } 966 void MUL(int *a,int *b,int *c,int n,int m,int lim){ 967 static int t1[MAXN],t2[MAXN],t3[MAXN]; 968 for(int i=0;i<n;i++)t1[i]=a[i]; 969 for(int i=0;i<m;i++)t2[i]=b[i]; 970 for(int i=n;i<lim;i++)t1[i]=0; 971 for(int i=m;i<lim;i++)t2[i]=0; 972 NTT(t1,1,lim),NTT(t2,1,lim); 973 for(int i=0;i<lim;i++)t3[i]=1ll*t1[i]*t2[i]%mod; 974 NTT(t3,-1,lim); 975 for(int i=0;i<n+m-1;i++)c[i]=t3[i]; 976 } 977 namespace Evaluation{ 978 #define ls(p) p<<1 979 #define rs(p) p<<1|1 980 int *T1[MAXN],*T2[MAXN],T3[MAXN],T4[MAXN],flow[MAXN*32],*now=flow; 981 void clear(){now=flow;} 982 inline void MUL2(int *a,int *b,int *c,int n,int m,int lim){ 983 static int t1[MAXN],t2[MAXN],t3[MAXN]; 984 for(int i=0;i<n;i++)t1[i]=a[i]; 985 for(int i=0;i<m;i++)t2[i]=b[i]; 986 reverse(t2,t2+m); 987 for(int i=n;i<lim;i++)t1[i]=0; 988 for(int i=m;i<lim;i++)t2[i]=0; 989 NTT(t1,1,lim),NTT(t2,1,lim); 990 for(int i=0;i<lim;i++)t3[i]=1ll*t1[i]*t2[i]%mod; 991 NTT(t3,-1,lim); 992 for(int i=m-1;i<n;i++)c[i-m+1]=t3[i]; 993 } 994 void pre(int *Q,int p,int l,int r){ 995 T1[p]=now,now+=r-l+2; 996 T2[p]=now,now+=r-l+2; 997 for(int i=0;i<=r-l+1;i++)T1[p][i]=T2[p][i]=0; 998 if(l==r){ 999 T1[p][0]=1; 1000 T1[p][1]=(mod-Q[l])%mod; 1001 return ; 1002 } 1003 int mid=(l+r)>>1; 1004 pre(Q,ls(p),l,mid); 1005 pre(Q,rs(p),mid+1,r); 1006 if(r-l+1<=256){ 1007 for(int i=0;i<=mid-l+1;i++) 1008 for(int j=0;j<=r-mid;j++) 1009 T1[p][i+j]=add(T1[p][i+j],1ll*T1[ls(p)][i]*T1[rs(p)][j]%mod); 1010 }else{ 1011 int lim=init_NTT(r-l+1); 1012 MUL(T1[ls(p)],T1[rs(p)],T1[p],mid-l+2,r-mid+1,lim); 1013 } 1014 } 1015 void Solve(int *S,int p,int l,int r){ 1016 if(l==r){ 1017 S[l]=T2[p][0]; 1018 return ; 1019 } 1020 int mid=(l+r)>>1; 1021 int lim=init_NTT(r-l+1); 1022 MUL2(T2[p],T1[rs(p)],T2[ls(p)],r-l+1,r-mid+1,lim); 1023 MUL2(T2[p],T1[ls(p)],T2[rs(p)],r-l+1,mid-l+2,lim); 1024 Solve(S,ls(p),l,mid); 1025 Solve(S,rs(p),mid+1,r); 1026 } 1027 //opt0/1 区分多点求值/快速插值 1028 void evaluation(int *F,int *Q,int *S,int n,int m,int opt){ 1029 clear(); 1030 static int AF[MAXN]; 1031 n=max(n,m+1),m=max(m,n-1); 1032 pre(Q,1,1,m); 1033 if(opt){ 1034 for(int i=0;i<n;i++)AF[i]=T1[1][i]; 1035 reverse(AF,AF+n); 1036 Polydao(AF,AF,n+1); 1037 } 1038 Polyinv(T1[1],T3,m+1); 1039 reverse(T3,T3+m+1); 1040 int lim=init_NTT(n+m+1); 1041 if(!opt)MUL(F,T3,T4,n,m+1,lim); 1042 else MUL(AF,T3,T4,n,m+1,lim); 1043 for(int i=n;i<n+m;i++)T2[1][i-n]=T4[i]; 1044 Solve(S,1,1,m); 1045 for(int i=1;i<=m;i++)S[i]=(1ll*S[i]*Q[i]%mod+(!opt?F[0]:AF[0]))%mod; 1046 for(int i=0;i<=n+m+1;i++)T3[i]=T4[i]=0; 1047 } 1048 }; 1049 namespace Lagrange_Interpolation{ 1050 #define ls(p) p<<1 1051 #define rs(p) p<<1|1 1052 int S[MAXN],*T[MAXN],flow[MAXN*32],*now=flow,tmp1[MAXN],tmp2[MAXN],e1[MAXN],e2[MAXN]; 1053 void solve(int p,int l,int r){ 1054 T[p]=now,now+=r-l+2; 1055 if(l==r){ 1056 T[p][0]=S[l]; 1057 return ; 1058 } 1059 int mid=(l+r)>>1; 1060 solve(ls(p),l,mid); 1061 solve(rs(p),mid+1,r); 1062 for(int i=0;i<mid-l+1;i++)tmp1[i]=T[ls(p)][i]; 1063 for(int i=0;i<r-mid;i++)tmp2[i]=T[rs(p)][i]; 1064 for(int i=0;i<r-mid+1;i++)e1[i]=Evaluation::T1[rs(p)][i]; 1065 reverse(e1,e1+r-mid+1); 1066 for(int i=0;i<mid-l+2;i++)e2[i]=Evaluation::T1[ls(p)][i]; 1067 reverse(e2,e2+mid-l+2); 1068 int lim=init_NTT(r-l+1); 1069 MUL(tmp1,e1,e1,mid-l+1,r-mid+1,lim); 1070 MUL(tmp2,e2,e2,r-mid,mid-l+2,lim); 1071 for(int i=0;i<=r-l;i++)T[p][i]=add(e1[i],e2[i]); 1072 } 1073 void Interpolation(int *x,int *y,int *ans,int n){ 1074 Evaluation::evaluation(x,x,S,n+1,n,1); 1075 for(int i=1;i<=n;i++)S[i]=1ll*y[i]*qkpow(S[i],mod-2)%mod; 1076 solve(1,1,n); 1077 for(int i=0;i<n;i++)ans[i]=T[1][i]; 1078 } 1079 } 1080 void Pre(int P){ 1081 int invP=qkpow(P,mod-2),kk=0,bb=0; 1082 K[0]=1,B[0]=0; 1083 for(int i=1;i<=k+1;i++){ 1084 K[i]=1ll*K[i-1]*invP%mod; 1085 B[i]=1ll*(B[i-1]+qkpow(i,k))*invP%mod; 1086 int Num=C(k+1,i); 1087 if(i&1)kk=dec(kk,1ll*Num*K[i]%mod),bb=dec(bb,1ll*Num*B[i]%mod); 1088 else kk=add(kk,1ll*Num*K[i]%mod),bb=add(bb,1ll*Num*B[i]%mod); 1089 } 1090 kk=(kk+1),kk=(kk==mod?0:kk); 1091 g[0]=1ll*(mod-bb)*qkpow(kk,mod-2)%mod; 1092 for(int i=1;i<=k;i++)g[i]=add(1ll*g[0]*K[i]%mod,B[i]); 1093 for(int i=1;i<=k+1;i++)x[i]=i-1,y[i]=(g[i-1]+mod)%mod; 1094 Lagrange_Interpolation::Interpolation(x,y,F,k+1); 1095 for(int i=0;i<=k;i++)F[i]=(F[i]+mod)%mod; 1096 // cout<<endl; 1097 for(int i=1;i<=n;i++)Q[i]=b[i]; 1098 Evaluation::evaluation(F,Q,val,k+1,n,0); 1099 for(int i=1;i<=n;i++)val[i]=(val[i]+mod)%mod; 1100 } 1101 inline void makeit(int Id,int y,Matrix& S){ 1102 //[S1S2,S1,S2,product of b] 1103 int X=dec(1ll*qkpow(P,y+1)*val[Id]%mod,1ll*P*g[0]%mod); 1104 S.a[0][0]=add(y,1),S.a[1][0]=y,S.a[2][0]=X,S.a[3][0]=X; 1105 S.a[1][1]=add(y,1),S.a[3][1]=X; 1106 S.a[2][2]=add(y,1),S.a[3][2]=y; 1107 S.a[3][3]=add(y,1); 1108 } 1109 signed main(){ 1110 gi(n),gi(k),gi(P); 1111 init(); 1112 for(int i=1;i<=n;i++)gi(b[i]); 1113 Pre(P); 1114 for(int i=1;i<=n;i++)makeit(i,b[i],d[i]); 1115 dp[1]=d[1]; 1116 for(int i=2;i<=n;i++)dp[i]=dp[i-1]*d[i]+d[i]; 1117 for(int i=1;i<=n;i++)ans+=dp[i]; 1118 pi(ans.a[3][0],'\n'); 1119 return 0; 1120 } 1121 ``` 1122 1123 **Feedback** 1124 1125 * Good problem 1126 * Average problem 1127 * Bad problem