rockdu
Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
4 10 20
Sample Output
5 42 627
Author
Ignatius.L
Recommend
同1398，我们只需要对于1~N的每一种值构造生成函数达到枚举这种值取几个，所有这些多项式乘起来的结果就是答案。详见HDU1398
同样的，为了练习NTT，我多项式乘法写了NTT。并且注意！这道题的答案是大于998244353的，我们需要更大的模数。我选择了2281701377，原根同样是3。另附NTT可用模数表：点我，我是"原根表"
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<complex>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 256 << 2;
const LL P = 2281701377LL, G = 3;
int N, n, m, mx2p, R[maxn << 1];
LL p[maxn << 1], ans[maxn << 1], inv;
void init(int n) {
for(N = 1; N <= n; N <<= 1) ++mx2p;
for(register int i = 0; i < N; ++i)
R[i] = (R[i >> 1] >> 1) | ((i & 1) << mx2p - 1);
}
LL fpow(LL a, LL b) {
LL ans = 1;
while(b) {
if(b & 1) ans = ans * a % P;
b >>= 1, a = a * a % P;
}
return ans;
}
void NTT(LL * a, int type) {
for(register int i = 0; i < N; ++i) if(i < R[i]) swap(a[i], a[R[i]]);
for(register int i = 1; i < N; i <<= 1) {
LL Wn = fpow(G, (P - 1) / (i << 1));
if(type == -1) Wn = fpow(Wn, P - 2);
for(register int j = 0, p = i << 1; j < N; j += p) {
LL w = 1;
for(register int k = 0; k < i; ++k, w = w * Wn % P) {
LL x = a[j + k], y = a[j + k + i] * w % P;
a[j + k] = ((x + y) % P + P) % P;
a[j + k + i] = ((x - y) % P + P) % P;
}
}
}
}
int main() {
n = 120, init(n << 1);
for(register int i = 0; i <= n; ++i) ans[i] = 1;
inv = fpow(N, P - 2);
for(register int i = 2; i <= n; ++i) {
memset(p, 0, sizeof(p));
for(register int j = 0; j <= n; j += i)
p[j] = 1;
NTT(p, 1), NTT(ans, 1);
for(register int j = 0; j <= N; ++j)
ans[j] = 1LL * ans[j] * p[j] % P;
NTT(ans, -1);
for(register int j = 0; j <= n; ++j)
ans[j] = 1LL * ans[j] * inv % P;
for(register int j = n + 1; j <= N; ++j)
ans[j] = 0;
}
while(~scanf("%d", &n)) {
printf("%d\n", ans[n]);
}
return 0;
}
没有帐号? 立即注册