結果
問題 | No.737 PopCount |
ユーザー |
![]() |
提出日時 | 2019-06-22 10:39:45 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 148 ms / 1,000 ms |
コード長 | 2,149 bytes |
コンパイル時間 | 3,038 ms |
コンパイル使用メモリ | 82,084 KB |
実行使用メモリ | 41,760 KB |
最終ジャッジ日時 | 2024-12-26 08:43:52 |
合計ジャッジ時間 | 6,374 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long MOD = (long)Math.pow(10, 9) + 7;String sn = "";sn = String.valueOf(n % 2);n /= 2;for(int i = 0; i < 100; i++) {if(n > 0) {long t = n % 2;n /= 2;sn = String.valueOf(t) + sn;} else {break;}}int len = sn.length();long[][][] dp = new long[len][100][2];long[][][] dp2 = new long[len][100][2];long[] rui = new long[len];rui[0] = 1;for(int i = 1; i < len; i++) {rui[i] = (rui[i - 1] * 2) % MOD;}int[] bin = new int[len];for(int i = 0; i < len; i++) {int t = Integer.parseInt(String.valueOf(sn.charAt(i)));bin[i] = t;}dp[0][0][1] = 0;dp[0][1][0] = rui[len - 1];dp2[0][0][1] = 1;dp2[0][1][0] = 1;for(int i = 1; i < len; i++) {for(int j = 0; j < 99; j++) {if(bin[i] == 0) dp2[i][j][0] = (dp2[i][j][0] + dp2[i - 1][j][0]) % MOD;if(bin[i] == 1) {dp2[i][j][1] = (dp2[i][j][1] + dp2[i - 1][j][0] + dp2[i - 1][j][1]) % MOD;} else {dp2[i][j][1] = (dp2[i][j][1] + dp2[i - 1][j][1]) % MOD;}if(bin[i] == 1) dp2[i][j + 1][0] = (dp2[i][j + 1][0] + dp2[i - 1][j][0]) % MOD;dp2[i][j + 1][1] = (dp2[i][j + 1][1] + dp2[i - 1][j][1]) % MOD;if(bin[i] == 0) dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][0]) % MOD;if(bin[i] == 1) {dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0] + dp[i - 1][j][1]) % MOD;} else {dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][1]) % MOD;}if(bin[i] == 1) dp[i][j + 1][0] = (dp[i][j + 1][0] + dp[i - 1][j][0] + rui[len - 1 - i] * dp2[i - 1][j][0]) % MOD;dp[i][j + 1][1] = (dp[i][j + 1][1] + dp[i - 1][j][1] + rui[len - 1 - i] * dp2[i - 1][j][1]) % MOD;}}long ans = 0;for(int j = 1; j < 100; j++) {for(int k = 0; k < 2; k++) {ans = (ans + (long)j * dp[len - 1][j][k]) % MOD;}}System.out.println(ans);}}