文章目錄

• T1：CF1228E Another Filling the Grid
• • solution
  • code
• T2：CF936C Lock Puzzle
• • solution
  • code

T1：CF1228E Another Filling the Grid

點我

solution

反過來思考，用所有方案數?不合法方案數
很容易想到的是——容斥！！
首先只考慮行數
減去至少一行沒有$1$的方案數，加上至少兩行沒有$1$的方案數…
得出以下柿子
$$\sum _{i=0}^n(?1{)}^i\times C_n^i\times (k?1{)}^{i\times n}\times k^{n^2?i\times n}$$
（枚舉$i$行不含$1$，那么這$i$行共$i\times n$個格子，除了$1$不能填，只有$k?1$個數可以填，剩下的$n^2?i\times n$格子$k$個數都可以填）
再加上列的限制
$$\sum _{i=0}^n\sum _{j=0}^n(?1{)}^{i+j}\times C_n^i\times C_n^j\times (k?1{)}^{i\times n+j\times n?i\times j}\times k^{n^2?(i\times n+j\times n?i\times j)}$$
（$i$行與$j$列包含的格子數$=i$行包含的格子數$i\times n+j$列包含的格子數$?i,j$共同包含的格子數$i\times j$）

---

到這里，$O(n^2)$已經可以悠閑地過這道題了，但是我們要 沒事找事吃飽了撐的 熱愛學習，深度挖掘，萬一$n$一下子猛加到$1e5,1e6$級別呢？？
換言之，我們是否還能再找到一個$O(nlogn)$的優秀算法呢？？

答案當然是$ofcourse,whynot$

---

來化一下上面的優美柿子

$$(k?1{)}^{i\times n+j\times n?i\times j}\times k^{n^2?(i\times n+j\times n?i\times j)}$$
$$=(k?1{)}^{i\times (n?j)}\times (k?1{)}^{j\times n}\times k^{(n?i)(n?j)}$$
$$=[(k?1{)}^i{]}^{(n?j)}\times [(k?1{)}^n{]}^j\times (k^{n?i}{)}^{n?j}$$
$$=[(k?1{)}^i\times k^{n?i}{]}^{n?j}\times [(k?1{)}^n{]}^j$$
到這里就非常明顯了，讓我們換個硬元更加明顯
令$x=(k?1{)}^i\times k^{n?i},y=(k?1{)}^n$
則上述柿子可變為$x^{n?j}\times y^j$
太像我們的二項式小可愛了，但是不要 不穿褲子就不跑 ，還少了點什么，我們需要把前面的
$(?1{)}^j\times C_n^j$提過來才行
$$(?1{)}^j\times C_n^j\times x^{n?j}\times y^j=(x?y{)}^n$$
于是答案柿子就可以剔除$j$，只剩下與$i$有關的柿子了
$$\sum _{i=0}^n(?1{)}^i\times C_n^i\times [(k?1{)}^i\times k^{n?i}+(k?1{)}^n{]}^n$$
次方就找快速冪$qkpow$老火雞完成，時間復雜度就成功降為$O(nlong)$
當然$k$的冪次可以提前預處理，這樣可以少跑幾次快速冪，優化可能有 個芝麻大點

code

#include <cstdio> #define int long long #define mod 1000000007 #define maxn 300 int n, k; int fac[maxn], inv[maxn];int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }int C( int n, int m ) {if( n < m ) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {scanf( "%lld %lld", &n, &k );fac[0] = inv[0] = 1;for( int i = 1;i <= n;i ++ )fac[i] = fac[i - 1] * i % mod;inv[n] = qkpow( fac[n], mod - 2 );for( int i = n - 1;i;i -- ) inv[i] = inv[i + 1] * ( i + 1 ) % mod;int ans = 0;for( int i = 0;i <= n;i ++ ) {if( i & 1 )ans = ( ans - C( n, i ) * qkpow( ( qkpow( k - 1, i ) * qkpow( k, n - i ) % mod - qkpow( k - 1, n ) + mod ) % mod, n ) % mod + mod ) % mod;elseans = ( ans + C( n, i ) * qkpow( ( qkpow( k - 1, i ) * qkpow( k, n - i ) % mod - qkpow( k - 1, n ) + mod ) % mod, n ) % mod ) % mod;} printf( "%lld", ans );return 0; }

T2：CF936C Lock Puzzle

戳一戳

solution

一般這種限制多少次以內就算成功的題目肯定是個構造題！！
觀察數據范圍$n\le 2000$，操作次數$\le 6100$
大膽猜想應該讓我們用$3\times n$的操作左右完成構造
即對于每一個字符最多只用$3$步就讓ta鎖定在我們想要ta在的位置

---

直接說正解吧
假設現在的$s$串長下列樣子

$AxBC$

$A,B,C$均為一個字符子串，$C$稍特殊一點，既是$s$串的后綴，同時要為$t$串的前綴，且最長
當然三個串可以為空
$x$為我們想移動的字符

現在目標是將$x$移動到$C$后面一個，即$Cx$構成一個新的$t$的前綴

---

操作①：$shiftlen(BC)$
原串變為 $C^{\prime }{B}^{\prime }Ax$

操作②：$shiftlen(1)$
繼續變為 $x{C}^{\prime }{B}^{\prime }A$

操作③：$shiftlen(n?1)$
成為 $A^{\prime }BCx$

我們只關心$Cx$是否一起出現在最后面，前面的$A$是否顛倒，不在乎滴

code

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 2005 int n, tot; char s[maxn], t[maxn]; int tot_s[maxn], tot_t[maxn], ans[maxn << 2];int main() {scanf( "%d %s %s", &n, s + 1, t + 1 );for( int i = 1;i <= n;i ++ )tot_s[s[i]] ++, tot_t[t[i]] ++;for( int i = 'a';i <= 'z';i ++ )if( tot_s[i] != tot_t[i] ) return ! printf( "-1\n" );int cnt = 0;for( int i = 1;i <= n;i ++ )if( s[i] == t[1] ) {bool flag = 1;for( int j = i;j <= n;j ++ )if( s[j] != t[j - i + 1] ) {flag = 0;break;}if( flag ) {cnt = n - i + 1;break;}}while( 1 ) {bool flag = 1;for( int i = 1;i <= n;i ++ )if( s[i] != t[i] ) {flag = 0;break;}if( flag ) break;int pos;for( int i = 1;i <= n - cnt;i ++ )if( s[i] == t[cnt + 1] ) {pos = i;break;}ans[++ tot] = n - pos;ans[++ tot] = 1;ans[++ tot] = n - 1;if( pos > 1 ) reverse( s + 1, s + pos );char temp = s[pos];for( int i = pos;i < n;i ++ )s[i] = s[i + 1]; s[n] = temp;cnt ++;}printf( "%d\n", tot );for( int i = 1;i <= tot;i ++ )printf( "%d ", ans[i] );return 0; }

總結

以上是生活随笔為你收集整理的[杂题训练]CF1228E Another Filling the Grid（容斥），CF936C Lock Puzzle（构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。