數論綜合訓練

• Magic Pairs
• • problem
  • solution
  • code
• CF107D Crime Management
• • problem
  • solution
  • code
• UVA12183 Top Secret
• • problem
  • solution
  • code
• P3746 [六省聯考2017]組合數問題
• • problem
  • solution
  • code

Magic Pairs

problem

已知$A_{0}x+B_{0}y\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$恒成立

求所有滿足$Ax+By\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$成立的$(A,B)$數量，$0\le A,B<N$?

solution

既然$A_{0}x+B_{0}y\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$都已經成立了

那么$2A_{0}x+2B_{0}y\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$?也同樣成立

換言之$k{A}_{0}x+k{B}_{0}y\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$??都成立

無腦倍加，還對$A,B$劃了范圍，肯定是會有周期循環的

注意$A_0,B_0$要先模一下$n$?

code

#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector < pair < int, int > > ans;int main() {int n, a0, b0;scanf( "%d %d %d", &n, &a0, &b0 );a0 %= n, b0 %= n;int a = a0, b = b0;do {ans.push_back( make_pair( a, b ) );a = ( a + a0 ) % n;b = ( b + b0 ) % n;}while( a != a0 || b != b0 );sort( ans.begin(), ans.end() );printf( "%d\n", ans.size() );for( int i = 0;i < ans.size();i ++ )printf( "%d %d\n", ans[i].first, ans[i].second );return 0; }

CF107D Crime Management

problem

solution

設$li{m}_i:i$字符所有限制之積

所有cnt相乘小于等于123，換言之：如果枚舉每個字符$i$的出現次數取模$li{m}_i$，哈希的總狀態數不超過$123$

取模后的狀態轉移是固定的，現在$i$出現了$j$次，那么下一個狀態$(j+1)\%li{m}_i$就可以設為$1$?（可以轉移過去）

與長度無關，因此可以矩陣加速

但最后第一行的哪些答案是符合條件的，就還需要一次dfs，確定對于每一個$i$枚舉的長度都必須至少是一個限制的倍數

到最后一層的時候，就去調用哈希字符串對應的編號，在矩陣中進行查詢，累加到答案上

code

#include <map> #include <cstdio> #include <vector> #include <cstring> using namespace std; #define mod 12345 #define int long long vector < int > G[27]; int n, m, cnt, ret; int lim[27];struct matrix {int c[125][125];matrix() { memset( c, 0, sizeof( c ) ); }int * operator [] ( int i ) { return c[i]; }matrix operator * ( matrix &t ) const {matrix ans;for( int i = 1;i <= 123;i ++ )for( int j = 1;j <= 123;j ++ )for( int k = 1;k <= 123;k ++ )ans[i][j] = ( ans[i][j] + c[i][k] * t[k][j] ) % mod;return ans;} }g;matrix qkpow( matrix x, int y ) {matrix ans;for( int i = 1;i <= 123;i ++ )ans[i][i] = 1;while( y ) {if( y & 1 ) ans = ans * x;x = x * x;y >>= 1;}return ans; }struct node {int cnt[27];node() { memset( cnt, 0, sizeof( cnt ) ); }bool operator < ( const node &t ) const {for( int i = 1;i <= 26;i ++ )if( cnt[i] == t.cnt[i] ) continue;else return cnt[i] < t.cnt[i];return 0;} }h;map < node, int > mp;void dfs( int x, node s ) {if( x > 26 ) {mp[s] = ++ cnt;return;}if( ! lim[x] ) dfs( x + 1, s );for( int i = 0;i < lim[x];i ++ ) {s.cnt[x] = i;dfs( x + 1, s );} }void calc( int x, node s ) {if( x > 26 ) {ret = ( ret + g[1][mp[s]] ) % mod;return;}if( ! lim[x] ) calc( x + 1, s );for( int i = 0;i < lim[x];i ++ ) {for( auto j : G[x] )if( i % j == 0 ) goto next;continue;next :s.cnt[x] = i;calc( x + 1, s );} }signed main() {scanf( "%lld %lld", &n, &m );if( ! n ) return ! printf( "1\n" );if( ! m ) return ! printf( "0\n" );for( int i = 1;i <= m;i ++ ) {char ch; int x, c;scanf( "\n%c %lld", &ch, &x );c = ch - 'A' + 1;if( ! lim[c] ) lim[c] = x;else lim[c] *= x;G[c].push_back( x ); }dfs( 1, h );for( map < node, int > :: iterator it = mp.begin();it != mp.end();it ++ ) {int id = it -> second; node now = it -> first;for( int i = 1;i <= 26;i ++ ) {if( ! lim[i] ) continue;node t = now;t.cnt[i] = ( now.cnt[i] + 1 ) % lim[i];g[id][mp[t]] ++;}}g = qkpow( g, n );calc( 1, h );printf( "%lld\n", ret );return 0; }

