2026-07-24~25 hetao1733837 的刷题记录

2026-07-24~25 hetao1733837 的刷题记录07-24AT-agc002-f [AGC002F] Leftmost Ball原题链接F - Leftmost Ball分析我们发现每种颜色最终都会变成0 i × ( K − 1 ) 0i\times(K-1)0i×(K−1)。难道直接插板就做完了吗可能暴力复杂度估反了不过不重要。之前想的状态是设d p i , j dp_{i,j}dpi,j​表示j jj前面放了i ii个0 00的方案数。不过这个不好转移我们换个设法。我们设d p i , j dp_{i,j}dpi,j​表示已经放了i ii个0 00和j jj个其他数。转移有d p i , j d p i − 1 , j d p i , j − 1 × C n − i ( n − j 1 ) × ( k − 1 ) − 1 k − 2 dp_{i,j}dp_{i-1,j}dp_{i,j-1}\times C_{n-i(n-j1)\times(k-1)-1}^{k-2}dpi,j​dpi−1,j​dpi,j−1​×Cn−i(n−j1)×(k−1)−1k−2​这里其实很好理解就是每次都要把所有的当前颜色都插进去所以就是插板最后也实现了我们所谓的“K KK维插板”。正解#includebits/stdc.h#defineintlonglong#definemod1000000007usingnamespacestd;constintN2005;intn,k;intfac[N*N],inv[N*N];intdp[N][N];intqpow(inta,intb){intres1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}intcalc(intn,intm){returnfac[n]*inv[n-m]%mod*inv[m]%mod;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnk;if(k1){cout1;return0;}fac[0]1;for(inti1;iN*N;i)fac[i]fac[i-1]*i%mod;inv[N*N-1]qpow(fac[N*N-1],mod-2);for(intiN*N-2;i0;--i)inv[i]inv[i1]*(i1)%mod;dp[0][0]1;for(inti1;in;i){for(intj0;ji;j){dp[i][j]dp[i-1][j];if(j0)continue;dp[i][j](dp[i][j]dp[i][j-1]*(n-j1)%mod*calc(n-i(n-j1)*(k-1)-1,k-2))%mod;}}coutdp[n][n];return0;}AT-agc003-f [AGC003F] Fraction of Fractal原题链接F - Fraction of Fractal分析原谅我没有读懂题。我大概明白他在说什么了……吗哦看懂了就是按照原图的相对位置放就行了。那然后呢思考一下怎么做的……难道说原图上出现什么样的结构就会使得新的图形怎么样吗但是话说回来这个真的只是紫吗感觉上是出现类似于·#· …… #·#之类的结构会出现这些东西。太困难了我先撤了。AT-agc005-d [AGC005D] ~K Perm Counting原题链接D - ~K Perm Counting07-25LGP2900 [USACO08MAR] Land Acquisition G原题链接[USACO08MAR] Land Acquisition G分析排序是否重要呢应该是重要的我们应该随便选一维排序剩下的做DP然后斜率优化先准备打 AT 吧……AT-abc468-c Between P and Q原题链接C - Between P and Q分析思考一下首先需要判无解就是P PP的字典序大于Q QQ。我们似乎可以尝试H X F HXFHXF容斥。但是我觉得并不好写啊……我来尝试一下吧……哦我们可以数比P PP小的和比Q QQ小的直接减最后忘了减去1 11即P PP本身即可。正解#includebits/stdc.husingnamespacestd;constintN15;intn,p[N],q[N];intfac[]{1,1,2,6,24,120,720,5040,40320,362880,3628800};boolvis[N];intcalc(intperm[]){memset(vis,0,sizeof(vis));intans0;for(inti0;in;i){intcurn-i;intcnt0;for(intx1;xperm[i];x){if(!vis[x])cnt;}anscnt*fac[cur-1];vis[perm[i]]true;}returnans;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti0;in;i)cinp[i];for(inti0;in;i)cinq[i];boolflagfalse;for(inti0;in;i){if(p[i]q[i]){flagtrue;break;}elseif(p[i]q[i]){cout0;return0;}}if(!flag){cout0;return0;}intresPcalc(p);intresQcalc(q);coutresQ-resP-1;return0;}AT-abc468-d Pre-Palindrome原题链接D - Pre-Palindrome分析我觉得可以枚举回文串的中心。正解#includebits/stdc.husingnamespacestd;string s;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cins;intns.length(),ans0;for(inti0;in;i){intcnt0;for(intli,ri;l0rn;l--,r){if(s[l]!s[r])cnt;if(cnt1)break;ans;}}for(inti0;in-1;i){intcnt0;for(intli,ri1;l0rn;l--,r){if(s[l]!s[r])cnt;if(cnt1)break;ans;}}coutans;return0;}AT-abc468-e Sum of Average原题链接E - Sum of Average分析就是每次和都会模一些我们意想不到的东西……怎么形容呢就很奇怪吧……欸复杂度真的能卡住吗不想打了要不放了。感觉这个更适合放进期末数学考试。