uva11916(数学题，模方程)

2019-04-13 17:14发布

站内文章 / 模拟电子
9191 0 1571
  题目的意思是有M*N列的格子，K种颜 {MOD}，B个不能涂 {MOD}的格子，涂 {MOD}的约束条件是每一列相连的格子上不能是相同的颜 {MOD}，然后总数Mod100000007的结果是等于R的，现在题目中告诉N，K，B，R，要求满足条件的最小M。   解答：根据B个格子的坐标，可以求出最小的行minM，然后求对于minM*N的格子有多少种方案，然后再往外扩展一行，又有多少种方案，假设求得Mod完之后的结果为a，那么往后每添加一行，方案是当前的(k-1)^N次倍，即要求下面的方程解的最小值。   ≡    转化一下就是a^x ≡ b(Mod n)的模型   #include "stdio.h" #include "string.h" #include "math.h" #include #include #include #include #include #include #include using namespace std; #define MAXM 1 #define MAXN 1 #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define Mem(a,b) memset(a,b,sizeof(a)) double pi = acos(-1.0); double eps = 1e-6; typedef struct{ int f,t,w,next; }Edge; Edge edge[MAXM]; int head[MAXN]; int kNum; typedef long long LL; LL Mod = 100000007; void addEdge(int f, int t, int w) { edge[kNum].f = f; edge[kNum].t = t; edge[kNum].w = w; edge[kNum].next = head[f]; head[f] = kNum ++; } LL N, K, R, B; int T; typedef struct{ int x, y; }BL; BL bl[505]; bool comp(BL a, BL b){ if( a.y == b.y ) return a.x < b.x; return a.y < b.y; } LL pow_mod(LL a, LL m){ if( m == 0 ) return 1; LL ans = pow_mod(a, m/2) % Mod; ans = ans * ans % Mod; if( m % 2 ) ans = ans * a % Mod; return ans; } void exgcd(LL a, LL b, LL &d, LL &x, LL &y){ if( !b ){ x = 1, y = 0; d = a; } else{ exgcd(b, a % b, d, y, x); y -= x * ( a / b ) ; } } //求a在mod n下的逆 LL inv(LL a){ LL x, y, d; exgcd(a, Mod, d, x, y); return d == 1 ? (x + Mod) % Mod : -1; } //求解a^x = b(mod n) LL log_mod(LL a, LL b){ LL m, v, e = 1; m = (LL)sqrt(Mod + 0.5); v = inv(pow_mod(a,m)); map x; x[1] = 0; for(int i = 1; i < m; i ++){ e = e * a % Mod; if( !x.count(e) ) x[e] = i; } for(int i = 0; i < m; i ++){ if( x.count(b) ) return i * m + x[b]; b = b * v % Mod; } return -1; } void solve(){ int minM = 1; for(int i = 0; i < B; i ++){ scanf("%d %d", &bl[i].x, &bl[i].y); if( minM < bl[i].x ) minM = bl[i].x; } sort(bl, bl + B, comp); R = R % Mod; LL ans = 1, powK1 = N; for(int i = 0; i < B; i ++){ if( bl[i].x == 1 ) powK1 --; if( bl[i].x != minM ){ if( i + 1 < B && bl[i+1].y == bl[i].y){ if( bl[i].x + 1 != bl[i+1].x ){ powK1 ++; } } else{ powK1 ++; } } } ans = ans * pow_mod(K, powK1) % Mod; ans = ans * pow_mod(K-1, minM * N - powK1 - B) % Mod; if( ans == R ){ printf("%d ", minM); return; } powK1 = 0; for(int i = 0; i < B; i ++){ if( bl[i].x == minM ){ powK1 ++; } } ans = ans * pow_mod(K, powK1) % Mod; ans = ans * pow_mod(K-1, N - powK1) % Mod; if( ans == R ){ printf("%d ", minM + 1); return; } // LL x, y, d; // exgcd(ans, Mod, d, x, y); LL x = inv(ans) * R % Mod; // x = ( x * R + Mod * Mod ) % Mod; ans = pow_mod(K-1, N) % Mod; printf("%d ", log_mod(ans, x) + minM + 1 ); } int main() { // freopen("d:\test.txt", "r", stdin); while(cin>>T){ for(int i = 0; i < T; i ++){ cin>>N>>K>>B>>R; printf("Case %d: ", i + 1); solve(); } } return 0; }

热门文章