來源：盼鸶海客網(wǎng)2017年校招全國統(tǒng)一模擬筆試(第五場)編程題集合
時間限制：1秒
空間限制：32768K
牛牛和羊羊在玩一個有趣的猜數(shù)游戲复亏。在這個游戲中,牛牛玩家選擇一個正整數(shù),羊羊根據(jù)已給的提示猜這個數(shù)字俱两。第i個提示是"Y"或者"N",表示牛牛選擇的數(shù)是否是i的倍數(shù)赎线。例如,如果提示是"YYNYY",它表示這個數(shù)使1,2,4,5的倍數(shù),但不是3的倍數(shù)。注意到一些提示會出現(xiàn)錯誤钥弯。例如: 提示"NYYY"是錯誤的,因為所有的整數(shù)都是1的倍數(shù),所以起始元素肯定不會是"N"径荔。此外,例如"YNNY"的提示也是錯誤的,因為結(jié)果不可能是4的倍數(shù)但不是2的倍數(shù)。現(xiàn)在給出一個整數(shù)n,表示已給的提示的長度寿羞。請計算出長度為n的合法的提示的個數(shù)猖凛。例如 n = 5:合法的提示有:YNNNN YNNNY YNYNN YNYNY YYNNN YYNNYYYNYN YYNYY YYYNN YYYNY YYYYN YYYYY所以輸出12 輸入描述:
輸入包括一個整數(shù)n(1 ≤ n ≤ 10^6),表示已給提示的長度。
輸出描述:
輸出一個整數(shù),表示合法的提示個數(shù)绪穆。因為答案可能會很大,所以輸出對于1000000007的模
輸入例子1:
5
輸出例子1:
12
分析
這道題比較難。
首先運用動態(tài)規(guī)劃的思想
首先我們分析虱岂，dp[i]表示前i個數(shù)的合法個數(shù)
當?shù)趇個數(shù)是素數(shù)的時候玖院，前面除了1都沒有能除盡的，所以這個位置可以隨便選Y或N,所以dp[i] = dp[i-1]
當?shù)趇個數(shù)不是素數(shù)的冪次第岖，比如6难菌，10這種數(shù)，那么他們的情況實際上是被前面的數(shù)所決定的蔑滓，對6來說郊酒，如果2，3為YY,那么6必然是Y键袱，其他情況6必須是N,所以dp[i] = dp[i-1]
當?shù)趇個數(shù)是素數(shù)的冪次的時候燎窘，也就是2，4蹄咖，8褐健，16這種數(shù)，這時候情況就復(fù)雜了澜汤。假設(shè)現(xiàn)在有2蚜迅，4舵匾，8，那么有多少種情況呢谁不，我們仔細分析也能找出規(guī)律
YYY,YNN,NNN坐梯，YYN就這四種情況
對于2，4
YN,YY,NN三種情況
我們發(fā)現(xiàn)實際上也是有規(guī)律的刹帕，首先都能或者都不能兩種吵血，然后就是從左到右添加Y：
YNN,YYN。
所以對于這種情況轩拨，我們得出規(guī)律践瓷，如果有n個冪次，就有n+1中可行的情況亡蓉。
分析完之后晕翠，我們就可以得出計算方法，對于12：
2砍濒，4淋肾，8這三個數(shù)是冪次，有4中可能
3爸邢，9 這兩個數(shù)冪次樊卓，有三種可能
5，7杠河，11碌尔，分別是兩種可能
其他的數(shù)都由其他數(shù)決定
所以最后結(jié)果就是43222
所以我們思考一下，最后就變成了找素數(shù)和素數(shù)冪次的個數(shù)了券敌。
代碼
import java.util.*;
public class Main {
final static int MAX = (int) (1e6+5);
final static int MOD = (int) (1E9+7);
static boolean[] visited = new boolean[MAX];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.close();
System.out.println(helper(n));
}
private static long helper(int n) {
long ans = 1;
for(int i=2;i<=n;i++) {
int count = 0;
if(visited[i])
continue;
for(int j=i+i;j<=n;j+=i) {
visited[j] = true;
}
long mi = i;
while(mi <= n) {
count++;
mi = mi*i;
}
ans = ans * (count+1) % MOD;
}
return ans;
}
}
?
