B 數列
傳送門
題目描述
給定一個正整數k(3≤k≤15),把所有k的方幂及所有有限個互不相等的k的方幂之和構成一個遞增的序列，例如，當k=3時，這個序列是：
1，3，4，9，10，12，13，…
（該序列實際上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
請你求出這個序列的第N項的值（用10進制數表示）。
例如，對于k=3，N=100，正确答案應該是981。
輸入
輸入隻有1行，為2個正整數，用一個空格隔開：k N
（k、N的含義與上述的問題描述一緻，且3≤k≤15，10≤N≤1000）。
輸出
輸出為計算結果，是一個正整數（在所有的測試資料中，結果均不超過2.1*109）。
（整數前不要有空格和其他符号）。
樣例輸入
3 100
樣例輸出
981
這個題可以模拟也可以找規律，，這裡就不介紹模拟了，說一下找規律的做法
我們可以注意到這個題有個提示要用10進制輸出，為什麼要強調這個呢？
看一下給出的例子
k=3時，數列為：1,3,4,9,10,12,13...
轉換成三進制就是：1,10,11,100,101,110,111..
是不是感覺有些熟悉？全是由0,1組成，那就試試将它們當做二進制轉換成十進制，就是
1,2,3,4,5,6,7..
顯然,第n項就是n.
程式就把這個過程逆回去，先把n轉換成二進制，再把它當成K進制，重新轉換為十進制.
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int n,k;
stack<int>s;
int main()
{
while(~scanf("%d%d",&n,&k)){
while(k){
s.push(k%2);
k/=2;
}
ll ans=0;
while(!s.empty()){
ans+=s.top()*pow(n,s.size()-1);
s.pop();
}
printf("%lld\n",ans);
}
}
C 擺花
傳送門
題目描述
小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共 m 盆。
通過調 查顧客的喜好，小明列出了顧客最喜歡的 n 種花，從 1 到 n 标号。
為了在門口展出更多種花， 規定第 i 種花不能超過 ai盆，擺花時同一種花放在一起，且不同種類的花需按标号的從小到 大的順序依次擺列。
試程式設計計算，一共有多少種不同的擺花方案。
輸入
第一行包含兩個正整數 n 和 m，中間用一個空格隔開。
第二行有 n 個整數，每兩個整數之間用一個空格隔開，依次表示 a1、a2、……an。
輸出
輸出隻有一行，一個整數，表示有多少種方案。
注意：因為方案數可能很多，請輸出 方案數對 1000007 取模的結果。
樣例輸入
2 4
3 2
樣例輸出
2
提示
【輸入輸出樣例說明】
有 2 種擺花的方案，分别是(1，1，1，2)， (1，1，2，2)。
括号裡的 1 和 2 表示兩種花， 比如第一個方案是前三個位置擺第一種花，第四個位置擺第二種花。
這是一個DP的題目，我們用一個二維數組記錄即可，一維數組a[i]表示每種花有多少個。
ans[i][j]表示選了前i種花共j個，目前的第i種可以選0到a[i]個，因為也可以不選這種花，那麼我們就可以得出狀态轉移方程
ans[i][j]=ans[i][j]+ans[i-1][j-k] (ans[i-1][j-k]表示前i-1種選了j-k個）
需要注意的是ans[0][0]一開始要初始化為1，因為第一種花一個也不選也是一種情況。
#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
#define mod 1000007
using namespace std;
int ans[110][110],n,m,a[110];
int main()
{
while(~scanf("%d%d",&n,&m))
{
met(ans,0);
for(int i=1;i<=n;i++)
sc(a[i]);
ans[0][0]=1; //第一種花選0個也是一種方案
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=a[i];k++)
if(j>=k){
ans[i][j]+=ans[i-1][j-k];
ans[i][j]%=mod;
}
printf("%d\n",ans[n][m]%mod);
}
}
![JSP制作網頁購物車[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)