HDU&POJトレーニングレコード4生成関数
1、Ignatius and the Princess III
トランスファゲート
題意を簡潔に述べる.
nをいくつかの整数に分割するシナリオ数を求める.
データ範囲
n≤120
問題解
まず,各数で構成できる数の生成関数を構築し,次に(1+x 1+x 2+x 3+...)を乗算する.(1+x2+x4+x6+...)(1+x3+x6+x9...)... そして多項式を展開し、xn項の係数が答えである.O(n 3)直接暴力で多項式を解くことができる.
コード#コード#
2、Square Coins
トランスファゲート
題意を簡潔に述べる.
nをいくつかの完全な平方数に分割するスキーム数を求める.
データ範囲
n≤300
問題解
前の問題と同様に,各完全二乗数の生成関数を構築し,乗算する(1+x 1+x 2+x 3+...)(1+x2+x4+x6+...)(1+x3+x6+x9...)... そして多項式を展開し、xn項の係数が答えである.O(n 3)直接暴力で多項式を解くことができる.
コード#コード#
3、Holding Bin-Laden Captive!
トランスファゲート
題意を簡潔に述べる.
a個1,b個2,c個5があり,最小の組み合わせられない数を尋ねる.
データ範囲
a,b,c≤1000
問題解
従来の方法とは差が少ない1,2,5の生成関数をそれぞれ構築し,ここでは有限数列(1+x 1+x 2+x 2+…+xa)(1+x 2+x 4+…+x 2 b)(1+x 5+x 10+…+x 5 c)が多項式を展開し,次いで回数が最も小さい係数のない項を探せば時間O(n 2)
コード#コード#
4、Big Event in HDU
トランスファゲート
題意を簡潔に述べる.
n種類のものがあり、それぞれの重み値はvで、m個あります.これらのものを2つに分けて、重みとできるだけ近づけるようにします.
データ範囲
0問題解
読み込み終了が負の数であると判断し、-1とは限らず、長い間waしていた.まず生成関数でそれらの重み値を組み合わせることができることを求めて、[m/2..0]の範囲内のものを列挙すればよい時間O(nmv)
コード#コード#
5、Blocks
トランスファゲート
題意を簡潔に述べる.
赤と黄と青の緑でn個の格子に染色して、赤と緑が偶数でなければならないことを要求して、方案数を求めます.10007を型抜きします.
データ範囲
T≤100,1≤n≤109
問題解
配列問題にかかわるため,指数型生成関数を用いてシナリオ数をanとし,生成関数を書くことができる:(1+x 22!+x 44!+...)2(1+x+x22!+x33!+...)2=(ex+e−x2)2⋅e2x=e2x+e−2x+24⋅e2x=e4x+2e2x+14=(4n−1+2n−1)∑n>0xnn! だからこの問題の答えは4 n−1+2 n−1です
コード#コード#
6、配列の組み合わせ
トランスファゲート
題意を簡潔に述べる.
n種類の物品があって、それぞれai個があって、これらの物品の中でm個を選んで、配列数を求めます.
データ範囲
1≤n,m≤10
問題解
配列問題は,指数型生成関数指数で出現回数を表し,生成関数を書くには∏i=1 n(1+x+x 22!+x 33!+…+xaiai!)であるべきである.それから多項式を展開して第m項の係数を求める過程の中で暴力は多項式乗算をしてdoubleを使って、c++強転intが0に向かって整頓することに注意します
コード#コード#
トランスファゲート
題意を簡潔に述べる.
nをいくつかの整数に分割するシナリオ数を求める.
データ範囲
n≤120
問題解
まず,各数で構成できる数の生成関数を構築し,次に(1+x 1+x 2+x 3+...)を乗算する.(1+x2+x4+x6+...)(1+x3+x6+x9...)... そして多項式を展開し、xn項の係数が答えである.O(n 3)直接暴力で多項式を解くことができる.
コード#コード#
#include
",a[n]);
}
}2、Square Coins
トランスファゲート
題意を簡潔に述べる.
nをいくつかの完全な平方数に分割するスキーム数を求める.
データ範囲
n≤300
問題解
前の問題と同様に,各完全二乗数の生成関数を構築し,乗算する(1+x 1+x 2+x 3+...)(1+x2+x4+x6+...)(1+x3+x6+x9...)... そして多項式を展開し、xn項の係数が答えである.O(n 3)直接暴力で多項式を解くことができる.
コード#コード#
#include
",a[m]);
}
}3、Holding Bin-Laden Captive!
トランスファゲート
題意を簡潔に述べる.
a個1,b個2,c個5があり,最小の組み合わせられない数を尋ねる.
データ範囲
a,b,c≤1000
問題解
従来の方法とは差が少ない1,2,5の生成関数をそれぞれ構築し,ここでは有限数列(1+x 1+x 2+x 2+…+xa)(1+x 2+x 4+…+x 2 b)(1+x 5+x 10+…+x 5 c)が多項式を展開し,次いで回数が最も小さい係数のない項を探せば時間O(n 2)
コード#コード#
#include
",ans);
}
}4、Big Event in HDU
トランスファゲート
題意を簡潔に述べる.
n種類のものがあり、それぞれの重み値はvで、m個あります.これらのものを2つに分けて、重みとできるだけ近づけるようにします.
データ範囲
0
読み込み終了が負の数であると判断し、-1とは限らず、長い間waしていた.まず生成関数でそれらの重み値を組み合わせることができることを求めて、[m/2..0]の範囲内のものを列挙すればよい時間O(nmv)
コード#コード#
#include
",m-i,i);
break;
}
}
}5、Blocks
トランスファゲート
題意を簡潔に述べる.
赤と黄と青の緑でn個の格子に染色して、赤と緑が偶数でなければならないことを要求して、方案数を求めます.10007を型抜きします.
データ範囲
T≤100,1≤n≤109
問題解
配列問題にかかわるため,指数型生成関数を用いてシナリオ数をanとし,生成関数を書くことができる:(1+x 22!+x 44!+...)2(1+x+x22!+x33!+...)2=(ex+e−x2)2⋅e2x=e2x+e−2x+24⋅e2x=e4x+2e2x+14=(4n−1+2n−1)∑n>0xnn! だからこの問題の答えは4 n−1+2 n−1です
コード#コード#
#include
",(fast_pow(4,n-1)+fast_pow(2,n-1))%Mod);
}
}6、配列の組み合わせ
トランスファゲート
題意を簡潔に述べる.
n種類の物品があって、それぞれai個があって、これらの物品の中でm個を選んで、配列数を求めます.
データ範囲
1≤n,m≤10
問題解
配列問題は,指数型生成関数指数で出現回数を表し,生成関数を書くには∏i=1 n(1+x+x 22!+x 33!+…+xaiai!)であるべきである.それから多項式を展開して第m項の係数を求める過程の中で暴力は多項式乗算をしてdoubleを使って、c++強転intが0に向かって整頓することに注意します
コード#コード#
#include
",a[m]*mul[m]);
}
}