UVA12183 Top Secret

problem

$N$個數排成一圈，一次操作為，每個位置的數$+=L\times$左$+R\times$右，保留$x$為整數

問$S$輪操作后每個位置的值

$N<=1000,S<=2^{30},x<=9$?

solution

非常標準的矩乘轉移加速題干

但是發現$n$?級別在$1e3$?，矩乘是$n^3$的復雜度，也就是說常規的矩乘不足以通過這道題

發現轉移矩陣的每一行相當于上一行進行右移$1$位，這種特殊的矩陣稱之為循環矩陣

只需要計算第一行的加速矩陣，然后每一行都可以根據一定的公示在第一行進行查找

code

#include <cstdio> #include <cstring> #define maxn 1005 #define int long long int n, s, l, r, x, mod, T; int ret[maxn], h[maxn];struct matrix {int n;int c[2][maxn];void clear() { memset( c, 0, sizeof( c ) ); }matrix() { clear(); }int * operator [] ( int i ) { return c[i]; }matrix operator * ( matrix &t ) const {matrix ans; ans.n = n;for( int k = 1;k <= n;k ++ )for( int j = 1;j <= n;j ++ ) {int i = ( j - k + 1 + n ) % n;if( ! i ) i = n;ans[1][j] = ( ans[1][j] + c[1][k] * t[1][i] ) % mod;}return ans;} }g;matrix qkpow( matrix x, int y ) {matrix ans; ans.n = x.n; ans[1][1] = 1;while( y ) {if( y & 1 ) ans = ans * x;x = x * x;y >>= 1;}return ans; }signed main() {scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld %lld %lld %lld", &n, &s, &l, &r, &x );mod = 1;for( int i = 1;i <= x;i ++ )mod = ( mod << 3 ) + ( mod << 1 );g.clear(); g.n = n;for( int i = 1;i <= n;i ++ )scanf( "%lld", &h[i] ), ret[i] = 0;g[1][1] = 1, g[1][n] = l, g[1][2] = r;g = qkpow( g, s );for( int k = 1;k <= n;k ++ )for( int i = 1;i <= n;i ++ ) {int j = ( k - i + 1 + n ) % n;if( ! j ) j = n;ret[i] = ( ret[i] + g[1][j] * h[k] ) % mod;}for( int i = 1;i < n;i ++ )printf( "%lld ", ret[i] );printf( "%lld\n", ret[n] );}return 0; }

P3746 [六省聯考2017]組合數問題

problem

solution

設$f_{i,j}:$ 前$i$個物品選擇物品數量取模$k$為$j$的方案數

$f_{i,j}=f_{i?1,j}+f_{i?1,(j?1+k)\%k}$

$i$的轉移只跟$i?1$有關，且$j$的轉移也是固定的

可以矩乘加速

code

#include <cstdio> #include <cstring> using namespace std; #define int long long #define maxn 50 int n, p, K, r; struct matrix {int c[maxn][maxn];matrix() {memset( c, 0, sizeof( c ) );}int * operator [] ( int i ) {return c[i];}matrix operator * ( matrix &t ) const {matrix ans;for( int i = 0;i < K;i ++ )for( int j = 0;j < K;j ++ )for( int k = 0;k < K;k ++ )ans[i][j] = ( ans[i][j] + c[i][k] * t[k][j] ) % p;return ans;} }ret, g;matrix qkpow( matrix x, int y ) {matrix ans;for( int i = 0;i < K;i ++ )ans[i][i] = 1;while( y ) {if( y & 1 ) ans = ans * x;x = x * x;y >>= 1;}return ans; }signed main() {scanf( "%lld %lld %lld %lld", &n, &p, &K, &r );ret[0][0] = 1;for( int i = 0;i < K;i ++ )g[i][i] ++, g[i][( i - 1 + K ) % K] ++;g = qkpow( g, n * K );ret = ret * g;printf( "%lld\n", ret[0][r] );return 0; }

總結

以上是生活随笔為你收集整理的数论四之综合训练——Magic Pairs，Crime Management，Top Secret，组合数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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