codeforces-scrape

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

1542.md (9395B)


      1 Source: https://codeforces.com/blog/entry/92492
      2 
      3 **A Tutorial**
      4 
      5 The answer is 'yes' if and only if there are exactly $n$ odd numbers.
      6 
      7 **A Code**
      8 
      9 ```
     10 #include<bits/stdc++.h>
     11 using namespace std;
     12 int main() {
     13 	int t;
     14 	cin>>t;
     15 	while(t--){
     16 		int n,cnt[2]={0};
     17 		cin>>n;
     18 		for(int i=1,x;i<=n*2;i++)cin>>x,cnt[x%2]++;
     19 		if(cnt[0]==n)puts("Yes");
     20 		else puts("No");
     21 	}
     22 	return 0;
     23 }
     24 ```
     25 
     26 **B Hint 1**
     27 
     28 What kind of element in the set is important?
     29 
     30 **B Hint 2**
     31 
     32 If $x$ is in the set, but $x-b$ is not, $x$ is important. Why?
     33 
     34 **B Hint 3**
     35 
     36 How can we find all important elements?
     37 
     38 **B Tutorial**
     39 
     40 First check specially if $b=1$.
     41 
     42 Let's consider when $n$ is in $S$. The answer is when the smallest number $m$ in $S$ that $n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$ is less than $n$. It's easy to see that a new case of $x\ \mathrm{mod}\ b$ can only appear when you use $\times a$ to generate a new element. So the smallest number $m$ in S that $m\ \mathrm{mod}\ b=k$ must be a power of $a$.
     43 
     44 Find all powers of a that is smaller than $n$. If there is one $m=a^k$ that $n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$, the answer is yes. Otherwise it's no. Time complexity is $O(\log n)$.
     45 
     46 **B Code (Python)**
     47 
     48 ```
     49 t=(int)(input())
     50 for i in range(t):
     51     w=input().split()
     52     n=(int)(w[0])
     53     a=(int)(w[1])
     54     b=(int)(w[2])
     55     if a==1 :
     56     	if (n-1)%b==0 :
     57     		print("Yes")
     58     	else :
     59     		print("No")
     60     	
     61     else :
     62     	t=1
     63     	flag=0
     64     	while t<=n :
     65     		if t%b==n%b:
     66     			flag=1
     67     			break
     68     		t=t*a
     69     	if flag==1:
     70     		print("Yes")
     71     	else :
     72     		print("No")
     73 ```
     74 
     75 **C Hint 1**
     76 
     77 $f(n)$ is small.
     78 
     79 **C Hint 2**
     80 
     81 For a given $x$, when is $f(n)$ equal to $x$?
     82 
     83 **C Tutorial**
     84 
     85 Enumerate the value of $f(i)$. Since $f(n)=i$ means $lcm(1,2,...,i-1)\le n$, $f(n)$ will not be too big (less than $100$). The number of $k$s such that $f(k)=i$ is $\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor $. ($k$ should be divisible by $1\sim i-1$ but not $i$) So the answer is $\sum_{i \gt 1} i(\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor )$.
     86 
     87 We can also write the answer in another form, which is equivalent to the previous form:
     88 
     89 $ \sum_{i\ge 1} \lfloor n/lcm(1,2,...,i)\rfloor +n $
     90 
     91 **C Code**
     92 
     93 ```
     94 #include<bits/stdc++.h>
     95 #define int long long
     96 #define re register
     97 using namespace std;
     98 int t,n;
     99 const int M=1e9+7;
    100 inline int gcd(re int x,re int y){
    101 	return y?gcd(y,x%y):x;
    102 }
    103 inline int LCM(re int x,re int y){
    104 	return x/gcd(x,y)*y;
    105 }
    106 signed main(){
    107 	scanf("%lld",&t);
    108 	while(t--){
    109 		scanf("%lld",&n);
    110 		re int G=1,ans=0;
    111 		for(re int i=1;G<=n;++i){
    112 			G=LCM(G,i);
    113 			if(G>n)break;
    114 			ans+=n/G;
    115 		}
    116 		printf("%lld\n",(ans+n)%M);
    117 	}
    118 }
    119 ```
    120 
    121 **D Hint**
    122 
    123 For each $x$, count how many $B$s make the final set contain $x$.
    124 
    125 **D Tutorial**
    126 
    127 For each $x$, count how many $B$s make the final set contain $x$.
    128 
    129 Let's say we have picked the $x$ in the $I$-th operation, call it $X$. Then, the subsequence we choose must satisfy the following conditions:
    130 
    131 * It must contain the $i$-th operation (otherwise $X$ won't be added).
    132 * Let $s$ denote the number of numbers less than $X$ in the current $T$. Whenever we meet a `-` element in $S$ after the $i$-th operation, $s$ should be greater than $0$.
    133 
    134 With those conditions, we can come up with the following dp.
    135 
    136 Let $f(i,j)$ denote the number of subsequences of $a[1...i]$, that if we maintain $T$ with the subsequence, $s$ will become $j$.
    137 
    138 Then we have the following transitions:
    139 
    140 * $f(i-1,j)\to f(i,j)$ (when we don't include the $i$-th element is $S$, here $i\ne I$)
    141 * $f(i-1,j)\to f(i,\max(j-1,0))$ (here, $i \lt I$, and the $i$-th element of $A$ is `-`, so the number of numbers in $T$ less than $x$ decreases by one. If there is no such number, $s$ remains $0$)
    142 * $f(i-1,j)\to f(i,j-1)$ (here, $i \gt I$, and and the $i$-th element of $A$ is `-`, so the number of numbers in $T$ less than $x$ decreases by one.)
    143 * $f(i-1,j)\to f(i,j)$ (here, the $i$-th element of $A$ is `+` and its $x$ is greater than $X$)
    144 * $f(i-1,j)\to f(i,j+1)$ (here, the $i$-th element of $A$ is `+` and its $x$ is less than $x$ or [equal to $x$ but $i>I$] ) [this is to deal with same elements]
    145 
    146 Then we add $ans$ by $X\times \sum_{i\ge 0} f(n,i)$.
    147 
    148 The time complexity is $O(n^3)$.
    149 
    150 **D Code (Python)**
    151 
    152 ```
    153 mod=998244353
    154 n=(int)(input())
    155 a=[0 for i in range(n+1)]
    156 for i in range(1,n+1):
    157 	m=input().split()
    158 	if m[0]=="+":
    159 		a[i]=(int)(m[1])
    160 	
    161 ans=0
    162 for t in range(1,n+1):
    163 	if a[t]==0:
    164 		continue
    165 	f=[[0 for i in range(n+2)] for j in range(n+2)]
    166 	f[0][0]=1
    167 	for i in range(1,n+1):
    168 		for j in range(0,i+1):
    169 			if a[i]==0:
    170 				if ((i<=t) or (j>0)):
    171 					f[i][max(j-1,0)]=(f[i][max(j-1,0)]+f[i-1][j])%mod
    172 			else :
    173 				if ((a[i]<a[t]) or ((a[i]==a[t]) and (i<t))):
    174 					f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod
    175 				else :
    176 					f[i][j]=(f[i][j]+f[i-1][j])%mod
    177 			
    178 			if (i!=t) :
    179 				f[i][j]=(f[i][j]+f[i-1][j])%mod
    180 				
    181 			
    182 		
    183 	
    184 	for i in range(0,n+1):
    185 		ans=(ans+f[n][i]*a[t])%mod
    186 	
    187  
    188 print(ans)
    189 ```
    190 
    191 **E1 Hint**
    192 
    193 What does lexicographically mean?
    194 
    195 **E1 Tutorial**
    196 
    197 Let's first calculate the number of permutation pair $(p,q)$s (with length $i$) that $p_1 \lt q_1$ but $inv(p) \gt inv(q)$ ($inv(p)$ is the number of inversions in $p$). Call it $t_i$.
    198 
    199 Let's enumerate $p_1=j$ and $q_1=k$, then $inv(p[2...i])-inv(q[2...i]) \gt k-j$. ($inv(p)=inv(p[2...i])+j-1,inv(q)=inv(q[2...i])+k-1$, with $inv(p) \gt inv(q)$ we get the following.)
    200 
    201 Precalculate $f(i,j)$: the number of permutation $p$s of length $i$ such that $inv(p)=j$. Let $s(i,j)$ be $\sum_{k\le j}f(i,k)$, then:
    202 
    203 $ t_i=\sum_{1\le j\le i}\sum_{j \lt k\le i} \sum_{w} f(i-1,w)s(i-1,w-(k-j)-1) $
    204 
    205 $f$ and $s$ can be calculated in $O(n^4)$ or $O(n^3)$ in the following way: if you insert $i$ into a permutation of length $i-1$ after the $i-1-p$-th element $(0\le p\le i-1)$, it will bring $p$ inversions into the permutation. So $f(i,j)=\sum_{j-i+1\le k\le j} f(i-1,k)$.
    206 
    207 After calculating $t$, calculating the answer it easy. Let $ans_i$ be the answer for $n=i$, then
    208 
    209 $ ans_i=i\times ans_{i-1}+t_i $
    210 
    211 Consider if $p_1=q_1$. If so, there are $i$ choices of $p_1$, and $ans_{i-1}$ choices of the following $n-1$ numbers. Otherwise, there are $t_i$ choices.
    212 
    213 Total complexity is $O(n^5)$, but it can be optimized to $O(n^4)$ if you consider the difference between $j-k$ only, and can be optimized to $O(n^3\log n)$ using FFT with arbitary mod (which we hope can't pass E2!).
    214 
    215 **E1 Code**
    216 
    217 ```
    218 #include<bits/stdc++.h>
    219 using namespace std;
    220 typedef long long ll;
    221 int n,mod,f[55][2005]={1},s[55][2005]={1},ans[55];
    222 int main(){
    223 	cin>>n>>mod;
    224 	for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;
    225 	for(int i=1;i<=n;i++){
    226 		for(int j=0;j<=n*(n-1)/2;j++){
    227 			if(j-i>=0)f[i][j]=(s[i-1][j]-s[i-1][j-i]+mod)%mod;
    228 			else f[i][j]=s[i-1][j];
    229 			s[i][j]=((j?s[i][j-1]:0)+f[i][j])%mod;
    230 		}
    231 	}
    232 	for(int i=1;i<=n;i++){
    233 		for(int j=1;j<=i;j++){
    234 			for(int k=j+1;k<=i;k++){
    235 				for(int o=0;o<=(i-1)*(i-2)/2;o++){
    236 					int t=o-(k-j)-1;
    237 					if(t<0)continue;
    238 					ans[i]=(ans[i]+1ll*f[i-1][o]*s[i-1][t]%mod)%mod;
    239 				}
    240 			} 
    241 		}
    242 	}
    243 	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
    244 	cout<<ans[n];
    245 }
    246 ```
    247 
    248 **E2 Hint**
    249 
    250 In E1 we calculated the number of permutation pairs from the number of permutations. Can we calculate the number of permutation pairs directly?
    251 
    252 **E2 Tutorial**
    253 
    254 We recommend you to read E1's editorial first.
    255 
    256 Let's directly count the number of permutation pairs $(p,q)$ of length $n$ with $inv(p)-inv(q)=k$, instead of counting it indirectly from "the number of permutation $p$s of length $i$ such that $inv(p)=j$.". Call this number $f(n,k)$.
    257 
    258 We have an $n^4$ transition: $f(n,k)=\sum_{|i| \lt n} f(n-1,k-i)\times (n-|i|)$ (Consider where to insert $n$ in the first and second permutation. If the two places are indices $(I,J)$, then the delta of $inv(p)$ is $n-I$, the other is $n-J$, so the delta of difference is $J-I$. In $[1,n]$ there are $n-|J-I|$ pairs of integers with difference $J-I$.)
    259 
    260 Let's speed it up. When $f(n,k)$ moves to $f(n,k+1)$, it looks like this: ($n=4$, as an example)
    261 
    262 * $f(n-1,k-3)\times 1+f(n-1,k-2)\times 2+f(n-1,k-1)\times 3+f(n-1,k)\times 4+f(n-1,k+1)\times 3+f(n-1,k+2)\times 2+f(n-1,k+3)\times 1$
    263 * $f(n-1,k-2)\times 1+f(n-1,k-1)\times 2+f(n-1,k)\times 3+f(n-1,k+1)\times 4+f(n-1,k+2)\times 3+f(n-1,k+3)\times 2+f(n-1,k+4)\times 1$
    264 
    265 So with prefix sums $s$ ($s(i,j)=\sum_{k\le j} f(i,k)$) we can write $f(n,k+1)=f(n,k)-(s(n-1,k)-s(n-1,k-n))+(s(n-1,k+n)-s(n-1,k))$.
    266 
    267 Note that the second indice of the array might be negative, so we should shift it by $130000$.
    268 
    269 The memory complexity is $O(n^3)$, so we should only keep two layers of transition to optimize it to $O(n^2)$ (If implemented well, $O(n^3)$ memory solutions can also pass.)
    270 
    271 **E2 Code**
    272 
    273 ```
    274 #include<bits/stdc++.h>
    275 using namespace std;
    276 typedef long long ll;
    277 const int B=130000;
    278 int n,mod,w[2][2*B+5],s[2][2*B+5],ans[505];
    279 int main(){
    280 	cin>>n>>mod;
    281 	w[0][B]=s[0][B]=1;
    282 	for(int i=B;i<=2*B;i++)s[0][i]=1;
    283 	for(int i=1;i<=n;i++){
    284 		int curs=1,I=i&1,J=I^1;
    285 		memset(w[I],0,sizeof(w[I])),memset(s[I],0,sizeof(s[I]));
    286 		for(int u=i*(i-1)/2,j=-u+B;j<=u+B;j++){
    287 			w[I][j]=curs;
    288 			curs=(0ll+curs-s[J][j]+s[J][j-i]+s[J][j+i]-s[J][j]+2ll*mod)%mod;
    289 		}
    290 		for(int j=B-i*(i-1)/2,v=(i+2)*(i+1)/2+B;j<=v;j++)s[I][j]=(s[I][j-1]+w[I][j])%mod;
    291 		for(int j=1;j<i;j++)ans[i]=(ans[i]+1ll*(s[J][(i+1)*i/2+B]-s[J][j+B]+mod)%mod*(i-j))%mod;
    292 	}
    293 	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
    294 	cout<<ans[n];
    295 }
    296 ```