23 条题解
-
2
zone LV 10 @ 2016-08-08 14:09:23
#include <iostream> #include <cstring> #include <bitset> using namespace std; typedef long long lg; //#define OPENFILE #define ll lg lg f[2][1<<9][81],w=0; lg n,k,m; lg st[1<<9],sum[100],cnt=0,ans=0; int r[10000]; inline int o(int n){return (n+1)&1;} inline lg gcd(lg a,lg b){return b==0?a:gcd(b,a%b);} void c(lg a,lg b) { lg res=1,k,re=1; for(int i=2;i<=a;i++) res*=i; for(int i=b;i>b-a;i--) { re*=i; k=gcd(re,res); res/=k; re/=k; } k=gcd(ans,re); ans/=k; re/=k; cout<<re<<"/"<<ans*res; } int main(int argc, char** argv) { # ifdef OPENFILE freopen("data.in","r",stdin); # endif ios::sync_with_stdio(0); cin>>n>>m>>k; if(n<m) { n=n^m; m=n^m; n=n^m; } int all=(1<<m)-1; for(int i=0;i<=all;i++) if(!(i&(i>>1))) { st[++cnt]=i; bitset<16>tt(i); sum[cnt]=tt.count(); f[w][cnt][sum[cnt]]=1; } for(int i=2;i<=n;i++) { w=o(w); memset(f[w],0,sizeof f[w]); for(int j=1;j<=cnt;j++) for(int c=1;c<=cnt;c++) if(!(st[j]&st[c])) { for(int t=0;t<=k-sum[j];t++) f[w][j][t+sum[j]]+=f[o(w)][c][t]; } } for(int i=1;i<=cnt;i++) ans+=f[w][i][k]; if(ans) c(k,n*m); else cout<<"Impossible!"; return 0; } -
1
#include<cstdio>
using namespace std;
const bool b[513]={true,true,true,false,true,true,false,false,true,true,true,false,false,false,false,false,true,true,true,false,true,true,false,false,false,false,false,false,false,false,false,false,true,true,true,false,true,true,false,false,true,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,true,true,false,true,true,false,false,true,true,true,false,false,false,false,false,true,true,true,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,true,true,false,true,true,false,false,true,true,true,false,false,false,false,false,true,true,true,false,true,true,false,false,false,false,false,false,false,false,false,false,true,true,true,false,true,true,false,false,true,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false};
const int sl[513]={0,1,1,0,1,2,0,0,1,2,2,0,0,0,0,0,1,2,2,0,2,3,0,0,0,0,0,0,0,0,0,0,1,2,2,0,2,3,0,0,2,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,0,2,3,0,0,2,3,3,0,0,0,0,0,2,3,3,0,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,0,2,3,0,0,2,3,3,0,0,0,0,0,2,3,3,0,3,4,0,0,0,0,0,0,0,0,0,0,2,3,3,0,3,4,0,0,3,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
double f[2][513][21];
int n,m,k;
double ccc(int x,int y)
{
double c=1,d=1;
for(int i=1;i<=x;i++) c*=i;
for(int i=y;i>=y-x+1;i--) d*=i;
return d/c;
}
long long gcd(long long a,long long b)
{
if (b==0) return a;
return gcd(b,a%b);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
if (m>n)
{
int t=n;
n=m;
m=t;
}
double anss1=ccc(k,n*m);
int ma=(1<<m)-1;
for(int i=0;i<=ma;i++)
if (b[i]&&sl[i]<=k)
f[1][i][sl[i]]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=ma;j++)
for(int s=0;s<=k;s++)
f[i%2][j][s]=0;
for(int s=0;s<=k;s++)
for(int j=0;j<=ma;j++)
if (b[j]&&sl[j]<=s)
for(int t=0;t<=ma;t++)
if ((j&t)==0&&b[t]&&sl[t]<=(s-sl[j]))
f[i%2][j][s]+=f[(i-1)%2][t][s-sl[j]];
}
double anss2=0;
for(int i=0;i<=ma;i++)
if (b[i])
anss2+=f[n%2][i][k];
if (anss2==0) printf("Impossible!");
else
{
long long tt=gcd((long long)anss1,(long long)anss2);
printf("%0.0lf/%0.0lf\n",anss1/tt,anss2/tt);
}
return 0;
}最后一个点WA了求大神看看。。
-
Independence @ 2017-08-09 10:43:05
你的做法，。。。。厉害
-
-
0
ljc20020730 LV 6 @ 2017-07-19 11:03:27
。
-
0
Accepted_upc LV 8 @ 2016-09-19 22:42:09
此题简直叼………………
```C++
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (1000 + 20)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;int state[100],cnt = 0,counts[100];
bool flag[100];
int gts[15];
int n,m,k;
LLI dp[200][2000][25];void dfs(int last,int p,int c) {
if(p >= m) {
int s = 0;
for(int i = 0; i < m; i ++) s = s * 2 + gts[i];
counts[cnt] = c;
state[cnt ++] = s;
return;
}
if(p - last > 1) {
gts[p] = 1;
dfs(p,p + 1,c + 1);
gts[p] = 0;
dfs(last,p + 1,c);
} else {
gts[p] = 0;
dfs(last, p + 1,c);
}
}LLI Com() {
LLI re = 1;
LLI x = n * m;
LLI y = min(n * m - k,k);
LLI z = max(n * m - k,k);
LLI p = 2;
for(int i = x; i >= z + 1; i --) {
re = re * i;
while(re % p == 0 && p <= y) {
re = re / p;
p ++;
}
}
return re;
}int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d%d",&n,&m,&k);
memset(flag,false,sizeof(flag));
if(m > n) swap(n,m);
dfs(-2,0,0);
memset(dp,0,sizeof(dp));
for(int j = 0; j < cnt; j ++) {
dp[1][j][counts[j]] ++;
}
for(int i = 1; i <= n; i ++)
for(int j = 0; j < cnt; j ++)
for(int l = 0; l < cnt; l ++)
if((state[j] & state[l]) == 0)
for(int k1 = 0; k1 <= k; k1 ++)
dp[(i + 1)][j][k1 + counts[j]] += dp[i][l][k1];
LLI re = 0;
for(int i = 0; i < cnt; i ++)
re += dp[n][i][k];
if(re == 0) printf("Impossible!\n");
else {
LLI p = Com();
LLI GCD = __gcd(re,p);
printf("%lld/%lld\n",p / GCD,re / GCD);
}
return 0;
}
```-
可以用
#include<bits/stdc++.h>
-
-
0
#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;int vnum,n,m,k;
LL ans;
LL f[81][60][21],vis[60],c[60];void Swap(int &x,int &y){
int t;
t=x;
x=y;
y=t;
}
int Check(int x){
int tot=0;
for(int i=0;i<m;i++)
if (x&(1<<i)) tot++;
return tot;
}
void Getvalidstate(){
for(int i=0;i<(1<<m);i++)
if (!(i&(i<<1))){
vis[++vnum]=i;
c[vnum]=Check(i);
}
}
LL Gcd(LL x,LL y){
if (y==0) return x;
else return Gcd(y,x%y);
}
/*void C(LL x,LL y){
LL x1,x2,p;
x1=1,x2=ans;
for(int i=y;i>=1;i--){
x1*=x;
x2*=i;
p=Gcd(x1,x2);
x1/=p;
x2/=p;
x--;
}
cout<<x1<<'/'<<x2<<endl;
}*/
void C(LL x,LL y){
LL x1,x2,p;
x1=x2=1;
for(int i=1;i<=y;i++)
x2*=i;
for(int i=1;i<=y;i++){
x1*=x;
p=Gcd(x1,x2);
x1/=p;
x2/=p;
p=Gcd(x1,ans);
x1/=p;
ans/=p;
x--;
}
x2*=ans;
p=Gcd(x1,x2);
x1/=p;
x2/=p;
cout<<x1<<'/'<<x2<<endl;
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
if (n<m) Swap(n,m);
vnum=0;
Getvalidstate();
f[0][1][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=vnum;j++)
for(int l=c[j];l<=k;l++)
for(int h=1;h<=vnum;h++)
if (!(vis[j]&vis[h])) f[i][j][l]+=f[i-1][h][l-c[j]];
ans=0;
for(int i=1;i<=vnum;i++)
ans+=f[n][i][k];
if (!ans) printf("Impossible!");
else C(n*m,k);
return 0;
} -
0
longlong足矣，状压dp+dp求组合数+gcd。。。这题数据太水了暴力80分。状压dp的数组没加longlong导致wa了好几次。。。
评测结果
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 6980 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 6980 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 6988 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 6984 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 6988 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 6988 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 6980 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 6988 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 6980 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 6980 KiB, score = 10
Accepted, time = 30 ms, mem = 6988 KiB, score = 100
-
0
jiaoyunhao LV 10 @ 2012-08-25 22:18:17
压位DP，不用高精
-
-2
razhangwei LV 3 @ 2008-11-04 08:11:22
我讲一点技巧，就是若n
zone
LV 10
@ 2016-08-08 14:09:23
