2023-07-09：給定N、M兩個(gè)參數(shù)， 一共有N個(gè)格子，每個(gè)格子可以涂上一種顏色，顏色在M
2023-07-09：給定N、M兩個(gè)參數(shù)，
一共有N個(gè)格子，每個(gè)格子可以涂上一種顏色，顏色在M種里選，
當(dāng)涂滿N個(gè)格子，并且M種顏色都使用了，叫一種有效方法。
求一共有多少種有效方法。
1 <= N, M <= 5000。
返回結(jié)果比較大，請(qǐng)把結(jié)果 % 1000000007 之后返回。
答案2023-07-09：
這兩種算法用于計(jì)算涂色的有效方法總數(shù)。
算法?ways1：
1.初始化路徑數(shù)組?path，顏色是否使用的數(shù)組?set。
2.調(diào)用?process?函數(shù)，傳入初始參數(shù)：路徑數(shù)組?path，顏色是否使用的數(shù)組?set，當(dāng)前處理的位置?i，格子數(shù)量?n，顏色種類?m。
3.如果當(dāng)前位置?i?等于格子數(shù)量?n，即路徑數(shù)組?path?已填滿：
??將顏色是否使用的數(shù)組?
set?中所有元素重置為?false。??統(tǒng)計(jì)路徑數(shù)組?
path?中不重復(fù)的顏色數(shù)量，并記錄在?colors?中。??如果?
colors?等于顏色種類?m，說(shuō)明此路徑是有效方法，返回 1；否則返回 0。
4.否則，遍歷顏色種類?m?的所有可能顏色：
??在路徑數(shù)組?
path?當(dāng)前位置?i?處填入該顏色。??調(diào)用?
process?函數(shù)遞歸處理下一個(gè)位置?i+1。??將返回的結(jié)果累加到?
ans?上。
5.返回最終的結(jié)果?ans。
算法?ways2：
1.初始化動(dòng)態(tài)規(guī)劃數(shù)組?dp，大小為?MAXN × MAXN。
2.對(duì)于?dp?數(shù)組的第一行，設(shè)置每個(gè)位置的值為顏色種類?m。
3.使用兩層循環(huán)，從第二行開始，依次計(jì)算每個(gè)位置?dp[i][j]?的值：
??
dp[i][j]?等于前一行?dp[i-1][j]?乘以顏色種類?j?取模?mod。??添加額外的項(xiàng)，
dp[i][j]?等于前一行?dp[i-1][j-1]?乘以剩余顏色種類?m-j+1，然后加上之前的結(jié)果，再取模?mod。
4.返回?dp[n][m]?的結(jié)果作為最終的答案。
功能測(cè)試：逐個(gè)測(cè)試從 1 到 9 的格子數(shù)量和顏色種類的組合，比較兩種算法的結(jié)果是否一致，如果不一致則輸出錯(cuò)誤信息并中斷。
性能測(cè)試：以 N=5000、M=4877 為例，計(jì)算兩種算法的運(yùn)行時(shí)間并打印結(jié)果。
算法?ways1?的時(shí)間復(fù)雜度為O(m^n)，空間復(fù)雜度為O(n)。
算法?ways2?的時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度為O(nm)。
go完整代碼如下：
package?main
import?(
????"fmt"
????"time"
)
const?MAXN?=?5001
const?mod?=?1000000007
var?dp?[MAXN][MAXN]int
func?ways1(n?int,?m?int)?int?{
????path?:=?make([]int,?n)
????set?:=?make([]bool,?m+1)
????return?process(path,?set,?0,?n,?m)
}
func?process(path?[]int,?set?[]bool,?i?int,?n?int,?m?int)?int?{
????if?i?==?n?{
????????for?j?:=?0;?j?<=?m;?j++?{
????????????set[j]?=?false
????????}
????????colors?:=?0
????????for?_,?c?:=?range?path?{
????????????if?!set[c]?{
????????????????set[c]?=?true
????????????????colors++
????????????}
????????}
????????if?colors?==?m?{
????????????return?1
????????}?else?{
????????????return?0
????????}
????}?else?{
????????ans?:=?0
????????for?j?:=?1;?j?<=?m;?j++?{
????????????path[i]?=?j
????????????ans?+=?process(path,?set,?i+1,?n,?m)
????????}
????????return?ans
????}
}
func?ways2(n?int,?m?int)?int?{
????for?i?:=?1;?i?<=?n;?i++?{
????????dp[i][1]?=?m
????}
????for?i?:=?2;?i?<=?n;?i++?{
????????for?j?:=?2;?j?<=?m;?j++?{
????????????dp[i][j]?=?int((int64(dp[i-1][j])?*?int64(j))?%?mod)
????????????dp[i][j]?=?int((int64(dp[i-1][j-1])*(int64(m-j+1))?+?int64(dp[i][j]))?%?mod)
????????}
????}
????return?dp[n][m]
}
func?main()?{
????N?:=?9
????M?:=?9
????fmt.Println("功能測(cè)試開始")
????for?n?:=?1;?n?<=?N;?n++?{
????????for?m?:=?1;?m?<=?M;?m++?{
????????????ans1?:=?ways1(n,?m)
????????????ans2?:=?ways2(n,?m)
????????????if?ans1?!=?ans2?{
????????????????fmt.Println("出錯(cuò)了!")
????????????????fmt.Println("n?:?",?n)
????????????????fmt.Println("m?:?",?m)
????????????????fmt.Println("ans1?:?",?ans1)
????????????????fmt.Println("ans2?:?",?ans2)
????????????????break
????????????}
????????}
????}
????fmt.Println("功能測(cè)試結(jié)束")
????fmt.Println("性能測(cè)試開始")
????n?:=?5000
????m?:=?4877
????fmt.Println("n?:?",?n)
????fmt.Println("m?:?",?m)
????start?:=?currentTimeMillis()
????ans?:=?ways2(n,?m)
????end?:=?currentTimeMillis()
????fmt.Println("取余之后的結(jié)果?:?",?ans)
????fmt.Println("運(yùn)行時(shí)間?:?",?(end?-?start),?"?毫秒")
????fmt.Println("性能測(cè)試結(jié)束")
}
func?currentTimeMillis()?int64?{
????return?time.Now().UnixNano()?/?int64(time.Millisecond)
}
rust完整代碼如下：
fn?ways1(n:?i32,?m:?i32)?->?i32?{
????let?mut?path?=?vec![0;?n?as?usize];
????let?mut?set?=?vec![false;?(m?+?1)?as?usize];
????process(&mut?path,?&mut?set,?0,?n,?m)
}
fn?process(path:?&mut?[i32],?set:?&mut?[bool],?i:?i32,?n:?i32,?m:?i32)?->?i32?{
????if?i?==?n?{
????????set.iter_mut().for_each(|x|?*x?=?false);
????????let?mut?colors?=?0;
????????for?&c?in?path.iter()?{
????????????if?!set[c?as?usize]?{
????????????????set[c?as?usize]?=?true;
????????????????colors?+=?1;
????????????}
????????}
????????return?if?colors?==?m?{?1?}?else?{?0?};
????}?else?{
????????let?mut?ans?=?0;
????????for?j?in?1..=m?{
????????????path[i?as?usize]?=?j;
????????????ans?+=?process(path,?set,?i?+?1,?n,?m);
????????}
????????ans
????}
}
const?MAXN:?usize?=?5001;
const?MOD:?i64?=?1000000007;
static?mut?DP:?[[i32;?MAXN];?MAXN]?=?[[0;?MAXN];?MAXN];
fn?ways2(n:?i32,?m:?i32)?->?i32?{
????unsafe?{
????????for?i?in?1..=n?{
????????????DP[i?as?usize][1]?=?m;
????????}
????????for?i?in?2..=n?{
????????????for?j?in?2..=m?{
????????????????DP[i?as?usize][j?as?usize]?=
????????????????????((DP[(i?-?1)?as?usize][j?as?usize]?as?i64?*?j?as?i64)?%?MOD)?as?i32;
????????????????DP[i?as?usize][j?as?usize]?=?(((DP[(i?-?1)?as?usize][(j?-?1)?as?usize]?as?i64
????????????????????*?(m?-?j?+?1)?as?i64)
????????????????????+?DP[i?as?usize][j?as?usize]?as?i64)
????????????????????%?MOD)?as?i32;
????????????}
????????}
????????DP[n?as?usize][m?as?usize]
????}
}
fn?main()?{
????let?n:?i32?=?9;
????let?m:?i32?=?9;
????println!("功能測(cè)試開始");
????for?n_val?in?1..=n?{
????????for?m_val?in?1..=m?{
????????????let?ans1?=?ways1(n_val,?m_val);
????????????let?ans2?=?ways2(n_val,?m_val);
????????????if?ans1?!=?ans2?{
????????????????println!("出錯(cuò)了!");
????????????????println!("n?:?{}",?n_val);
????????????????println!("m?:?{}",?m_val);
????????????????println!("ans1?:?{}",?ans1);
????????????????println!("ans2?:?{}",?ans2);
????????????????break;
????????????}
????????}
????}
????println!("功能測(cè)試結(jié)束");
????println!("性能測(cè)試開始");
????let?n_val:?i32?=?5000;
????let?m_val:?i32?=?4877;
????println!("n?:?{}",?n_val);
????println!("m?:?{}",?m_val);
????let?start?=?std::time::Instant::now();
????let?ans?=?ways2(n_val,?m_val);
????let?duration?=?start.elapsed();
????println!("取余之后的結(jié)果?:?{}",?ans);
????println!("運(yùn)行時(shí)間?:?{}?毫秒",?duration.as_millis());
????println!("性能測(cè)試結(jié)束");
}
c++完整代碼如下：
using?namespace?std;
const?int?MAXN?=?5001;
const?int?mod?=?1000000007;
vector<vector<int>>?dp(MAXN,?vector<int>(MAXN,?0));
int?process(vector<int>&?path,?vector<bool>&?set,?int?i,?int?n,?int?m);
int?ways1(int?n,?int?m)?{
????vector<int>?path(n,?0);
????vector<bool>?set(m?+?1,?false);
????return?process(path,?set,?0,?n,?m);
}
int?process(vector<int>&?path,?vector<bool>&?set,?int?i,?int?n,?int?m)?{
????if?(i?==?n)?{
????????fill(set.begin(),?set.end(),?false);
????????int?colors?=?0;
????????for?(int?c?:?path)?{
????????????if?(!set[c])?{
????????????????set[c]?=?true;
????????????????colors++;
????????????}
????????}
????????return?colors?==?m???1?:?0;
????}
????else?{
????????int?ans?=?0;
????????for?(int?j?=?1;?j?<=?m;?j++)?{
????????????path[i]?=?j;
????????????ans?+=?process(path,?set,?i?+?1,?n,?m);
????????}
????????return?ans;
????}
}
int?ways2(int?n,?int?m)?{
????for?(int?i?=?1;?i?<=?n;?i++)?{
????????dp[i][1]?=?m;
????}
????for?(int?i?=?2;?i?<=?n;?i++)?{
????????for?(int?j?=?2;?j?<=?m;?j++)?{
????????????dp[i][j]?=?((long)dp[i?-?1][j]?*?j)?%?mod;
????????????dp[i][j]?=?(((long)dp[i?-?1][j?-?1]?*?(m?-?j?+?1))?+?dp[i][j])?%?mod;
????????}
????}
????return?dp[n][m];
}
int?main()?{
????int?N?=?9;
????int?M?=?9;
????cout?<<?"功能測(cè)試開始"?<<?endl;
????for?(int?n?=?1;?n?<=?N;?n++)?{
????????for?(int?m?=?1;?m?<=?M;?m++)?{
????????????int?ans1?=?ways1(n,?m);
????????????int?ans2?=?ways2(n,?m);
????????????if?(ans1?!=?ans2)?{
????????????????cout?<<?"出錯(cuò)了!"?<<?endl;
????????????????cout?<<?"n?:?"?<<?n?<<?endl;
????????????????cout?<<?"m?:?"?<<?m?<<?endl;
????????????????cout?<<?"ans1?:?"?<<?ans1?<<?endl;
????????????????cout?<<?"ans2?:?"?<<?ans2?<<?endl;
????????????????break;
????????????}
????????}
????}
????cout?<<?"功能測(cè)試結(jié)束"?<<?endl;
????cout?<<?"性能測(cè)試開始"?<<?endl;
????int?n?=?5000;
????int?m?=?4877;
????cout?<<?"n?:?"?<<?n?<<?endl;
????cout?<<?"m?:?"?<<?m?<<?endl;
????long?long?start?=?clock();
????int?ans?=?ways2(n,?m);
????long?long?end?=?clock();
????cout?<<?"取余之后的結(jié)果?:?"?<<?ans?<<?endl;
????cout?<<?"運(yùn)行時(shí)間?:?"?<<?(end?-?start)?<<?"?毫秒"?<<?endl;
????cout?<<?"性能測(cè)試結(jié)束"?<<?endl;
????return?0;
}
