挺有意思的模板题。
记住几个基本的生成函数
对于(1+x^k+x^{2k} + dots = frac{1}{1 - x^k})
(x + x^{k+1} + x^{2k+1} + dots = frac{x}{1-x^k})
那么把所有的式子变成母函数后再相乘，就有(frac{x}{(1-x)^4})
那么答案就是(x(1+x+x^2+dots + )^4)
等价于任意取4个价值不同的，然后再取一个价值为1的，最后组合一下，和是(n)的种类数
根据非负整数解的个数公式
(n)个物品放进(k)个盒子里的方法总数为(egin{equation}
left(egin{array}{l}
n+k - 1 \
k-1
end{array}
ight)
end{equation})(允许有空盒子)
那么答案就是(C_{n+2}^3)，用大整数去做就行了
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define CASE int Kase = 0; cin >> Kase; for(int kase = 1; kase <= Kase; kase++)
using namespace std;
template<typename T = long long> inline T read() {
T s = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
return s * f;
}
#ifdef ONLINE_JUDGE
#define qaq(...) ;
#else
template <typename... T> void qaq(const T &...args) {
auto &os = std::cerr;
(void)(int[]){(os << args << " ", 0)...};
os << std::endl;
}
#endif
const int N = 1e5 + 5, MAXN = 1e4 + 5, MOD = 1e9 + 7, CM = 998244353, INF = 0x3f3f3f3f; const ll linf = 0x7f7f7f7f7f7f7f7f;
struct BigInteget{ // 非负整数范围运行
int digit[MAXN];
int length;
BigInteget();
BigInteget(int x);
BigInteget(string str);
BigInteget(const BigInteget& b);
BigInteget operator =(int x);
BigInteget operator =(string str);
BigInteget operator =(const BigInteget& b);
bool operator <=(const BigInteget& b);
bool operator ==(const BigInteget& b);
bool operator >(const BigInteget& b);
BigInteget operator +(const BigInteget& b);
BigInteget operator -(const BigInteget& b);
BigInteget operator *(const BigInteget& b);
BigInteget operator /(const BigInteget& b);
BigInteget operator %(const BigInteget& b);
friend istream& operator>>(istream& in, BigInteget& x);
friend ostream& operator<<(ostream& out, const BigInteget& x);
void show();
};
istream& operator >> (istream& in, BigInteget& x){
string str;
in >> str;
x = str;
return in;
}
ostream& operator << (ostream& out, const BigInteget& x){
for(int i = x.length-1; i >= 0; i--)
out << x.digit[i];
return out;
}
BigInteget::BigInteget(){
memset(digit, 0, sizeof(digit));
length = 0;
}
BigInteget::BigInteget(int x){
memset(digit, 0, sizeof(digit));
length = 0;
if(x == 0)
digit[length++] = x;
while(x) {
digit[length++] = x % 10;
x /= 10;
}
}
BigInteget::BigInteget(string str){
memset(digit, 0, sizeof(digit));
length = str.size();
for(int i = 0; i < length; i++)
digit[i] = str[length - i - 1] - '0';
}
BigInteget::BigInteget(const BigInteget& b){
memset(digit, 0, sizeof(digit));
length = b.length;
for(int i = 0; i < length; i++)
digit[i] = b.digit[i];
}
BigInteget BigInteget::operator = (int x){
memset(digit, 0, sizeof(digit));
length = 0;
if(x == 0)
digit[length++] = x;
while(x){
digit[length++] = x % 10;
x /= 10;
}
return *this;
}
BigInteget BigInteget::operator = (string str){
memset(digit, 0, sizeof(digit));
length = str.size();
for(int i = 0; i < length; i++)
digit[i] = str[length - i - 1] - '0';
return *this;
}
BigInteget BigInteget::operator = (const BigInteget& b){
memset(digit, 0, sizeof(digit));
length = b.length;
for(int i = 0; i < length; i++)
digit[i] = b.digit[i];
return *this;
}
bool BigInteget::operator > (const BigInteget &b) {
if(length > b.length) return true;
else if(b.length > length) return false;
else {
for(int i = length - 1; i >= 0; i--) {
if(digit[i] == b.digit[i]) continue;
else return digit[i] > b.digit[i];
}
}
return false;
}
bool BigInteget::operator <= (const BigInteget& b) {
if(length < b.length) return true;
else if (b.length < length) return false;
else {
for(int i = length - 1; i >= 0; i--) {
if(digit[i] == b.digit[i]) continue;
else return digit[i] < b.digit[i];
}
}
return true;
}
bool BigInteget::operator == (const BigInteget& b){
if(length != b.length) return false;
else{
for(int i = length -1; i >= 0; i--){
if(digit[i] != b.digit[i])
return false;
}
}
return true;
}
BigInteget BigInteget::operator + (const BigInteget& b){
BigInteget answer;
int carry = 0;
for(int i = 0; i < length || i < b.length; i++){
int current = carry + digit[i] + b.digit[i];
carry = current /10;
answer.digit[answer.length++] = current % 10;
}
if(carry){
answer.digit[answer.length++] = carry;
}
return answer;
}
BigInteget BigInteget::operator - (const BigInteget& b){
BigInteget answer;
int carry = 0;
for(int i = 0; i < length; i++){
int current = digit[i] - b.digit[i] - carry;
if(current < 0) {
current += 10;
carry = 1;
} else carry = 0;
answer.digit[answer.length++] = current;
}
while(answer.digit[answer.length - 1] == 0 && answer.length > 1){//书上在这里写得是answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator * (const BigInteget& b){
BigInteget answer;
answer.length = length + b.length;
for(int i = 0; i < length; i++){
for(int j = 0; j < b.length; j++)
answer.digit[i+j] += digit[i] * b.digit[j];
}
for(int i = 0; i < answer.length; i++){
answer.digit[i+1] += answer.digit[i] / 10;
answer.digit[i] %= 10;
}
while(answer.digit[answer.length - 1] == 0 && answer.length > 1){ //书上在这里写得是answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator / (const BigInteget& b){
BigInteget answer;
answer.length = length;
BigInteget remainder = 0;
BigInteget temp = b;
for(int i = length - 1; i >= 0; i--){
if(!(remainder.length == 1 && remainder.digit[0] == 0)){
for(int j = remainder.length -1; j >= 0; j--)
remainder.digit[j + 1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while(temp <= remainder){
remainder = remainder - temp;
answer.digit[i]++;
}
}
while(answer.digit[answer.length - 1] == 0 && answer.length > 1){//书上在这里写得是answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator % (const BigInteget &b){
BigInteget remainder = 0;
BigInteget temp = b;
for(int i = length - 1; i >= 0; i--) {
if(!(remainder.length == 1 && remainder.digit[0] == 0)){
for(int j = remainder.length - 1; j >= 0; j--)
remainder.digit[j + 1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while(temp <= remainder){
remainder = remainder - temp;
}
}
return remainder;
}
void BigInteget::show() {
for(int i = length - 1; i >= 0; i--)
printf("%d", digit[i]);
putchar('
');
}
void solve(int kase){
BigInteget mod = 10007;
BigInteget n;
cin >> n;
cout << n * (n + 1) * (n + 2) / 6 % mod << endl;
}
const bool ISFILE = 0, DUO = 0;
int main(){
clock_t start, finish; double totaltime; start = clock();
if(ISFILE) freopen("/Users/i/Desktop/practice/in.txt", "r", stdin);
if(DUO) {CASE solve(kase);} else solve(1);
finish = clock();
#ifdef ONLINE_JUDGE
return 0;
#endif
printf("
Time: %lfms
", (double)(finish - start) / CLOCKS_PER_SEC * 1000);
return 0;
}