HDU 5965 扫雷
传送门:http://acm.split.hdu.edu.cn/showproblem.php?pid=5965
题解
很明显确定前两列的状态就可以确定全部列填的状态了。
对于某一列如果只填一个,那么可以有两种填法,那么这种状态的方案数*2
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
//while(true) RP++; #include<cstdio> #include<cstring> #define LL long long #define Mod 100000007 using namespace std; const int Maxn=10000; LL Ans; int num[Maxn+5]; char str[Maxn+5]; int n; LL dfs(int pos,int s1,int s2){ if (pos==n){ if (s1+s2==num[pos]) return 1LL; else return 0LL; } if (s1+s2<=num[pos]){ int cho=num[pos]-s1-s2; if (cho>2 || cho<0) return 0LL; return (dfs(pos+1,s2,cho)*(cho==1?2LL:1LL))%Mod; }else{ return 0LL; } } inline void solve(int T){ scanf("%s",str); n=strlen(str); for (int i=1;i<=n;i++) num[i]=str[i-1]-'0'; if (n==1){ if (num[n]==1){ printf("2\n"); return; } if (num[n]==0 || num[n]==2){ printf("1\n"); return ; } printf("0\n"); return ; } Ans=0; for (int fs=0;fs<=2;fs++) for (int ss=0;ss<=2;ss++){ LL tim=1; if (fs==1) tim*=2LL; if (ss==1) tim*=2LL; if (fs+ss!=num[1]) continue; Ans = (Ans + tim*dfs(2,fs,ss)%Mod)%Mod; } printf("%I64d\n",Ans); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |

原文链接:HDU 5965 扫雷
WNJXYKの博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!