題意:
在一個M*N的矩陣內塗K種顏色。
其中有B個格子不能塗色,並且每個單元格不能和上面的那個單元格顏色一樣。
已知N和總共的結果R,求最少滿足的行M。
數據都對100,000,007.取模。
思路:
由於輸入的不能塗色的點的X坐標一定在M以內。所以就記錄一下maxX
把整個矩陣分成3個部分。
第一個部分是maxX*N.這部分的答案可以算出來看是否滿足。
第二個部分是(maxX+1)*N.這個部分都是多了一行,為了去掉有些格子不能填帶來的影響。
第三個部分就是M*N了,後面的(M-maxX-1)行每個格子填的顏色都是只有K-1種。
這時候設前面的答案為ans,設M-maxX-1=T
則 ans*(K-1)^(T*N) = R (mod 100000007)
這時候其實就需要求一個 A^X=B (mod M) 時的X
需要用一個枚舉的方法。
代碼:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" #include"map" #define ll long long using namespace std; int mark[502][502]; mapid; ll mod=100000007; int n,k,b,idcnt,maxx,maxcnt; ll r; ll power(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b/=2; } return ans%mod; } ll inv(ll x) { return power(x,mod-2); } ll log_mod(ll a,ll b) { ll m,v,e=1,i; m=(ll)sqrt(mod+0.5); v=inv(power(a,m)); map x; x.clear(); x[1]=0; for(i=1;i =mod) e%=mod; if(x[e]==0) x[e]=i; } for(i=0;i =mod) b%=mod; } return -1; } int solve() { //1~maxx ll ans=1; if(maxx!=0) { for(int i=1;i<=idcnt;i++) { int cur=0; mark[i][++mark[i][0]]=maxx+1; for(int j=1;j<=mark[i][0];j++) { int sum=mark[i][j]-cur-1; cur=mark[i][j]; if(sum==0) continue; ans*=k; if(ans>=mod) ans%=mod; ans*=power(k-1,sum-1); if(ans>=mod) ans%=mod; } } ans*=power(k,n-idcnt); if(ans>=mod) ans%=mod; ans*=power(k-1,(maxx-1LL)*(n-idcnt)); if(ans>=mod) ans%=mod; if(ans==r) return maxx; } //maxx+1 ans*=power(k,maxcnt); if(ans>=mod) ans%=mod; ans*=power(k-1,n-maxcnt); if(ans>=mod) ans%=mod; if(ans==r) return maxx+1; ll tep=inv(ans); ll A,B; B=(tep*r)%mod; A=power(k-1,n); return log_mod(A,B)+maxx+1; } int main() { int t,cas=1; cin>>t; while(t--) { scanf("%d%d%d%lld",&n,&k,&b,&r); memset(mark,0,sizeof(mark)); id.clear(); idcnt=0; maxx=0; maxcnt=n; for(int i=0;imaxx) { maxx=x; maxcnt=1; } else if(x==maxx) maxcnt++; } printf("Case %d: %d\n",cas++,solve()); } return 0; }