以前写的，把垃圾代码丢上来 :)
#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;
const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;
#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))
#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
const ll maxn = 6e2 + 9, base = 1e8;
char s[(int)5e3 + 9];
struct bign_c
{
ll a[5];
int len;
void clear() { len = 1, a[len] = 0; }
bign_c() { clear(); };
bign_c(ll x) { a[1] = x,len=1; }
bign_c operator=(bign_c b)
{
len = b.len;
for (int i = 1; i <= len; ++i)
a[i] = b.a[i];
return *this;
}
bign_c operator+(bign_c b)
{
int L = max(len, b.len);
bign_c tmp;
for (int i = 1; i <= L + 1; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= L; ++i)
if (i > len)
tmp.a[i] += b.a[i];
else if (i > b.len)
tmp.a[i] += a[i];
else
{
tmp.a[i] += a[i] + b.a[i];
if (tmp.a[i] >= base)
{
tmp.a[i] -= base;
++tmp.a[i + 1];
}
}
if (tmp.a[L + 1])
tmp.len = L + 1;
else
tmp.len = L;
return tmp;
}
bign_c operator-(bign_c b)
{
int L = max(len, b.len);
bign_c tmp;
for (int i = 1; i <= L + 1; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= L; ++i)
{
if (i > b.len)
b.a[i] = 0;
tmp.a[i] += a[i] - b.a[i];
//cerr<<tmp.a[i]<<"-de\n";
if (tmp.a[i] < 0)
{
tmp.a[i] += base;
--tmp.a[i + 1];
//cerr<<tmp.a[i]<<"-tst\n";
}
}
while (L > 1 && !tmp.a[L])
L -= 1;
tmp.len = L;
return tmp;
}
bign_c operator*(bign_c b)
{
int L = len + b.len;
bign_c tmp;
for (int i = 1; i <= L; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= len; ++i)
{
for (int j = 1; j <= b.len; ++j)
{
tmp.a[i + j - 1] += a[i] * b.a[j];
if (tmp.a[i + j - 1] >= base)
{
tmp.a[i + j] += tmp.a[i + j - 1] / base;
tmp.a[i + j - 1] %= base;
}
}
}
tmp.len = len + b.len;
while (tmp.len > 1 && !tmp.a[tmp.len])
--tmp.len;
return tmp;
}
bign_c operator/(ll x)
{
ll d = 0;
bign_c tmp;
for (int i = len; i; --i)
{
d = d * base + a[i];
tmp.a[i] = d / x;
d %= x;
}
tmp.len = len;
while (tmp.len > 1 && !tmp.a[tmp.len])
--tmp.len;
return tmp;
}
bign_c operator+=(ll x)
{
bign_c T;
T = x;
return *this + T;
}
bign_c operator*=(bign_c b)
{
*this = *this * b;
return *this;
}
bign_c operator/=(ll x)
{
*this = *this / x;
return *this;
}
bign_c operator+(ll x)
{
bign_c T;
T = x;
return *this + T;
}
bign_c operator-=(bign_c b)
{
*this = *this - b;
return *this;
}
void print()
{
printf("%lld", a[len]);
for (int i = len - 1; i; --i)
{
for (int j = base / 10; j >= 10; j /= 10)
{
if (a[i] < j)
printf("0");
else
break;
}
printf("%lld", a[i]);
}
printf("\n");
}
void str(char s[])
{
int l = strlen(s);
ll x = 0, y = 1;
len = 0;
for (int i = l - 1; i >= 0; --i)
{
x = x + (s[i] - '0') * y;
y *= 10;
if (y == base)
a[++len] = x, x = 0, y = 1;
}
if (!len || x)
a[++len] = x;
}
int read()
{
int sta = ~scanf("%s", s);
if (sta)
this->str(s);
return sta;
}
bool operator <(bign_c b)const {
if(len<b.len)return 1;
if(len>b.len)return 0;
for(int i=len;i;--i){
if(a[i]<b.a[i])return 1;
if(a[i]>b.a[i])return 0;
}
return 0;
}
};
struct bign
{
ll a[maxn];
int len;
void clear() { len = 1, a[len] = 0; }
bign() { clear(); };
bign(ll x) { a[1] = x,len=1; }
bign operator=(bign b)
{
len = b.len;
for (int i = 1; i <= len; ++i)
a[i] = b.a[i];
return *this;
}
bign operator+(bign b)
{
int L = max(len, b.len);
bign tmp;
for (int i = 1; i <= L + 1; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= L; ++i)
if (i > len)
tmp.a[i] += b.a[i];
else if (i > b.len)
tmp.a[i] += a[i];
else
{
tmp.a[i] += a[i] + b.a[i];
if (tmp.a[i] >= base)
{
tmp.a[i] -= base;
++tmp.a[i + 1];
}
}
if (tmp.a[L + 1])
tmp.len = L + 1;
else
tmp.len = L;
return tmp;
}
bign operator-(bign b)
{
int L = max(len, b.len);
bign tmp;
for (int i = 1; i <= L + 1; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= L; ++i)
{
if (i > b.len)
b.a[i] = 0;
tmp.a[i] += a[i] - b.a[i];
//cerr<<tmp.a[i]<<"-de\n";
if (tmp.a[i] < 0)
{
tmp.a[i] += base;
--tmp.a[i + 1];
//cerr<<tmp.a[i]<<"-tst\n";
}
}
while (L > 1 && !tmp.a[L])
L -= 1;
tmp.len = L;
return tmp;
}
bign operator*(bign b)
{
int L = len + b.len;
bign tmp;
for (int i = 1; i <= L; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= len; ++i)
{
for (int j = 1; j <= b.len; ++j)
{
tmp.a[i + j - 1] += a[i] * b.a[j];
if (tmp.a[i + j - 1] >= base)
{
tmp.a[i + j] += tmp.a[i + j - 1] / base;
tmp.a[i + j - 1] %= base;
}
}
}
tmp.len = len + b.len;
while (tmp.len > 1 && !tmp.a[tmp.len])
--tmp.len;
return tmp;
}
bign operator*(bign_c b)
{
int L = len + b.len;
bign tmp;
for (int i = 1; i <= L; ++i)
tmp.a[i] = 0;
for (int i = 1; i <= len; ++i)
{
for (int j = 1; j <= b.len; ++j)
{
tmp.a[i + j - 1] += a[i] * b.a[j];
if (tmp.a[i + j - 1] >= base)
{
tmp.a[i + j] += tmp.a[i + j - 1] / base;
tmp.a[i + j - 1] %= base;
}
}
}
tmp.len = len + b.len;
while (tmp.len > 1 && !tmp.a[tmp.len])
--tmp.len;
return tmp;
}
bign operator/(ll x)
{
ll d = 0;
bign tmp;
for (int i = len; i; --i)
{
d = d * base + a[i];
tmp.a[i] = d / x;
d %= x;
}
tmp.len = len;
while (tmp.len > 1 && !tmp.a[tmp.len])
--tmp.len;
return tmp;
}
bign operator+=(ll x)
{
bign T;
T = x;
return *this + T;
}
bign operator*=(bign b)
{
*this = *this * b;
return *this;
}
bign operator/=(ll x)
{
*this = *this / x;
return *this;
}
bign operator+(ll x)
{
bign T;
T = x;
return *this + T;
}
bign operator-=(bign b)
{
*this = *this - b;
return *this;
}
void print()
{
printf("%lld", a[len]);
for (int i = len - 1; i; --i)
{
for (int j = base / 10; j >= 10; j /= 10)
{
if (a[i] < j)
printf("0");
else
break;
}
printf("%lld", a[i]);
}
printf("\n");
}
void str(char s[])
{
int l = strlen(s);
ll x = 0, y = 1;
len = 0;
for (int i = l - 1; i >= 0; --i)
{
x = x + (s[i] - '0') * y;
y *= 10;
if (y == base)
a[++len] = x, x = 0, y = 1;
}
if (!len || x)
a[++len] = x;
}
int read()
{
int sta = ~scanf("%s", s);
if (sta)
this->str(s);
return sta;
}
bool operator <(bign b)const {
if(len<b.len)return 1;
if(len>b.len)return 0;
for(int i=len;i;--i){
if(a[i]<b.a[i])return 1;
if(a[i]>b.a[i])return 0;
}
return 0;
}
};
bign n;
long long k;
/*
map<pair<bign,long long>,bign>dp;
bign solve(bign nn, long long kk)
{
if (kk == 1)
return nn * (nn + 1ll) / 2ll;
if(dp.count({nn,kk}))return dp[{nn,kk}];
bign base, res;
base = nn + 1ll, res = 1ll;
for (int i = 1; i <= kk + 1; ++i)
{
//cerr<<i<<"\n";
res *= base;
}
for (int i = 2; i <= kk; ++i)
{
//cout << i << "--" << kk << "\n";
res -= solve(nn, kk - i + 1) * c[kk + 1][i];
}
res -= nn + 1;
return dp[{nn,kk}]=res / (kk + 1);
}*/
bign dp[109],dpb[109];
bign_c c[109][109];
bign solve(bign nn, long long kk)
{
dp[1]=nn * (nn + 1ll) / 2ll;
//if(vis[kk])return dp[kk];
//if(dp.count({nn,kk}))return dp[{nn,kk}];
//nn.print();\
(nn+1).print();
bign base, res;
base = nn + 1, res = 1;
for (int i = 1; i <= kk + 2; ++i)
{
//cerr<<i<<"\n";
res *=base;
dpb[i]=res;
//printf("%d--",i);\
res.print();
}
/*for (int i = 2; i <= kk; ++i)
{
//cout << i << "--" << kk << "\n";
res -= solve(nn, kk - i + 1) * c[kk + 1][i];
}
res -= nn + 1;*/
//return dp[{nn,kk}]=res / (kk + 1);
//vis[kk]=1;
//2^100
for(int i=2;i<=kk;++i){
dp[i]=dpb[i+1];
for(int j=2;j<=i;++j){
//(dp[i-j+1]*c[i+1][j]).print();\
dp[i].print();
dp[i]-=dp[i-j+1]*c[i+1][j];
//dp[i].print()\
printf("%d_en_\n\n",dp[i].len);
}
dp[i]-=nn+1;
dp[i]/=(i+1);
//dp[i].print();
//printf("\n%d------\n",i);
}
return dp[kk];
}
int main()
{
//bign a=1e7-1,b=1e7-1;
//bign cc=a*b*a*b*a*b;cc.print();
//bign aa=1800244155348828,cc=244155348829;\
(aa-cc).print();
int fk=0;
f(i, 1, 102)
{
c[i][i] = c[i][0] = 1;
for (int j = 1; j < i; j++)
{
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]);
}
}
while (n.read())
{
scanf("%lld", &k);
bign res = solve(n, k);
res.print();
}
return 0;
}
/*
* ┌───┐┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ ┌──┐ ┌──┐ ┌──┐
* │╠╣1││Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ │┌┐│ │┌┐│ │┌┐│
* ├───┤└───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └└┘┘ └└┘┘ └└┘┘
* │╠╣2│┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* └───┘│~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ┌───┐├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │╠╣3││ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├───┤├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │╠╣4││ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │
* └───┘├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* ┌───┐│ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* │╠╣5│├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* ├───┤│ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* │╠╣6│└─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
* └───┘
*/
