https://codeiq.jp/q/3097

CarryOver_constLoopDone.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
#if DEBUG
		// sample
		Check(F(1, 1), 45);
		Check(F(1, 0), 55);
		Check(F(2, 0), 3025);
		Check(F(2, 1), 4500);
		Check(F(2, 2), 2475);
		Check(F(3, 1), 358875);
		
#endif		
		
		var d = ria();
		int N = d[0];
		int C = d[1];
		
		Console.WriteLine(F(N, C));
		
	}
	
	
	long F(int n,int c){
		
		long[][] dp = new long[2][];
		for(int i=0;i<2;i++) dp[i] = new long[n+2];
		
		dp[0][0] = 1;
		
		for(int i=0;i<n;i++){
			long[][] nxt = new long[2][];
			for(int j=0;j<2;j++) nxt[j] = new long[n+2];
			
			for(int cr=0;cr<2;cr++){
				for(int tot=0;tot<n+1;tot++){
					if(cr==0){
						nxt[0][tot] += 55 * dp[cr][tot];
						nxt[1][tot+1] += 45 * dp[cr][tot];
					}else{
						nxt[0][tot] += 45 * dp[cr][tot];
						nxt[1][tot+1] += 55 * dp[cr][tot];
					}
				}
			}
			
			dp = nxt;
			//Console.WriteLine("dp0:{0}",String.Join(" ",dp[0]));
			//Console.WriteLine("dp1:{0}",String.Join(" ",dp[1]));
		}
		
		return dp[0][c] + dp[1][c];
		
	}
	
	
	static bool Check(long input, long ans){
		Console.Write(input==ans?"OK":"NG");
		if(input!=ans){
			Console.Write(": input={0},ans={1}",input,ans);
		}
		Console.WriteLine();
		return input==ans;
	}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
}

CarryOver_Naive.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
#if DEBUG
		// sample
		Check(F(1, 1), 45);
		Check(F(1, 0), 55);
		Check(F(2, 0), 3025);
		Check(F(2, 1), 4500);
		Check(F(2, 2), 2475);
		Check(F(3, 1), 358875);
		
#endif		
		
		var d = ria();
		int N = d[0];
		int C = d[1];
		
		Console.WriteLine(F(N, C));
		
	}
	
	
	long F(int n,int c){
		
		long[][] dp = new long[2][];
		for(int i=0;i<2;i++) dp[i] = new long[n+2];
		
		dp[0][0] = 1;
		
		for(int i=0;i<n;i++){
			long[][] nxt = new long[2][];
			for(int j=0;j<2;j++) nxt[j] = new long[n+2];
			
			for(int cr=0;cr<2;cr++){
				for(int tot=0;tot<n+1;tot++){
					for(int a=0;a<10;a++){
						for(int b=0;b<10;b++){
							if(a+b+cr<10){
								// not carried
								nxt[0][tot] += dp[cr][tot];
							}else{
								// carried
								nxt[1][tot+1] += dp[cr][tot];
							}
						}
					}
				}
			}
			
			dp = nxt;
			//Console.WriteLine("dp0:{0}",String.Join(" ",dp[0]));
			//Console.WriteLine("dp1:{0}",String.Join(" ",dp[1]));
		}
		
		return dp[0][c] + dp[1][c];
		
	}
	
	
	static bool Check(long input, long ans){
		Console.Write(input==ans?"OK":"NG");
		if(input!=ans){
			Console.Write(": input={0},ans={1}",input,ans);
		}
		Console.WriteLine();
		return input==ans;
	}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
}

comment

Naive:
 dp[cr][tot] := cr (キャリーの有無) かつ これまでのキャリー回数の総和がtot となる組み合わせの数．
 
 Leading Zero があるものとして考えてよい．
 A+Bのそれぞれの上位の桁に 0から9を割り当てる10*10通りに対して，
 それ以前からのキャリーがあるかを考慮して，キャリーが増えたかを更新していく動的計画法

constLoopDone:
　上の各100回のループ部分は定数なのであらかじめ展開できる．これでO(N^2)の動的計画法になる．