UVA - 11916 Emoogle Grid (组合计数+离散对数)

时间:2022-07-31 11:34:16

假如有这样一道题目:要给一个M行N列的网格涂上K种颜色,其中有B个格子不用涂色,其他每个格子涂一种颜色,同一列中的上下两个相邻格子不能涂相同颜色。给出M,N,K和B个格子的位置,求出涂色方案总数除以1e8+7的结果R。

本题的任务和这个相反:已知N,K,R和B个格子的位置,求最小可能的M。

蓝书(大白)上的例题,设xm为不能涂色的格子的最大x值,则分三种情况讨论:M=xm,M=xm+1,M>xm+1。前两种用组合公式直接算,第三种可设前xm+1行的格子涂色方法有n种,由于每增加一行,总涂色方案数增加p=(k-1)^N,于是有n*p^(M-xm-1)=R,用BSGS算法求出M-xm-1的值即可得到答案。

中间有一个连乘少取了一次模爆了longlong,差点debug到自闭..

 #include<bits/stdc++.h>

 using namespace std;
typedef long long ll;
const ll N=+;
const ll mod=1e8+;
struct P {
ll x,y;
bool operator<(const P& b)const {return x!=b.x?x<b.x:y<b.y;}
};
ll n,k,b,r,ka;
ll x[N],y[N],xm,all;
set<P> st; ll Pow(ll a,ll b) {
ll ret=;
for(; b; b>>=,a=a*a%mod)if(b&)ret=ret*a%mod;
return ret;
}
ll inv(ll a) {return Pow(a,mod-);}
ll Log(ll a,ll b) {
ll m=sqrt(mod+0.5),v=inv(Pow(a,m));
map<ll,ll> mp;
for(ll i=,e=; i<m; ++i,e=e*a%mod)if(!mp.count(e))mp[e]=i;
for(ll i=; i<m; ++i,b=b*v%mod)if(mp.count(b))return i*m+mp[b];
return -;
} ll solve() {
ll ans=Pow(k,all)*Pow(k-,n*xm-all-b)%mod;
if(ans==r)return xm;
ll cnt=;
for(ll i=; i<b; ++i)if(x[i]==xm)++cnt;
ans=ans*Pow(k,cnt)%mod*Pow(k-,n-cnt)%mod;
if(ans==r)return xm+;
return xm++Log(Pow(k-,n),r*inv(ans)%mod);
} int main() {
ll T;
scanf("%lld",&T);
while(T--) {
printf("Case %lld: ",++ka);
xm=;
st.clear();
scanf("%lld%lld%lld%lld",&n,&k,&b,&r);
all=n;
for(ll i=; i<b; ++i) {
scanf("%lld%lld",&x[i],&y[i]);
xm=max(xm,x[i]);
st.insert({x[i],y[i]});
if(x[i]==)all--;
}
for(ll i=; i<b; ++i) {
if(x[i]!=xm&&!st.count({x[i]+,y[i]}))all++;
}
printf("%lld\n",solve());
}
return ;
}