Uva1191————思维+bsgs算法

青旅半醒 2024-04-18 23:25 27阅读 0赞

[可以看这篇博客][Link 1]

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const ll Mod = 100000007;
    struct node
    { 
        ll x,y;
    };
    vector<node>v;
    bool cmp(node a, node b)
    { 
        if(a.y == b.y)return a.x < b.x;
        return a.y < b.y;
    }
    
    ll qpow(ll a, ll n, ll mod)
    { 
        ll ret = 1;
        while(n)
        { 
            if(n%2)ret = ret*a%mod;
            a = a*a%mod;
            n/=2;
        }
        return ret;
    }
    ll bsgs(ll a,ll b)
    { 
        ll m = (ll)sqrt(Mod+0.5);
        map<ll,ll> x;
        x[1] = 0;
        ll ans = 1;
        for(int i = 1; i <= m; i++)
        { 
            ans = ans*a%Mod;
            if(!x.count(ans)) x[ans] = i;
        }
        ll pm = qpow(qpow(a,m, Mod), Mod-2, Mod);// a^m 的逆
        for(int i = 0; i < m; i++)
        { 
            if(x.count(b)) return i*m+x[b];
            b = b*pm%Mod;
        }
    }
    
    void solve(ll &m, ll n, ll k, ll b,ll r)
    { 
        sort(v.begin(), v.end(), cmp);
        m = 1;
        for(int i = 0; i < b; i++)
        { 
            m = max(m, v[i].x);
        }
    
        ll k1 = n;// 能涂k中颜色块的个数
        ll cnt1 = 0;// 统计最后一行不能涂的个数
        for(int i = 0; i < b; i++)
        { 
            if(v[i].x == 1)k1--; // 如果是第一行 涂k种颜色的 减1
            if(v[i].x != m)// 如果不是最后一行可能会使得 涂k种颜色的加1
            { 
                if(i+1< b && v[i+1].y == v[i].y&&v[i].x+1 == v[i+1].x)//如果 下一个不涂颜色的和他在一行并且 他们两相邻 ， 这种情况k1 不加
                { 
                    //这种情况k1 不加
                }
                else k1++;
            }
            if(v[i].x == m)cnt1++;
    
    
        }
        ll ans = 1;
        ans = ans*qpow(k, k1, Mod);// 涂k种颜色块 所能产生的涂法
        ans = ans*qpow(k-1,n*m-k1- b,Mod)%Mod; // 涂k-1中颜色块 所能产生的涂法， 涂k-1种颜色块的数量 == 总块数 - 不能涂的块数 - 涂k种的块数
        if(ans == r)
        { 
            return;
        }
        m++;
        ans = ans*qpow(k, cnt1, Mod)%Mod;
        ans = ans*qpow(k-1,n-cnt1, Mod)%Mod;
        if(ans == r)
        { 
            return;
        }
        ll inv = qpow(ans, Mod-2, Mod);
        ll p = qpow(k-1, n, Mod);
        ll r2 = (inv*r)%Mod;
        ll add;
        add = bsgs(p, r2);
        m +=add;
        return;
    
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
        ll T,cnt(0);
        cin>>T;
        ll m, n, k, b, r;
    
        while(T--)
        { 
            cin>>n>>k>>b>>r;
            v.clear();
            for(int i = 0; i < b; i++)
            { 
                node tmp;
                cin>>tmp.x>>tmp.y;
                v.push_back(tmp);
            }
            solve(m, n, k, b, r);
            cout<<"Case "<<++cnt<<": "<<m<<endl;
        }
    
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/qingqiu_WD/article/details/75676133