codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1677.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