首页 > 代码库 > (UVA)11916 Emoogle Grid
(UVA)11916 Emoogle Grid
题意:一个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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。