题目传送门

 /*
题意:转换就是求n位数字,总和为s/2的方案数
DP+高精度:状态转移方程:dp[cur^1][k+j] = dp[cur^1][k+j] + dp[cur][k];
高精度直接拿JayYe的:)
异或运算的规则:
0⊕0=0,0⊕1=1
1⊕0=1,1⊕1=0
口诀:相同取0,相异取1
*/
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std; const int numlen = ;
const int numbit = ;
const int addbit = ;
const int maxn = numlen/numbit + ; struct bign {
int len, s[numlen];
bign() {
memset(s, , sizeof(s));
len = ;
}
bign(int num) { *this = num; }
bign(const char *num) { *this = num; }
bign operator = (const int num) {
char s[numlen];
sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator = (const char *num){
int clen = strlen(num);
while(clen > && num[] == '') num++, clen--;
len = ;
for(int i = clen-;i >= ; i -= numbit) {
int top = min(numbit, i+), mul = ;
s[len] = ;
for(int j = ;j < top; j++) {
s[len] += (num[i-j]-'')*mul;
mul *= ;
}
len++;
}
deal();
return *this;
}
void deal() {
while(len > && !s[len-]) len--;
}
bign operator + (const bign &a) const {
bign ret;
ret.len = ;
int top = max(len, a.len), add = ;
for(int i = ;add || i < top; i++) {
int now = add;
if(i < len) now += s[i];
if(i < a.len) now += a.s[i];
ret.s[ret.len++] = now%addbit;
add = now/addbit;
}
return ret;
}
bign operator * (const bign &a)const {
bign ret;
ret.len = len + a.len;
for(int i = ;i < len; i++) {
int pre = ;
for(int j = ;j < a.len; j++) {
int now = s[i]*a.s[j] + pre;
pre = ;
ret.s[i+j] += now;
if(ret.s[i+j] >= addbit) {
pre = ret.s[i+j]/addbit;
ret.s[i+j] -= pre*addbit;
}
}
if(pre) ret.s[i+a.len] = pre;
}
ret.deal();
return ret;
}
}dp[][];
istream& operator >> (istream &in, bign &x) {
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream &out, const bign &x) {
printf("%d", x.s[x.len-]);
for(int i = x.len-;i >= ; i--) printf("%04d", x.s[i]);
return out;
} int main(void) //URAL 1036 Lucky Tickets
{
//freopen ("W.in", "r", stdin); int n, s;
while (scanf ("%d%d", &n, &s) == )
{
if (s & ) {puts (""); continue;} dp[][] = ;
int cur = ;
for (int i=; i<=n; ++i)
{
for (int j=; j<=s/; ++j) dp[cur^][j] = ;
for (int j=; j<=; ++j)
{
for (int k=; k+j<=s/; ++k)
dp[cur^][k+j] = dp[cur^][k+j] + dp[cur][k];
}
cur ^= ;
} cout << dp[cur][s/] * dp[cur][s/] << endl;
} return ;
}

最新文章

  1. 机器学习之sklearn——聚类
  2. shell正则表达式
  3. UVA-11997 K Smallest Sums
  4. 通过swap代码分析C语言指针在汇编级别的实现
  5. zepto源码--extend--学习笔记
  6. YTU 2602: 熟悉题型——类设计( 矩形类定义【C++】)
  7. Choosing Columns and Expressions to Index
  8. C# 截取字符串,区分中英文情况
  9. 更改mysql 数据库名称
  10. HDU2138 随机素数测试 Miller-Rabin算法
  11. JustMock .NET单元测试利器(二)JustMock基础
  12. 运维-替换kibana徽标
  13. ORACLE中通过SQL语句(alter table)来增加、删除、修改字段
  14. SpringBoot之前端文件管理
  15. script id
  16. ps: 图层样式;
  17. laravel 5.6
  18. [daily][editer] 二进制编辑工具 hyx
  19. VC调试小结
  20. python 获取函数调用者

热门文章

  1. LINQ体验(18)——LINQ to SQL语句之视图和继承支持
  2. css3中我们不知道的一些属性
  3. 域名ip自动跳转 跳转指定页面的js
  4. kafka 查询 SQL Query
  5. html5--6-60 阶段练习7-下拉菜单
  6. hdu-5676 ztr loves lucky numbers(乱搞题)
  7. fastText(二):微博短文本下fastText的应用(一)
  8. Python3中使用PyMongo的方法详解
  9. Bootstrap-CSS:图片
  10. 【旧文章搬运】修改PEB,断链隐藏模块成功