fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define mod 1000000007
  6.  
  7. int n,p,q;
  8. char x[2005],y[2005];
  9. char f[2005][6];
  10. int ex[2005];
  11. ll dp[2005];
  12. ll dp2[2005][2005];
  13. int c[2005][2005];
  14. vector<int>num;
  15. ll rec(int i,int j)
  16. {
  17. 	if(dp2[i][j]>=0) return dp2[i][j];
  18. 	if(j==0) return dp2[i][j] = 1;
  19. 	if(i>=num.size()) return dp2[i][j] = 0;
  20. 	return dp2[i][j] = (1LL*num[i]*rec(i+1,j-1) + rec(i+1,j)) %mod;
  21. }
  22. int main()
  23. {
  24. 	scanf("%d %d %d",&n,&p,&q);
  25. 	for(int i=0;i<n;i++) scanf(" %c",&x[i]);
  26. 	for(int i=0;i<n;i++) scanf(" %c",&y[i]);
  27. 	for(int i=0;i<n;i++) scanf("%s",&f[i]);
  28. 	for(int i=0;i<n;i++) for(int j=0;j<5;j++) ex[i]+=(f[i][j]!='.');
  29. 	dp[0]=1;
  30. 	for(int i=0;i<n;i++)
  31. 	{
  32. 		if(x[i] == y[i])
  33. 		{
  34. 			for(int j=2003;j>=0;j--)
  35. 			{
  36. 				dp[j] = (dp[j]*(ex[i]-1)+(j?dp[j-1]:0))%mod;
  37. 			}
  38. 		}
  39. 		else
  40. 		{
  41. 			num.push_back(ex[i]-2);
  42. 		}
  43. 	}
  44. 	memset(dp2,-1,sizeof(dp2));
  45. 	for(int i=0;i<num.size();i++)
  46. 	{
  47. 		for(int j=0;j<=n;j++)
  48. 		{
  49. 			if(dp2[i][j] >= 0) continue;
  50. 			dp2[i][j] = rec(i,j);
  51. 		}
  52. 	}
  53. 	for(int i=0;i<=2000;i++)
  54. 	{
  55. 		for(int j=0;j<=i;j++)
  56. 		{
  57. 			if(j==0 || j==i) c[i][j]=1;
  58. 			else c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
  59. 		}
  60. 	}
  61. 	ll res = 0;
  62. 	for(int i=0;i<=min(p,q);i++)
  63. 	{
  64. 		int pp = p-i;
  65. 		int qq = q-i;
  66. 		int ot = num.size()-pp-qq;
  67. 		if(ot<0) continue;
  68. 		res = (res+(dp2[0][ot]*dp[i])%mod*c[pp+qq][pp])%mod;
  69. 	}
  70. 	printf("%lld\n",res);
  71. }
Success #stdin #stdout 0.04s 50496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/bU7o6J
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!