zoj 3791 An Easy Game dp
An Easy Game
Time Limit: 2 Seconds Memory Limit: 65536 KB
One day, Edward and Flandre play a game. Flandre will show two 01-strings s1 and s2, the lengths of two strings are n. Then, Edward must move exact k steps. In each step, Edward should change exact m positions of s1. That means exact m positions of s1, '0' will be changed to '1' and '1' will be changed to '0'.
The problem comes, how many different ways can Edward change s1 to s2 after k steps? Please calculate the number of the ways mod 1000000009.
Input
Input will consist of multiple test cases and each case will consist of three lines. The first line of each case consist of three integers n (1 ≤ n ≤ 100), k (0 ≤ k ≤ 100), m (0 ≤ m ≤ n). The second line of each case is a 01-string s1. The third line of each case is a 01-string s2.
Output
For each test case, you should output a line consist of the result.
Sample Input
3 2 1
100
001
Sample Output
2
Hint
100->101->001
100->000->001
题目大意:给两个01字符串s1,s2,经过K次操作每次对M个取反,求有多少种方案使得s1==s2。 dp[i][j]表示i次操作之后有j个位置不同的方法数,答案就是dp[t][0]。对于dp[i - 1][j],经过一次操作之后假设把t个位置从不同变为相同,剩下m - t个位置从相同变为不同。
那么dp[i][j + m - t - t] += dp[i - 1][j] * C(j, t) * C(n - j, m - t)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; typedef __int64 LL;
const int maxn=;
const int Mod=;
int n,k,m,C[maxn][maxn];
LL d[maxn][maxn];
char s1[maxn],s2[maxn]; int max(int a,int b){return a>b?a:b;} void init_C()
{
memset(C,,sizeof(C));
int i,j;
for(i=;i<=;i++)
{
C[i][]=;
for(j=;j<=i;j++)
{
C[i][j]=(C[i-][j-]+C[i-][j])%Mod;
}
}
} void solve()
{
memset(d,,sizeof(d));
int i,j,t,dif=;
for(i=;i<n;i++) dif+=(s1[i]!=s2[i]?:);
d[][dif]=;
for(i=;i<=k;i++)
{
for(j=;j<=n;j++)
{
for(t=max(,m-(n-j));t<=j && t<=m;t++)
{
d[i][j+m-t-t]=(d[i][j+m-t-t]+d[i-][j]*C[j][t]%Mod*C[n-j][m-t]%Mod)%Mod;
}
}
}
printf("%I64d\n",d[k][]);
}
int main()
{
init_C();
while(~scanf("%d %d %d",&n,&k,&m))
{
getchar();
gets(s1);
gets(s2);
solve();
}
return ;
}
最新文章
- 【转】sql to_char 日期转换字符串
- Linux老是提示compat-libstdc++ is not installed的原因
- javascript日历控件——纯javascript版
- 开源一个基于nio的java网络程序
- iOS支付宝集成详细流程
- G面经prepare: Friends Recommendation
- C常用字符字符串处理函数
- 性能调优之SQL优化
- ajax的4个字母分别是什么意思
- 初识docker
- Javascript高级编程学习笔记(82)—— 富文本操作(2)
- matlab练习程序(局部加权线性回归)
- mybatis之批量插入
- Python oracle乱码问题
- (21)The history of human emotions
- centos7环境下对防火墙的操作
- JSTL标签 使用总结,foreach
- Zabbix安装(debian,centos)
- 浅谈c++中map插入数据的用法
- 【转】vc api 录音