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 ```