设为首页 加入收藏

TOP

uva 11916 - Emoogle Grid(大步小步算法)
2015-07-24 05:45:48 来源: 作者: 【大 中 小】 浏览:4次
Tags：uva 11916 Emoogle Grid 大步 小步 算法

题目连接：uva 11916 - Emoogle Grid

题目大意：有一问题，在M行N列的网格上涂K种颜色，其中有B个格子不用涂色，其它每个格子涂一种颜色，同一列的上下两个相邻的格子不能涂相同的颜色。给出M，N，K和B个格子的位置，求出总方案数模掉1e8+7的结果R。现在已知R，求最小的M。

解题思路：有确定不用涂色格子的区域作为不变部分，总数通过计算为tmp，外加可变部分的第一行，方案数为cnt，可变部分除第一行外，每加一行都将总数乘以(K?1)N,既有

  • cnt?PM=Rmod(1e8+7)
  • PM=cnt?1?Rmod(1e8+7)
    就是大步小步算法求M。 
    #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            using namespace std; typedef long long ll; const ll MOD = 1e8+7; const int maxn = 505; int N, M, K, R, B, X[maxn], Y[maxn]; set
           
             > bset; inline ll mul_mod (ll a, ll b) { return (ll)a * b % MOD; } inline ll pow_mod (ll a, ll n) { ll ans = 1; while (n) { if (n&1) ans = mul_mod(ans, a); a = mul_mod(a, a); n /= 2; } return ans; } void gcd (ll a, ll b, ll& d, ll& x, ll& y) { if (!b) { d = a; x = 1; y = 0; } else { gcd (b, a%b, d, y, x); y -= x * (a/b); } } inline ll inv (ll a) { ll d, x, y; gcd(a, MOD, d, x, y); return d == 1 ? (x+MOD)%MOD : -1; } void init () { scanf("%d%d%d%d", &N, &K, &B, &R); bset.clear(); M = 1; for (int i = 0; i < B; i++) { scanf("%d%d", &X[i], &Y[i]); M = max(M, X[i]); bset.insert(make_pair(X[i], Y[i])); } } int count () { int c = 0; for (int i = 0; i < B; i++) { if (X[i] != M && !bset.count(make_pair(X[i]+1, Y[i]))) c++; } c += N; for (int i = 0; i < B; i++) if (X[i] == 1) c--; return mul_mod(pow_mod(K, c), pow_mod(K-1, (ll)M*N-B-c)); } int log_mod (ll a, ll b) { ll m = (ll)sqrt(MOD+0.5), v, e = 1; v = inv(pow_mod(a, m)); map
            
              g; g[1] = 0; for (ll i = 1; i < m; i++) { e = mul_mod(e, a); if (!g.count(e)) g[e] = i; } for (ll i = 0; i < m; i++) { if (g.count(b)) return i*m+g[b]; b = mul_mod(b, v); } return -1; } int doit () { int cnt = count(); if (cnt == R) return M; int c = 0; for (int i = 0; i < B; i++) if (X[i] == M) c++; M++; cnt = mul_mod(cnt, pow_mod(K, c)); cnt = mul_mod(cnt, pow_mod(K-1, N-c)); if (cnt == R) return M; return log_mod(pow_mod(K-1, N), mul_mod(R, inv(cnt))) + M; } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init(); printf("Case %d: %d\n", i, doit()); } return 0; }
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：uva 11754 - Code Feat(中国剩余.. 下一篇：SPOJ 694、705 Distinct Substrin..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: