Time Limit: 1 second
Memory Limit: 50 MB
【问题描述】
设r是个2K进制数，并满足以下条件：
（1）r至少是个2位的2K进制数。
（2）作为2K进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k≤30000）是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2K进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2K进制数r。
例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。
【输入】
只有1行，为两个正整数，用一个空格隔开：
k W
【输出】
为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）
【输入样例】
3 7
【输出样例】
36
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=b604
【题意】
【题解】
比较裸的排列组合题了.
写个高精度,求出组合数就好;
组合数公式
C[I][J] = C[I-1][J]+C[I-1][J-1];
然后根据要求计数就好;
平台上面有限制内存50MB；
写个压位的高精度吧.
压8位的高精度加法.
【完整代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 520;
const int jz = 100000000;
struct bignum
{
int len;
int a[30];
void init(int x)
{
memset(a, 0, sizeof a);
len = 1; a[1] = x;
}
};
bignum operator + (bignum a, bignum b)
{
bignum c;
c.init(0);
int lena = a.len, lenb = b.len;
int len = max(lena, lenb);
int x = 0;
rep1(i, 1, len)
{
c.a[i] += a.a[i] + b.a[i]+x;
x = c.a[i] / jz;
c.a[i] %= jz;
}
while (x > 0)
{
c.a[++len] = x;
x = c.a[len] / jz;
c.a[len] %= jz;
}
c.len = len;
return c;
}
bignum c[N][N],ans;
int k, w;
void get_C()
{
rep1(i, 1, 512)
c[i][0].init(1), c[i][i].init(1);
rep1(i, 2, 512)
rep1(j, 1, i)
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
void input_data()
{
rei(k), rei(w);
}
void get_ans()
{
ans.init(0);
int len = w / k, mod = w%k;
int t = (1 << k) - 1;
rep1(i, 2, len)
{
rep1(j, 1, t - i+1)
{
if (t - j < i - 1) break;
ans = ans + c[t - j][i - 1];
}
}
int d = (1 << mod) - 1;
rep1(j, 1, d)
{
if (t - j < len) break;
ans = ans + c[t - j][len];
}
}
void ze_ro(int num)
{
rep1(i, 1, num)
putchar('0');
}
void output_ans()
{
printf("%d", ans.a[ans.len]);
rep2(i, ans.len - 1, 1)
{
if (ans.a[i] < 10)
ze_ro(7);
if (ans.a[i] < 100)
ze_ro(6);
if (ans.a[i] < 1000)
ze_ro(5);
if (ans.a[i] < 10000)
ze_ro(4);
if (ans.a[i] < 100000)
ze_ro(3);
if (ans.a[i] < 1000000)
ze_ro(2);
if (ans.a[i] < 10000000)
ze_ro(1);
printf("%d", ans.a[i]);
}
puts("");
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
//printf("%d\n", sizeof(c) / 1024 / 1024);
get_C();
input_data();
get_ans();
output_ans();
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}