HDU-1028 Ignatius and the Princess III(生成函数)

题意

给出$n$，问用$1$到$n$的数字问能构成$n$的方案数

思路

生成函数基础题，$x^{n}$的系数即答案。

代码

#include <bits/stdc++.h> #define DBG(x) cerr << #x << " = " << x << endl;using namespace std;const int N = 120 + 5;int n, c[2][N];int main() {while(~scanf("%d", &n)) {for(int i = 0; i <= n; i++) c[1][i] = 1, c[0][i] = 0;for(int i = 2; i <= n; i++) {for(int j = 0; j <= n; j++) {for(int k = 0; k + j <= n; k += i) c[i & 1][k + j] += c[1 - (i & 1)][j];}for(int j = 0; j <= n; j++) c[1 - (i & 1)][j] = 0;}printf("%d\n", c[n & 1][n]);}return 0; }

　　

转载于:https://www.cnblogs.com/DuskOB/p/10604288.html

总结

以上是生活随笔为你收集整理的HDU-1028 Ignatius and the Princess III(生成函数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。