楊輝三角形//第8回北京師範大学プログラム設計コンテスト決勝戦

タイトルリンク

ヤングさんかくけい

Time Limit: 1500ms
Memory Limit: 65536KB
64-bit integer IO format: 
%lld      Java class name: 
Main
Prev 
Submit  Status  Statistics  Discuss
  Next
Type: 
None
  None Graph Theory      2-SAT     Articulation/Bridge/Biconnected Component      Cycles/Topological Sorting/Strongly Connected Component      Shortest Path          Bellman Ford         Dijkstra/Floyd Warshall      Euler Trail/Circuit      Heavy-Light Decomposition     Minimum Spanning Tree      Stable Marriage Problem      Trees     Directed Minimum Spanning Tree      Flow/Matching          Graph Matching             Bipartite Matching              Hopcroft–Karp Bipartite Matching              Weighted Bipartite Matching/Hungarian Algorithm          Flow              Max Flow/Min Cut             Min Cost Max Flow  DFS-like      Backtracking with Pruning/Branch and Bound      Basic Recursion     IDA* Search      Parsing/Grammar     Breadth First Search/Depth First Search      Advanced Search Techniques          Binary Search/Bisection         Ternary Search  Geometry      Basic Geometry     Computational Geometry      Convex Hull      Pick's Theorem Game Theory      Green Hackenbush/Colon Principle/Fusion Principle      Nim     Sprague-Grundy Number  Matrix     Gaussian Elimination      Matrix Exponentiation Data Structures      Basic Data Structures     Binary Indexed Tree      Binary Search Tree      Hashing     Orthogonal Range Search      Range Minimum Query/Lowest Common Ancestor      Segment Tree/Interval Tree     Trie Tree      Sorting      Disjoint Set String      Aho Corasick     Knuth-Morris-Pratt      Suffix Array/Suffix Tree Math      Basic Math     Big Integer Arithmetic      Number Theory         Chinese Remainder Theorem          Extended Euclid          Inclusion/Exclusion         Modular Arithmetic      Combinatorics          Group Theory/Burnside's lemma         Counting      Probability/Expected Value  Others     Tricky      Hardest     Unusual      Brute Force     Implementation      Constructive Algorithms     Two Pointer      Bitmask     Beginner      Discrete Logarithm/Shank's Baby-step Giant-step Algorithm      Greedy     Divide and Conquer  Dynamic Programming                   Tag it!
  
LZM
同級生は牛のように、
Lsy
最近もますます激しくなって、彼らの考えは速くて、コードのスピードは勇ましいです.最近、この二人が学校の試合に参加するという驚きを聞いて、チームは問題カードを出すことにした.彼らのストが問題グループに重い負担を残したからだ.(報復)
すると、
XsugarX
狙いを定めた
LZM
あまり好きではない数学の問題と
Lsy
公式の好みを当てて、奸笑中(
^.^
).この数学の問題は比較的古い問題で、下図のような三角形は楊輝三角形と呼ばれています.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
最初に覚えておきます
1
を選択して
0
行、下に順番に番号を付けます.
このうち三角形の左右の斜辺の数字はいずれも
1
他の位置は両肩の数の和である.
この2牛は偶数を見ると複雑に感じ、カードされた時間は偶数の個数に比例し、
XsugarX
彼らの時間が長ければ長いほどいいことを望んでいます.
任意の楊輝三角の行数を与える
n
、楊輝三角中前を出力してください
n行
の中で全部で何偶数がありますか.

Input

  
1つの数
n
(
0<=n<=3,000,000
).楊輝三角を求める前に
n
行の偶数の数.

Output

  
1つの数
R
.楊輝三角の前で
n
行中共有
R
偶数個、結果が大きくなる可能性がありますので、出力してください
R mod 10,000,000
と入力します.

Sample Input

4

Sample Output

4

Source

第8回北京師範大学プログラム設計コンテスト決勝戦

Author

XsugarX

Tags Toggle

Prev 
Submit  Status  Statistics  Discuss
  Next 
                                                                                                                                                                                                                                               
題解:楊輝三角形の分形問題、楊輝三角形の前のn行の偶数の個数を求めます.プロトタイプは,楊輝三角形のn行目の奇数個の数が2 k個に等しく,kがnをバイナリとして表すときの1個の数に基づいている.従って、n<=300000のデータ範囲に対して、1回のスキャン、累積、打表を線形に行うことができる.統計的バイナリビットのため、複雑度O(N)のNは小さな定数Cを含み、Cは数値の長さである.ほとんどがフラクタルで解決されていますが、もちろんこれも自然な考えで、効率は少し低くなります.またVIJOSには問題の強化版があり,問題データn<=10^50は,上記の定理に基づいて公式を押し倒し,その後高速べき乗+高精細に解決する必要がある. 
ふごうコード
方法1:

#include<stdio.h>
#include<math.h>
#define N 10000000
int a[3000001]={0};
int gs(int n)
{
    int k=0;
    while(n)
        {
            n=n&(n-1);
            k++;
        }
        return k;
}
void jg(int n)
{
    int k;
        a[2]=1;
    a[3]=0;
    for(int i=4;i<=n;i++)
    {
        a[i]=i+1-pow(2,gs(i));
      // printf("%d ",a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=(a[i-1]+a[i])%N;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    jg(n);
    printf("%d
",a[n]%N);
}

方法2:

#include<stdio.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;
 const int MOD=10000000;
 int dp[3000010];
 int sum[3000010];
 void pp()
{
    dp[0]=0;
    dp[1]=0;
    dp[2]=0;
    dp[3]=1;
    dp[4]=0;
    int x=4;
    int i;
   for( i=5;i<=3000001;i++)
    {    dp[i]=dp[i-x]*2+i-(i-x)*2;//      
           dp[i]=dp[i]%MOD;
            if(i==x*2)
                x=x*2;
    }
    sum[0]=0;
    for(i=0;i<=3000000;i++)//  
        sum[i]=(dp[i+1]+sum[i-1])%MOD;
}
int main()
{pp();
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d
",sum[n]);
    }
}