DP+高精度 URAL 1036 Lucky Tickets
2024-08-27 04:59:24
/*
题意:转换就是求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 ;
}
最新文章
- 机器学习之sklearn——聚类
- shell正则表达式
- UVA-11997 K Smallest Sums
- 通过swap代码分析C语言指针在汇编级别的实现
- zepto源码--extend--学习笔记
- YTU 2602: 熟悉题型——类设计( 矩形类定义【C++】)
- Choosing Columns and Expressions to Index
- C# 截取字符串,区分中英文情况
- 更改mysql 数据库名称
- HDU2138 随机素数测试 Miller-Rabin算法
- JustMock .NET单元测试利器(二)JustMock基础
- 运维-替换kibana徽标
- ORACLE中通过SQL语句(alter table)来增加、删除、修改字段
- SpringBoot之前端文件管理
- script id
- ps: 图层样式;
- laravel 5.6
- [daily][editer] 二进制编辑工具 hyx
- VC调试小结
- python 获取函数调用者