首页 > 代码库 > (UVA)11916 Emoogle Grid

(UVA)11916 Emoogle Grid

2024-08-11 05:28:53   221人阅读

题意：一个N列的网格，有B个格子可以不涂色，其他格子各涂一种颜色，现在一共有k种颜色，要求同一列格子颜色不能相同，问总方案数 MOD 100000007答案等于R时最小的M是多少。

思路：首先这个m一定是大于等于所给的不能放的点的x的最大值。我们可以先统计出当前矩阵的方案数，我们知道如果当前格子上面能放东西，当前格子的方案数是k-1,否则就是k种，然后乘法原理，所以先判断下当前的m是否符合，然后不符合的情况下，再加一层，再判断下，算出当前答案cnt，你再往下加层数的时候情况是一样的，都是cnt*(（k-1）^n);然后就转换成

求cnt*(（k-1）^(n*t))%mod = r;然后大步小步算出t的最小值再加上原来m就是答案，复杂度（sqrt(mod)）；

  1 #include<stdio.h>  2 #include<algorithm>  3 #include<stdlib.h>  4 #include<iostream>  5 #include<queue>  6 #include<math.h>  7 #include<map>  8 #include<vector>  9 #include<string.h> 10 #include<set> 11 typedef long long LL; 12 using namespace std; 13 typedef struct pp { 14         int x; 15         int y; 16 } ss; 17 ss ans[100005]; 18 ss bns[100005]; 19 set<pair<int,int> >vec; 20 const  LL mod = 100000007; 21 bool cmp(pp p, pp q) { 22         if(p.x == q .x) 23                 return p.y < q.y; 24         return p.x < q.x; 25 } 26 LL coutt(int m,int n,int b,int k); 27 LL quick(LL n, LL m); 28 LL solve(int n,int m,int b,int k,int r); 29 LL BSS(LL kk,LL k,LL cnt,LL n); 30 int er(int n,int m,LL fin); 31 ss cn[100005]; 32 int main(void) { 33         int T; 34         int __ca = 0; 35         scanf("%d",&T); 36         while(T--) { 37                 __ca++; 38                 int  n, k, b,r; 39                 vec.clear(); 40                 scanf("%d %d %d %d",&n,&k,&b,&r); 41                 int i,j; 42                 int  m = 1; 43                 for(i = 0 ; i  < b; i++) { 44                         scanf("%d %d",&ans[i].x,&ans[i].y); 45                         if(ans[i].x > m)m = ans[i].x; 46                         pair<int,int>ac = make_pair(ans[i].x,ans[i].y); 47                         // printf("%d %d\n",ans[i].x,ans[i].y); 48                         vec.insert(ac); 49                 } 50                 printf("Case %d: %lld\n",__ca,solve(n,m,b,k,r)); 51         } 52         return 0; 53 } 54 LL coutt(int m,int n,int b,int k) { 55         LL sum = 0; 56         for(int i = 0; i < b; i++) {//printf("%d\n",ans[i].x); 57                 if(ans[i].x != m&& !vec.count(make_pair(ans[i].x+1,ans[i].y))) 58                         sum++; 59                 if(ans[i].x == 1) { 60                         sum--; 61                 } 62         } 63         sum += n; 64         LL dt = quick((LL)k,sum)%mod; 65         dt =  dt*quick((LL)(k-1),(LL)m*(LL)n-b-sum)%mod; 66         return dt % mod; 67 } 68 LL quick(LL n, LL m) { 69         LL ask = 1; 70         n %= mod; 71         while(m) { 72                 if(m&1) 73                         ask =  ask*n %mod; 74                 n = n*n %mod; 75                 m>>=1; 76         } 77         return ask ; 78 } 79 LL solve(int n,int m,int b,int k,int r) { 80         LL cnt = coutt(m,n,b,k); 81         if(cnt == r) 82                 return (LL)m; 83         int i,j; 84         int ac = 0; 85         for(i = 0; i < b; i++) { 86                 if(ans[i].x == m) { 87                         ac++ ; 88                 } 89         } 90         //printf("%lld\n",cnt); 91         m++; 92         LL ak = quick((LL)k,ac); 93         cnt = cnt *ak %mod; 94         ak = quick((LL)(k-1),n-ac); 95         cnt = cnt *ak%mod; 96         if(cnt == r) 97                 return (LL)m; 98         LL tp = quick((LL)(k-1),n); 99         LL kk = (LL)r;100         return (m+BSS(kk,(LL)k,cnt,n))%mod;101 }102 LL BSS(LL kk,LL k,LL cnt,LL n) {103         int i,j;104         LL ni = quick(cnt,mod-2);105         kk = kk*ni%mod;106         LL ak = quick(k-1,n)%mod;107         LL modd = sqrt(1.0*mod);108         LL ac = kk;109         LL nii = quick(ak,mod-2);110         for(i = 0; i < modd; i++) {111                 bns[i].x = ac;112                 bns[i].y = i;113                 ac = ac*nii%mod;114         }115 116         sort(bns,bns+modd,cmp);117         int cnn = 1;118         cn[0] = bns[0];119         int c = bns[0].x;120         for(i = 1; i <modd; i++) {121                 if(c!=bns[i].x) {122                         c=bns[i].x;123                         cn[cnn]=bns[i];124                         cnn++;125                 }126         }127         LL akk = 1;128         LL app = quick(ak,modd);129         for(i = 0; i <= modd+1; i++) {130                 int ack = er(0,cnn,akk);131                 if(ack!=-1) {   //printf("%d %lld\n",i,ack);132                         return modd*(LL)i+(LL)ack;133                 }134                 akk = akk*app%mod;135         }136 }137 int er(int n,int m,LL fin) {138         if(n>m)139                 return -1;140         int mid = (n+m)/2;141         if(cn[mid].x == fin) {142                 return cn[mid].y;143         } else if(cn[mid].x > fin) {144                 return er(n,mid-1,fin);145         } else return er(mid+1,m,fin);146 }

 

(UVA)11916 Emoogle Grid


联系
我们